More Like this

1. A convex combination based primal-dual algorithm with linesearch for general convex-concave saddle point problems

   https://doi.org/10.1093/imanum/draf158  

   Chang, Xiaokai; Yang, Junfeng; Zhang, Hongchao (April 2026, IMA Journal of Numerical Analysis)

   Abstract Using convex combination and linesearch techniques, we introduce a novel primal-dual algorithm for solving structured convex–concave saddle point problems with a generic, smooth, nonbilinear coupling term. Our adaptive linesearch strategy works under specific local smoothness conditions, allowing for potentially larger step sizes. For an important class of structured convex optimization problems, the proposed algorithm reduces to a fully adaptive proximal gradient algorithm without linesearch, thereby representing an advancement over the golden ratio algorithm delineated in Malitsky,Y. (2020, Golden ratio algorithms for variational inequalities. Math. Program., 184, 383–410). We establish the global pointwise and ergodic sublinear convergence rate of the algorithm, measured by the restricted merit function in the general case. When the coupling term is linear in the dual variable, we measure the convergence rate by the function value residual and constraint violation of an equivalent constrained optimization problem. Furthermore, an accelerated algorithm achieving a faster $$ O(1/N^{2})$$ ergodic convergence rate is presented for the strongly convex case, where $$N$$ denotes the iteration number. The convergence rates established in this work are optimal (up to a constant factor) under the corresponding assumptions. Our numerical experiments on quadratically constrained quadratic programming and sparse logistic regression problems indicate that the new algorithm is significantly faster than the comparison algorithms. 

   more » « less
2. Multivariate Distributionally Robust Convex Regression under Absolute Error Loss

   Blanchet, Jose and (October 2019, Advances in Neural Information Processing Systems 32 (NIPS 2019))

   This paper proposes a novel non-parametric multidimensional convex regression estimator which is designed to be robust to adversarial perturbations in the empirical measure. We minimize over convex functions the maximum (over Wasserstein perturbations of the empirical measure) of the absolute regression errors. The inner maximization is solved in closed form resulting in a regularization penalty involves the norm of the gradient. We show consistency of our estimator and a rate of convergence of order O˜(n−1/d), matching the bounds of alternative estimators based on square-loss minimization. Contrary to all of the existing results, our convergence rates hold without imposing compactness on the underlying domain and with no a priori bounds on the underlying convex function or its gradient norm. 

   more » « less
3. Sparse Tensor Additive Regression

   Hao, Botao; Wang, Boxiang; Wang, Pengyuan; Zhang, Jingfei; Yang, Jian; Sun, Will Wei (January 2021, Journal of machine learning research)

   null (Ed.)

   Tensors are becoming prevalent in modern applications such as medical imaging and digital marketing. In this paper, we propose a sparse tensor additive regression (STAR) that models a scalar response as a flexible nonparametric function of tensor covariates. The proposed model effectively exploits the sparse and low-rank structures in the tensor additive regression. We formulate the parameter estimation as a non-convex optimization problem, and propose an efficient penalized alternating minimization algorithm. We establish a non-asymptotic error bound for the estimator obtained from each iteration of the proposed algorithm, which reveals an interplay between the optimization error and the statistical rate of convergence. We demonstrate the efficacy of STAR through extensive comparative simulation studies, and an application to the click-through-rate prediction in online advertising. 

   more » « less
4. MARS via LASSO

   https://doi.org/10.1214/24-AOS2384  

   Ki, Dohyeong; Fang, Billy; Guntuboyina, Adityanand (June 2024, The Annals of Statistics)

   Multivariate adaptive regression splines (MARS) is a popular method for nonparametric regression introduced by Friedman in 1991. MARS fits sim- ple nonlinear and non-additive functions to regression data. We propose and study a natural lasso variant of the MARS method. Our method is based on least squares estimation over a convex class of functions obtained by con- sidering infinite-dimensional linear combinations of functions in the MARS basis and imposing a variation based complexity constraint. Our estimator can be computed via finite-dimensional convex optimization, although it is defined as a solution to an infinite-dimensional optimization problem. Under a few standard design assumptions, we prove that our estimator achieves a rate of convergence that depends only logarithmically on dimension and thus avoids the usual curse of dimensionality to some extent. We also show that our method is naturally connected to nonparametric estimation techniques based on smoothness constraints. We implement our method with a cross- validation scheme for the selection of the involved tuning parameter and compare it to the usual MARS method in various simulation and real data settings. 

   more » « less
5. Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality

   Lacotte, Jonathan; Wang, Yifei; Pilanci, Mert (January 2021, Preceedings of the 38th International Conference on Machine Learning)

   We propose a randomized algorithm with quadratic convergence rate for convex optimization problems with a self-concordant, composite, strongly convex objective function. Our method is based on performing an approximate Newton step using a random projection of the Hessian. Our first contribution is to show that, at each iteration, the embedding dimension (or sketch size) can be as small as the effective dimension of the Hessian matrix. Leveraging this novel fundamental result, we design an algorithm with a sketch size proportional to the effective dimension and which exhibits a quadratic rate of convergence. This result dramatically improves on the classical linear-quadratic convergence rates of state-of-theart sub-sampled Newton methods. However, in most practical cases, the effective dimension is not known beforehand, and this raises the question of how to pick a sketch size as small as the effective dimension while preserving a quadratic convergence rate. Our second and main contribution is thus to propose an adaptive sketch size algorithm with quadratic convergence rate and which does not require prior knowledge or estimation of the effective dimension: at each iteration, it starts with a small sketch size, and increases it until quadratic progress is achieved. Importantly, we show that the embedding dimension remains proportional to the effective dimension throughout the entire path and that our method achieves state-of-the-art computational complexity for solving convex optimization programs with a strongly convex component. We discuss and illustrate applications to linear and quadratic programming, as well as logistic regression and other generalized linear models. 

   more » « less