Optimal Stochastic Strongly Convex Optimization with a Logarithmic Number of Projections

Jianhui Chen Yahoo, Tianbao Yang, Qihang Lin, Lijun Zhang Nanjing University, Yi Chang Yahoo!
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:475-484, 2016.

Abstract

We consider stochastic strongly convex optimization with a complex inequality constraint. This complex inequality constraint may lead to computationally expensive projections in algorithmic iterations of the stochastic gradient descent (SGD) methods. To reduce the computation costs pertaining to the projections, we propose an Epoch-Projection Stochastic Gradient Descent (Epro-SGD) method. The proposed Epro-SGD method consists of a sequence of epochs; it applies SGD to an augmented objective function at each iteration within the epoch, and then performs a projection at the end of each epoch. Given a strongly convex optimization and for a total number of $T$ iterations, Epro-SGD requires only $\log(T)$ projections, and meanwhile attains an optimal convergence rate of $O(1/T)$, both in expectation and with a high probability. To exploit the structure of the optimization problem, we propose a proximal variant of Epro-SGD, namely Epro-ORDA, based on the optimal regularized dual averaging method. We apply the proposed methods on real-world applications; the empirical results demonstrate the effectiveness of our methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-yahoo16a, title = {Optimal Stochastic Strongly Convex Optimization with a Logarithmic Number of Projections}, author = {Yahoo, Jianhui Chen and Yang, Tianbao and Lin, Qihang and University, Lijun Zhang Nanjing and Yahoo!, Yi Chang}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {475--484}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/yahoo16a/yahoo16a.pdf}, url = {https://proceedings.mlr.press/r14/yahoo16a.html}, abstract = {We consider stochastic strongly convex optimization with a complex inequality constraint. This complex inequality constraint may lead to computationally expensive projections in algorithmic iterations of the stochastic gradient descent (SGD) methods. To reduce the computation costs pertaining to the projections, we propose an Epoch-Projection Stochastic Gradient Descent (Epro-SGD) method. The proposed Epro-SGD method consists of a sequence of epochs; it applies SGD to an augmented objective function at each iteration within the epoch, and then performs a projection at the end of each epoch. Given a strongly convex optimization and for a total number of $T$ iterations, Epro-SGD requires only $\log(T)$ projections, and meanwhile attains an optimal convergence rate of $O(1/T)$, both in expectation and with a high probability. To exploit the structure of the optimization problem, we propose a proximal variant of Epro-SGD, namely Epro-ORDA, based on the optimal regularized dual averaging method. We apply the proposed methods on real-world applications; the empirical results demonstrate the effectiveness of our methods.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Optimal Stochastic Strongly Convex Optimization with a Logarithmic Number of Projections %A Jianhui Chen Yahoo %A Tianbao Yang %A Qihang Lin %A Lijun Zhang Nanjing University %A Yi Chang Yahoo! %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-yahoo16a %I PMLR %P 475--484 %U https://proceedings.mlr.press/r14/yahoo16a.html %V R14 %X We consider stochastic strongly convex optimization with a complex inequality constraint. This complex inequality constraint may lead to computationally expensive projections in algorithmic iterations of the stochastic gradient descent (SGD) methods. To reduce the computation costs pertaining to the projections, we propose an Epoch-Projection Stochastic Gradient Descent (Epro-SGD) method. The proposed Epro-SGD method consists of a sequence of epochs; it applies SGD to an augmented objective function at each iteration within the epoch, and then performs a projection at the end of each epoch. Given a strongly convex optimization and for a total number of $T$ iterations, Epro-SGD requires only $\log(T)$ projections, and meanwhile attains an optimal convergence rate of $O(1/T)$, both in expectation and with a high probability. To exploit the structure of the optimization problem, we propose a proximal variant of Epro-SGD, namely Epro-ORDA, based on the optimal regularized dual averaging method. We apply the proposed methods on real-world applications; the empirical results demonstrate the effectiveness of our methods. %Z Reissued by PMLR on 04 October 2026.
APA
Yahoo, J.C., Yang, T., Lin, Q., University, L.Z.N. & Yahoo!, Y.C.. (2016). Optimal Stochastic Strongly Convex Optimization with a Logarithmic Number of Projections. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:475-484 Available from https://proceedings.mlr.press/r14/yahoo16a.html. Reissued by PMLR on 04 October 2026.

Related Material