2 citations · 5 across the 9 of their papers we have counts for
7 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…
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…
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…