12 papers · 2 filters
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…
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…
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…