22 papers
Gradient-Hessian Query Tradeoffs: Matching Lower Bounds in Logarithmic Dimension
Wendao Wu, Haihan Zhang, Chenheng Zhang +5
We establish matching lower bounds for the tradeoff between gradient and Hessian queries in nonconvex optimization with Lipschitz Hessian. In normalized units, the initial objectiv…
Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning
Yanyi Li, Wendao Wu, Haihan Zhang +6
Tracking changing comparators is a central problem in online learning. For exp-concave losses, previous work established the dependence on the horizon and Eu…
Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization
Haihan Zhang, Wendao Wu, Fangqing Zhang +5
Does randomization improve the worst-case first-order complexity of nonconvex optimization when the objective is very smooth? We prove that, for every fixed finite integer ,…
Matching Randomized Bounds for Finite-Sum Nonconvex-Concave Optimization
Wendao Wu, Haihan Zhang, Qian Chen +5
We characterize the randomized component-oracle complexity of finite-sum nonconvex-concave optimization with a bounded dual domain. For $Φ(x)=\max_{y\in Y}n^{-1}\sum_{i=1}^n f_i(x,…
Matching Complexity for Second-Order Stationary Point with Sample Reuse
Qian Chen, Wendao Wu, Haihan Zhang +5
We consider stochastic nonconvex optimization with sample-wise Lipschitz gradients and Hessians, and reusable opaque sample handles. Gradient and complete-Hessian evaluations are c…
Matching Full-Hessian Oracle Complexity for Nonconvex--Strongly-Concave Minimax Optimization
Fangqing Zhang, Haihan Zhang, Wendao Wu +5
We characterize the oracle complexity of finding first-order stationary points in smooth nonconvex--strongly-concave (NC--SC) minimax optimization when each query provides the full…
ORCA: The Annealed Spectral Conditioning Optimizer for Faster, Better LLM Training
Yuanshi Liu, Boyuan Jiang, Liang Hou +4
Modern LLM optimizers such as Muon often produce weight matrices with higher effective rank than Adam, yet further spectral control has delivered only modest gains. We identify a t…
The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization
Wendao Wu, Haihan Zhang, Chenheng Zhang +5
We study the sample complexity of finding a point with expected hypergradient norm at most in nonconvex--strongly-convex stochastic bilevel optimization using fresh, globally…
Closing the Accuracy Gap in Stochastic First-Order Bilevel Optimization
Haihan Zhang, Wendao Wu, Chenheng Zhang +5
We characterize the optimal accuracy dependence for smooth nonconvex--strongly-convex bilevel optimization with stochastic first-order oracles. For globally unbiased fresh-gradient…
Matrix-Vector Complexity of Low-Rank Approximation
Haihan Zhang, Wendao Wu, Chenheng Zhang +5
We establish matching polynomial query bounds for low-rank approximation from exact matrix--vector products. Given an unknown matrix , at each step a ra…
Convergence of Rotation-based Matrix Optimizers: A Unified Analysis of SOAP, Conda, and SPlus
Yiwen Sun, Huan Li, Zhouchen Lin
In this work, we develop a unified theoretical framework for analyzing the convergence of rotation-based matrix optimizers, which apply orthogonal transformations to map the moment…
Matching Higher-Order Oracle Complexity for Smooth Monotone Variational Inequalities
Haihan Zhang, Wendao Wu, Chenheng Zhang +3
We establish near-optimal higher-order oracle bounds for smooth monotone variational inequalities. For fixed , let be monotone on a known compact convex set of diame…
Convergence Rate Analysis of SOAP with Arbitrary Orthogonal Projection Matrices
Huan Li, Zhouchen Lin
In this short note, we establish, for the first time, the convergence rate of SOAP, an efficient and popular matrix-based optimizer for training deep neural networks. Our analysis…
Convergence Rate Analysis of the AdamW-style Shampoo: Unifying One-Sided and Two-Sided Preconditioning
Huan Li, Yiming Dong, Zhouchen Lin
This paper studies AdamW-style Shampoo, an effective variant of the classical Shampoo that won the external tuning track of the AlgoPerf neural network training competition. Our an…
Improving Model Representation and Reducing KV Cache via Skip Connections with First Value Heads
Zhoutong Wu, Yuan Zhang, Yiming Dong +4
Transformer models have driven breakthroughs across various language tasks by their strong capability to learn rich contextual representations. Scaling them to improve representati…
Conda: Column-Normalized Adam for Training Large Language Models Faster
Junjie Wang, Pan Zhou, Yiming Dong +6
Large language models (LLMs) have demonstrated impressive generalization and emergent capabilities, yet their pre-training remains computationally expensive and sensitive to optimi…
DNT: a Deeply Normalized Transformer that can be trained by Momentum SGD
Xianbiao Qi, Marco Chen, Wenjie Xiao +4
Transformers have become the de facto backbone of modern deep learning, yet their training typically demands an advanced optimizer with adaptive learning rate like AdamW, rather th…
Simple Convergence Proof of Adam From a Sign-like Descent Perspective
Hanyang Peng, Shuang Qin, Yue Yu +3
Adam is widely recognized as one of the most effective optimizers for training deep neural networks (DNNs). Despite its remarkable empirical success, its theoretical convergence an…
Stepsize anything: A unified learning rate schedule for budgeted-iteration training
Anda Tang, Yiming Dong, Yutao Zeng +2
The expanding computational costs and limited resources underscore the critical need for budgeted-iteration training, which aims to achieve optimal learning within predetermined it…
On the Convergence Rate of AdamW Measured by Norm
Huan Li, Yiming Dong, Zhouchen Lin
As the default optimizer for training large language models, AdamW has achieved remarkable success in deep learning. However, its convergence behavior is not theoretically well-und…
Convergence Rate Analysis of LION
Yiming Dong, Huan Li, Zhouchen Lin
The LION (evoLved sIgn mOmeNtum) optimizer for deep neural network training was found by Google via program search, with the simple sign update yet showing impressive performance i…
On the Convergence Rate of RMSProp and Its Momentum Extension Measured by Norm
Huan Li, Yiming Dong, Zhouchen Lin
Although adaptive gradient methods have been extensively used in deep learning, their convergence rates proved in the literature are all slower than that of SGD, particularly with…