243 citations · 392 across the 23 of their papers we have counts for
10 papers · 1 filter
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…
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…
Partial Feedback Online Learning
Shihao Shao, Cong Fang, Zhouchen Lin +1
We study a new learning protocol, termed partial-feedback online learning, where each instance admits a set of acceptable labels, but the learner observes only one acceptable label…