Organizations: 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 · State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China
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.
Table 1: Comparison of ADA-FULL and its FD-based variants, where (M) and (P) represent the primal-dual framework and the mirror descent framework, respectively.
Table 2: Comparison of FD-based variants of ADA-FULL, where (M) and (P) represent the primal-dual framework and the mirror descent framework, respectively.
Table 3: Comparison of adaptive methods when the decision has a matrix structure Xt∈Rm×n , where (M) and (P) represent the primal-dual framework and the mirror descent framework, respectively. Without loss of generality, we assume m≤n . We denote the gradient by GtX∈Rm×n and let r be the largest rank of GtX .
Figure 1: Results for the Gisette dataset.
Figure 2: Results for the Epsilon dataset.
Figure 3: Running time of two types of SVD implementation.
Figure 4: Results for the CIFAR-10 dataset.
Figure 5: Results for the CIFAR-100 dataset.
Figure 6: Results of the running time.
Figure 7: Results for GPT-2 Pretraining with a sequence length of 512 .
Figure 8: Results for GPT-2 Pretraining with a sequence length of 256 .
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.
Modern deep learning optimization features heterogeneous parameter structures, noisy gradients, and highly nonconvex landscapes, posing significant challenges for both algorithm design and theoretical analysis. Motivated by the limitations of SGD and the success of adaptive optimizers, we propose {\it Schattor}, a family of adaptive first-order methods based on Schatten norms. Schattor unifies SGD and the recently proposed matrix-variate adaptive optimizer Muon within a single Schatten-norm-based framework. We establish dimension-free stationarity guarantees for methods in the Schattor family for stochastic matrix optimization problems via a novel matrix martingale moment bound. We also develop multi-block extensions that adaptively balance block-wise optimization progress and prove dimension-free stationarity guarantees in this more general setting.
Bohao Ma, Junyu Zhang, Chuan He
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
We develop a comprehensive theoretical analysis of Matrix Shampoo for tracking time-varying optima in nonstationary stochastic optimization. We derive finite-horizon high-probability bounds for average tracking error that disentangle initialization, optimizer drift, momentum-induced drift penalty, stochastic noise, and adaptive preconditioning, with explicit dependence on momentum parameter β1 and stabilization parameter ε. These bounds reveal an explicit drift--noise and stability--geometry tradeoffs: noise-dominated regimes favor larger β1, which provides stronger first-moment averaging and greater suppression of gradient noise, whereas drift-dominated regimes favor smaller β1, allowing faster adaptation to moving optimizer. Larger ε reduces the preconditioner-perturbation term while weakening Shampoo's ability to exploit matrix geometry, thereby reducing adaptivity. We establish a matching minimax lower bound under squared path-variation constraint, proving the information-theoretic optimality of Shampoo over the class of causal optimization procedures. Under a constant stepsize, we establish high-probability bounds for the average projected stationarity gap along general nonstationary nonconvex objectives. We validate our theoretical findings on both synthetic and multiple real-world problems.
Abir Sarkar, Nirmalya Mandal, Martin T. Wells
Department of Statistics and Data Science, Cornell University · Department of Statistics, NC State University