Optimal Projection-Free Adaptive SGD for Matrix Optimization

Dmitry Kovalev

math.OCApr 2, 2026

Optimal Projection-Free Adaptive SGD for Matrix Optimization

Authors: Dmitry Kovalev

Organizations: Yandex Research

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.

Figures & tables

Panel of Figure 1 — Algorithm 1 Generalized Leon for Online Optimization

Panel of Figure 2 — Algorithm 2 Generalized Leon with Nesterov Acceleration

Adaptive Gradient Methods

Adaptive Gradient Methods adjust updates using gradient history, curvature, or noise estimates to improve optimization across diverse problems.

See all 155 papers

Efficient Preconditioned Optimization Methods with Frequent Directions
Oct 12, 2026Sifan Yang, Yuanyu Wan, Yibo Wang +1Adaptive Gradient Methods Online Convex Optimization
State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China · School of Software Technology, Zhejiang University, Ningbo, China +1
Schattor: Schatten-family methods for deep learning optimization
Jun 14, 2026Bohao Ma, Junyu Zhang, Chuan HeDeep Learning Optimization Stochastic Optimization Convergence
School of Data Science, The Chinese University of Hong Kong (Shenzhen), Shenzhen, Guangdong, China · Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore · Department of Mathematics, Linköping University, Sweden
Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates
Nov 14, 2025Dmitry Kovalev, Ekaterina BorodichNonconvex Stochastic Optimization Stochastic Optimization Convergence
Yandex Research

Oct 12, 2026J/K move · Enter open · S save

Efficient Preconditioned Optimization Methods with Frequent Directions

Sifan Yang, Yuanyu Wan, Yibo Wang, Lijun Zhang

State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China · School of Software Technology, Zhejiang University, Ningbo, China+1

Adaptive Gradient Methods Online Convex Optimization Stochastic Optimization Deep Learning Optimization Randomized Sketching

Open paper AskPDF arXiv

Adaptive optimization methods have received considerable attention in recent years due to their strong empirical performance. However, they generally require maintaining a preconditioning matrix, which incurs prohibitive computational overhead in large-scale applications. To address these limitations, we investigate the acceleration of preconditioned optimization methods through frequent directions (FD), a widely used matrix sketching technique. We first propose FTSL by integrating FD with adaptive subgradient methods under the primal-dual framework and adding back the cumulative information discarded by FD. FTSL obtains a tighter regret bound than existing state-of-the-art results. We then apply a doubling trick that further reduces the time complexity of FTSL, while maintaining the same regret guarantee. We also consider optimization over matrix-valued decision variables and exploit their structural properties to construct sketched preconditioners. We develop FTSL-Shampoo by adapting FD to Shampoo and give a novel analysis under the primal-dual framework. To further mitigate its computational complexity, we design one-sided variants of FTSL-Shampoo under both mirror descent and primal-dual frameworks. Our algorithms not only reduce the computational cost of FTSL-Shampoo, but also achieve tighter regret bounds. We extend our methods to offline stochastic convex optimization and exploit smoothness to achieve faster convergence rates. Finally, we introduce practical variants of our algorithms and empirically demonstrate their efficiency and effectiveness across a broad range of tasks.

Abstract

Adaptive Gradient Methods

Explore similar work

Efficient Preconditioned Optimization Methods with Frequent Directions

Schattor: Schatten-family methods for deep learning optimization

Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates