Optimal Projection-Free Adaptive SGD for Matrix Optimization

• URL: http://arxiv.org/abs/2604.02505v1
• Date: Thu, 02 Apr 2026 21:02:10 GMT
• Title: Optimal Projection-Free Adaptive SGD for Matrix Optimization
• Abstract summary: Recently, Jiang et al. developed Leon, a practical variant of One-sided Shampoo [Xie et al., 2025a, An et al., 2025] algorithm for online convex projections.<n>In this paper, we prove certain properties of Leon's stability preconditioner.<n>We develop the first practical variant of One-sided Shampoo with Nesterov acceleration.
• Score: 10.350093268971836
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, Jiang et al. [2026] developed Leon, a practical variant of One-sided Shampoo [Xie et al., 2025a, An et al., 2025] algorithm for online convex optimization, which does not require computing a costly quadratic projection at each iteration. Unfortunately, according to the existing analysis, Leon requires tuning an additional hyperparameter in its preconditioner and cannot achieve dimension-independent convergence guarantees for convex optimization problems beyond the bounded gradients assumption. In this paper, we resolve this issue by proving certain stability properties of Leon's preconditioner. Using our improved analysis, we show that tuning the extra hyperparameter can be avoided and, more importantly, develop the first practical variant of One-sided Shampoo with Nesterov acceleration, which does not require computing projections at each iteration. As a side contribution, we obtain improved dimension-independent rates in the non-smooth non-convex setting and develop a unified analysis of the proposed algorithm, which yields accelerated projection-free adaptive SGD with (block-)diagonal preconditioners.

Related papers

• Schattor: Schatten-family methods for deep learning optimization [13.92796349861358]
  We propose a family of adaptive firstorder methods based on Schatten norms.<n>We establish dimension-free station guarantees for methods Schattor and SGD.<n>We also develop multiblock extensions that adaptively balance block-wise optimization progress.
  arXiv  Detail & Related papers  (2026-06-14T09:31:59Z)
• Stochastic Non-Smooth Convex Optimization with Unbounded Gradients [10.350093268971836]
  We show that clipped AdamW is theoretically better than other popular optimization methods, such as SGDW and AdaGrad.<n>We also establish the critical role of AdamW's exponentially weighted accumulation, as opposed to simple averaging.
  arXiv  Detail & Related papers  (2026-05-15T01:43:22Z)
• Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization [54.723834588133165]
  We study online linear optimization with matrix variables by the operatorAML, a setting where the geometry renders designing datadependent and efficient adaptive algorithms challenging.<n>We instantiate this framework with two efficient methods that avoid projections.<n>We show both methods admit closed-form updates match one-sided Shampoo's regret up to a constant factor, while significantly reducing computational cost.
  arXiv  Detail & Related papers  (2026-02-09T03:09:47Z)
• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization [57.179679246370114]
  A potential limitation of existing methods is the bias inherent in most perturbation estimators unless a stepsize is proposed.<n>We propose a novel family of unbiased gradient scaling estimators that eliminate bias while maintaining favorable construction.
  arXiv  Detail & Related papers  (2025-10-22T18:25:43Z)
• Towards Weaker Variance Assumptions for Stochastic Optimization [19.339358874690568]
  We revisit a classical assumption for analyzing gradient algorithms where the squared norm of the subgradient is allowed to grow as fast as the squared norm of the optimization variable.<n>We analyze convex problems with functional constraints or regularized convex-concave min-max problems.<n>We obtain rates for optimality measures that do not require boundedness of the feasible set.
  arXiv  Detail & Related papers  (2025-04-14T07:26:34Z)
• Structured Preconditioners in Adaptive Optimization: A Unified Analysis [30.17859434112402]
  We present a novel unified analysis for a broad class of adaptive optimization algorithms with structured preconditioners.<n>Our analysis provides matching rate to several important structured preconditioned algorithms including diagonal AdaGrad, full-matrix AdaGrad, and AdaGrad-Norm.<n>We show that one-sided Shampoo, which is relatively much cheaper than full-matrix AdaGrad could outperform it both theoretically and experimentally.
  arXiv  Detail & Related papers  (2025-03-13T16:51:59Z)
• A Novel Unified Parametric Assumption for Nonconvex Optimization [53.943470475510196]
  Non optimization is central to machine learning, but the general framework non convexity enables weak convergence guarantees too pessimistic compared to the other hand.<n>We introduce a novel unified assumption in non convex algorithms.
  arXiv  Detail & Related papers  (2025-02-17T21:25:31Z)
• Parameter-free projected gradient descent [0.0]
  We consider the problem of minimizing a convex function over a closed convex set, with Projected Gradient Descent (PGD) We propose a fully parameter-free version of AdaGrad, which is adaptive to the distance between the initialization and the optimum, and to the sum of the square norm of the subgradients. Our algorithm is able to handle projection steps, does not involve restarts, reweighing along the trajectory or additional evaluations compared to the classical PGD.
  arXiv  Detail & Related papers  (2023-05-31T07:22:44Z)
• Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives [1.7640556247739623]
  We analyze algorithms for zeroth-order entropy composite objectives, focusing on dependence on dimensionality. This is achieved by exploiting low dimensional structure of the decision set using the mirror descent method with an estimation alike function. To improve the gradient, we replace the classic sampling method based on Rademacher and show that the mini-batch method copes with non-Eucli geometry.
  arXiv  Detail & Related papers  (2022-08-09T07:36:25Z)
• Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares [68.8204255655161]
  We consider potentially non- optimized approximation problems. In this paper, we propose an algorithm that achieves close to optimal a priori computational guarantees.
  arXiv  Detail & Related papers  (2022-04-11T09:37:04Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  In high dimensional sparse regression, pivotal estimators are estimators for which the optimal regularization parameter is independent of the noise level. We show minimax sup-norm convergence rates for non smoothed and smoothed, single task and multitask square-root Lasso-type estimators.
  arXiv  Detail & Related papers  (2020-01-15T16:11:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.