More Like this

1. 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
2. On Global and Local Convergence of Iterative Linear Quadratic Optimization Algorithms for Discrete Time Nonlinear Control

   Roulet, V; Srinivasa, S; Fazel, M; Harchaoui, Z (May 2025, Journal of machine learning research)

   Jaggi, Martin (Ed.)

   A classical approach for solving discrete time nonlinear control on a nite horizon consists in repeatedly minimizing linear quadratic approximations of the original problem around current candidate solutions. While widely popular in many domains, such an approach has mainly been analyzed locally. We provide detailed convergence guarantees to stationary points as well as local linear convergence rates for the Iterative Linear Quadratic Regulator (ILQR) algorithm and its Di erential Dynamic Programming (DDP) variant. For problems without costs on control variables, we observe that global convergence to minima can be ensured provided that the linearized discrete time dynamics are surjective, costs on the state variables are gradient dominated. We further detail quadratic local convergence when the costs are self-concordant. We show that surjectivity of the linearized dynamics hold for appropriate discretization schemes given the existence of a feedback linearization scheme. We present complexity bounds of algorithms based on linear quadratic approximations through the lens of generalized Gauss-Newton methods. Our analysis uncovers several convergence phases for regularized generalized Gauss-Newton algorithms. 

   more » « less
3. 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
4. LSEMINK: a modified Newton–Krylov method for Log-Sum-Exp minimization

   https://doi.org/10.1553/etna_vol60s618  

   Kan, Kelvin; Nagy, James G; Ruthotto, Lars (January 2024, ETNA - Electronic Transactions on Numerical Analysis)

   This paper introduces LSEMINK, an effective modified Newton–Krylov algorithm geared toward minimizing the log-sum-exp function for a linear model. Problems of this kind arise commonly, for example, in geometric programming and multinomial logistic regression. Although the log-sum-exp function is smooth and convex, standard line-search Newton-type methods can become inefficient because the quadratic approximation of the objective function can be unbounded from below. To circumvent this, LSEMINK modifies the Hessian by adding a shift in the row space of the linear model. We show that the shift renders the quadratic approximation to be bounded from below and that the overall scheme converges to a global minimizer under mild assumptions. Our convergence proof also shows that all iterates are in the row space of the linear model, which can be attractive when the model parameters do not have an intuitive meaning, as is common in machine learning. Since LSEMINK uses a Krylov subspace method to compute the search direction, it only requires matrix-vector products with the linear model, which is critical for large-scale problems. Our numerical experiments on image classification and geometric programming illustrate that LSEMINK considerably reduces the time-to-solution and increases the scalability compared to geometric programming and natural gradient descent approaches. It has significantly faster initial convergence than standard Newton–Krylov methods, which is particularly attractive in applications like machine learning. In addition, LSEMINK is more robust to ill-conditioning arising from the nonsmoothness of the problem. We share our MATLAB implementation at a GitHub repository (https://github.com/KelvinKan/LSEMINK). 

   more » « less
5. A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression

   https://doi.org/10.1145/3744970.3727269  

   Zhang, Yixuan; Huo, Dongyan Lucy; Chen, Yudong; Xie, Qiaomin (June 2025, ACM SIGMETRICS Performance Evaluation Review)

   Motivated by robust and quantile regression problems, we investigate the stochastic gradient descent (SGD) algorithm for minimizing an objective functionfthat is locally strongly convex with a sub--quadratic tail. This setting covers many widely used online statistical methods. We introduce a novel piecewise Lyapunov function that enables us to handle functionsfwith only first-order differentiability, which includes a wide range of popular loss functions such as Huber loss. Leveraging our proposed Lyapunov function, we derive finite-time moment bounds under general diminishing stepsizes, as well as constant stepsizes. We further establish the weak convergence, central limit theorem and bias characterization under constant stepsize, providing the first geometrical convergence result for sub--quadratic SGD. Our results have wide applications, especially in online statistical methods. In particular, we discuss two applications of our results. 1) Online robust regression: We consider a corrupted linear model with sub--exponential covariates and heavy--tailed noise. Our analysis provides convergence rates comparable to those for corrupted models with Gaussian covariates and noise. 2) Online quantile regression: Importantly, our results relax the common assumption in prior work that the conditional density is continuous and provide a more fine-grained analysis for the moment bounds. 

   more » « less