Complexity of Minimizing Projected-Gradient-Dominated Functions with Stochastic First-order Oracles

Abstract

This work investigates the performance limits of projected stochastic first-order methods for minimizing functions under the $(α,τ,\mathcal{X})$-projected-gradient-dominance property, that asserts the sub-optimality gap $F(\mathbf{x})-\min_{\mathbf{x}'\in \mathcal{X}}F(\mathbf{x}')$ is upper-bounded by $τ\cdot\|\mathcal{G}_{η,\mathcal{X}}(\mathbf{x})\|^α$ for some $α\in[1,2)$ and $τ>0$ and $\mathcal{G}_{η,\mathcal{X}}(\mathbf{x})$ is the projected-gradient mapping with $η>0$ as a parameter. For non-convex functions, we show that the complexity lower bound of querying a batch smooth first-order stochastic oracle to obtain an $ε$-global-optimum point is $Ω(ε^{-{2}/α})$. Furthermore, we show that a projected variance-reduced first-order algorithm can obtain the upper complexity bound of $\mathcal{O}(ε^{-{2}/α})$, matching the lower bound. For convex functions, we establish a complexity lower bound of $Ω(\log(1/ε)\cdotε^{-{2}/α})$ for minimizing functions under a local version of gradient-dominance property, which also matches the upper complexity bound of accelerated stochastic subgradient methods.