ICML 2017poster52 citations
Stochastic Convex Optimization: Faster Local Growth Implies Faster Global Convergence
Yi Xu, Qihang Lin, Tianbao Yang
Abstract
In this paper, a new theory is developed for first-order stochastic convex optimization, showing that the global convergence rate is sufficiently quantified by a local growth rate of the objective function in a neighborhood of the optimal solutions. In particular, if the objective function $F(\mathbf{w})$ in the $\epsilon$-sublevel set grows as fast as $\|\mathbf{w} - \mathbf{w}_*\|_2^{1/\theta}$, where $\mathbf{w}_*$ represents the closest optimal solution to $\mathbf{w}$ and $\theta\in(0,1]$ quantifies the local growth rate, the iteration complexity of first-order stochastic optimization for achieving an $\epsilon$-optimal solution can be $\widetilde O(1/\epsilon^{2(1-\theta)})$, which is
BibTeX
@InProceedings{pmlr-v70-xu17a,
title = {Stochastic Convex Optimization: Faster Local Growth Implies Faster Global Convergence},
author = {Yi Xu and Qihang Lin and Tianbao Yang},
booktitle = {Proceedings of the 34th International Conference on Machine Learning},
pages = {3821--3830},
year = {2017},
editor = {Precup, Doina and Teh, Yee Whye},
volume = {70},
series = {Proceedings of Machine Learning Research},
month = {06--11 Aug},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v70/xu17a/xu17a.pdf},
url = {https://proceedings.mlr.press/v70/xu17a.html},
abstract = {In this paper, a new theory is developed for first-order stochastic convex optimization, showing that the global convergence rate is sufficiently quantified by a local growth rate of the objective function in a neighborhood of the optimal solutions. In particular, if the objective function $F(\mathbf{w})$ in the $\epsilon$-sublevel set grows as fast as $\|\mathbf{w} - \mathbf{w}_*\|_2^{1/\theta}$, where $\mathbf{w}_*$ represents the closest optimal solution to $\mathbf{w}$ and $\theta\in(0,1]$ quantifies the local growth rate, the iteration complexity of first-order stochastic optimization for achieving an $\epsilon$-optimal solution can be $\widetilde O(1/\epsilon^{2(1-\theta)})$, which is