The new first-order lower bound is specifically robust to persistent sample reuse and to complete-Hessian access, and uses a slowly parameterized conservative sign chain, a third-order reverse stick-breaking localization inequality, and stateful relative-entropy accounting for reusable handles.
Abstract
We consider stochastic nonconvex optimization with sample-wise Lipschitz gradients and Hessians, and reusable opaque sample handles. Gradient and complete-Hessian evaluations are charged separately, including both endpoints of a same-sample difference. For fixed positive problem parameters and in the high-dimensional worst case, we prove that the minimax total derivative-query complexity of finding an $(\varepsilon,\gamma)$-second-order stationary point is \begin{equation*} \widetilde\Theta(\varepsilon^{-3}+\gamma^{-3}). \end{equation*} The upper bound combines curvature-first randomly signed negative-curvature steps with binary-ancestor derivative estimators; a truncated increment estimate charges predictable drift linearly and martingale motion quadratically. The curvature lower bound uses a deterministic smooth bounded-gradient chain, a radial barrier, and a random rotation. The new first-order lower bound is specifically robust to persistent sample reuse and to complete-Hessian access. It uses a slowly parameterized conservative sign chain, a third-order reverse stick-breaking localization inequality, and stateful relative-entropy accounting for reusable handles. Thus the total rate is near-optimally matched for every relation between $\varepsilon$ and $\gamma$.
We study the sample complexity of finding a point with expected hypergradient norm at most $\epsilon>0$ in nonconvex--strongly-convex stochastic bilevel optimization using fresh, globally unbiased first-order samples with bounded variance. For lower-variable smoothness order $p\ge1$, F$^2$SA-$p$ achieves $\widetilde O(...
Wen-Dao Wu, Hai-Han Zhang, Chen-Heng Zhang et al.· 0 citations
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 $p\ge3$, finding an $\eps$-stationary point requires $\Omega_p(\eps^{-5/3})$ exact value-and-gradient queries, even for $C^\infty$ objectives with i...
Hai-Han Zhang, Wen-Dao Wu, Fang-Qing Zhang et al.· 0 citations
We study nonconvex--strongly-convex bilevel optimization under a stochastic first-order oracle. We introduce MRT-FD, a single-loop first-order method that simultaneously tracks the upper-level variable, the lower-level solution, and the auxiliary response arising from implicit differentiation of the hyperobjective. MRT...
We develop accelerated gradient-free methods for stochastic convex optimization with constraints defined by expectations. Our batched primal-dual sliding method uses two-point evaluations sharing a random sample and guarantees expected objective error and expected maximum constraint violation at most $\varepsilon$. It...
Vadim Abronin, A. Gasnikov, D. Dvinskikh· 0 citations
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 Hessian in addition to the function value and gradient. For $\Phi(x)=\max_y f(x,y)$, assume that $f$ has an $L$-Lipschitz gradient, a $\rho...
Fang-Qing Zhang, Hai-Han Zhang, Wen-Dao Wu et al.· 0 citations
We study how curvature estimated from gradient differences can accelerate proximal-extragradient quasi-Newton methods. Existing global guarantees for QNPE, A-QNPE, and OL-OQN learn Hessian approximations online and incur dimension dependence through regret bounds. We introduce certified curvature reuse: one finite-diff...
Aryan Mokhtari, Francisco Patitucci· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.