15 papers
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…
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…
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…
Near-Optimal Lower Bounds for Randomized Algorithms in Exact Value Zeroth-Order Convex Optimization
Haihan Zhang, Chenheng Zhang, Zhiquan Qi +1
Whether exact scalar feedback intrinsically incurs the additional dimension paid by known zeroth-order methods remains open even for Lipschitz convex optimization. For a univer…
What Makes a Strong Model? A Unified Spectral Analysis of Knowledge Transfer over High-dimensional Linear Regression
Wendao Wu, Fangqing Zhang, Haihan Zhang +1
Teacher-Student Knowledge Transfer (KT) is ubiquitous in modern machine learning, ranging from classical model compression via Knowledge Distillation (KD) to the emergent phenomeno…
Reliable Fine-Grained Evaluation of Natural Language Math Proofs
Wenjie Ma, Andrei Cojocaru, Neel Kolhe +6
Recent advances in large language models (LLMs) for mathematical reasoning have largely focused on tasks with easily verifiable final answers while generating and verifying natural…
Learning Curves of Stochastic Gradient Descent in Kernel Regression
Haihan Zhang, Weicheng Lin, Yuanshi Liu +1
This paper considers a canonical problem in kernel regression: how good are the model performances when it is trained by the popular online first-order algorithms, compared to the…
Scaling Law for Stochastic Gradient Descent in Quadratically Parameterized Linear Regression
Shihong Ding, Haihan Zhang, Hanzhen Zhao +1
In machine learning, the scaling law describes how the model performance improves with the model and data size scaling up. From a learning theory perspective, this class of results…
Optimal Algorithms in Linear Regression under Covariate Shift: On the Importance of Precondition
Yuanshi Liu, Haihan Zhang, Qian Chen +1
A common pursuit in modern statistical learning is to attain satisfactory generalization out of the source data distribution (OOD). In theory, the challenge remains unsolved even u…
The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization
Haihan Zhang, Yuanshi Liu, Qianwen Chen +1
Stochastic gradient descent (SGD) is a widely used algorithm in machine learning, particularly for neural network training. Recent studies on SGD for canonical quadratic optimizati…