10 papers · 1 filter
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…