A tight lower bound is proved of $\Omega(\lambda^{1/2}\epsilon^{-7/2})$ for finding points satisfying the recently proposed relaxed notion of $(\lambda,\epsilon)$-stationarity, which allows combining further-away gradients.
Abstract
We prove that first-order algorithms require $\Omega(\delta^{-1}\epsilon^{-3})$ gradient queries (in the worst case) to find a $(\delta,\epsilon)$-Goldstein stationary point of a Lipschitz function, at which there is a convex combination of gradients within distance $\delta$ whose norm is at most $\epsilon$. This lower bound is tight, matching known algorithms up to absolute constants, therefore resolving the complexity of convergence to stationarity in nonsmooth nonconvex optimization. We further prove a tight lower bound of $\Omega(\lambda^{1/2}\epsilon^{-7/2})$ for finding points satisfying the recently proposed relaxed notion of $(\lambda,\epsilon)$-stationarity, which allows combining further-away gradients. Our results reveal that convergence rates to nonsmooth stationarity are not affected by gradient stochasticity, in sharp contrast to smooth optimization.
The results establish an exponential computational advantage in nonsmooth nonconvex optimization offered by randomization by proving a lower bound of order $(1/\epsilon)^{\Omega(d)}$ for deterministic algorithm, closing the exponential gap between the previously known lower and upper bounds.
It is proved that every deterministic first-order method requires $\Omega(\ell\Delta\kappa/\epsilon^2)$ oracle queries in the worst case to find $x$ satisfying $\Phi(0)-\inf_x\Phi(x)$ and that the linear dependence on $\kappa$ is unavoidable for deterministic first-order methods.
The bounded-variance lower bound improves the dependence on the condition number from $\kappa^{1/3}$ in previous lower bounds to $\kappa$, while the averaged-smoothness lower bound is the first of its kind.
We establish a randomized first-order lower bound for finding an $\epsilon$-stationary point, $\|\nabla f(x)\|\le \epsilon$, of a nonconvex function with initial gap at most $\Delta$, $L_1$-Lipschitz gradient, and $L_2$-Lipschitz Hessian. Each oracle call returns the exact function value and gradient. Let $Q_{\mathrm{r...
We study whether the linear condition-number dependence in the stochastic complexity of SAPD+ is necessary for nonconvex-strongly-concave minimax optimization. For jointly $L$-smooth objectives with dual strong-concavity parameter $\mu$, we prove a lower bound that matches the SAPD+ upper bound under the same Moreau-en...
We prove a joint stochastic zeroth-order lower bound for Goldstein stationarity on a Euclidean query ball, even when the ball is guaranteed to contain a stationary point. In dimension $d$, let $f=\mathbb{E}[F(\cdot;\xi)]$, assume $\mathbb{E}[\operatorname{Lip}(F(\cdot;\xi))^2]\le L_0^2$, and bound the initial objective...