Complexity of Minimizing Projected-Gradient-Dominated Functions with Stochastic First-order Oracles
<|reference_start|>Complexity of Minimizing Projected-Gradient-Dominated Functions with Stochastic First-order Oracles: This work investigates the performance limits of projected stochastic first-order methods for minimizing functions under the $(\alpha,\tau,\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 $\tau\cdot\|\mathcal{G}_{\eta,\mathcal{X}}(\mathbf{x})\|^{\alpha}$ for some $\alpha\in[1,2)$ and $\tau>0$ and $\mathcal{G}_{\eta,\mathcal{X}}(\mathbf{x})$ is the projected-gradient mapping with $\eta>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 $\epsilon$-global-optimum point is $\Omega(\epsilon^{-{2}/{\alpha}})$. Furthermore, we show that a projected variance-reduced first-order algorithm can obtain the upper complexity bound of $\mathcal{O}(\epsilon^{-{2}/{\alpha}})$, matching the lower bound. For convex functions, we establish a complexity lower bound of $\Omega(\log(1/\epsilon)\cdot\epsilon^{-{2}/{\alpha}})$ for minimizing functions under a local version of gradient-dominance property, which also matches the upper complexity bound of accelerated stochastic subgradient methods.<|reference_end|>
@article{masiha2024complexity,
    title={Complexity of Minimizing Projected-Gradient-Dominated Functions with
  Stochastic First-order Oracles},
    author={Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, and
  Patrick Thiran},
    journal={arXiv preprint arXiv:2408.01839},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.01839},
    primaryClass={math.OC cs.LG}
}