Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums

Kaiwen Zhou, Lai Tian, Anthony Man-Cho So, James Cheng
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:3684-3708, 2022.

Abstract

In convex optimization, the problem of finding near-stationary points has not been adequately studied yet, unlike other optimality measures such as the function value. Even in the deterministic case, the optimal method (OGM-G, due to Kim and Fessler (2021)) has just been discovered recently. In this work, we conduct a systematic study of algorithmic techniques for finding near-stationary points of convex finite-sums. Our main contributions are several algorithmic discoveries: (1) we discover a memory-saving variant of OGM-G based on the performance estimation problem approach (Drori and Teboulle, 2014); (2) we design a new accelerated SVRG variant that can simultaneously achieve fast rates for minimizing both the gradient norm and function value; (3) we propose an adaptively regularized accelerated SVRG variant, which does not require the knowledge of some unknown initial constants and achieves near-optimal complexities. We put an emphasis on the simplicity and practicality of the new schemes, which could facilitate future work.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-zhou22a, title = { Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums }, author = {Zhou, Kaiwen and Tian, Lai and Man-Cho So, Anthony and Cheng, James}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {3684--3708}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/zhou22a/zhou22a.pdf}, url = {https://proceedings.mlr.press/v151/zhou22a.html}, abstract = { In convex optimization, the problem of finding near-stationary points has not been adequately studied yet, unlike other optimality measures such as the function value. Even in the deterministic case, the optimal method (OGM-G, due to Kim and Fessler (2021)) has just been discovered recently. In this work, we conduct a systematic study of algorithmic techniques for finding near-stationary points of convex finite-sums. Our main contributions are several algorithmic discoveries: (1) we discover a memory-saving variant of OGM-G based on the performance estimation problem approach (Drori and Teboulle, 2014); (2) we design a new accelerated SVRG variant that can simultaneously achieve fast rates for minimizing both the gradient norm and function value; (3) we propose an adaptively regularized accelerated SVRG variant, which does not require the knowledge of some unknown initial constants and achieves near-optimal complexities. We put an emphasis on the simplicity and practicality of the new schemes, which could facilitate future work. } }
Endnote
%0 Conference Paper %T Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums %A Kaiwen Zhou %A Lai Tian %A Anthony Man-Cho So %A James Cheng %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-zhou22a %I PMLR %P 3684--3708 %U https://proceedings.mlr.press/v151/zhou22a.html %V 151 %X In convex optimization, the problem of finding near-stationary points has not been adequately studied yet, unlike other optimality measures such as the function value. Even in the deterministic case, the optimal method (OGM-G, due to Kim and Fessler (2021)) has just been discovered recently. In this work, we conduct a systematic study of algorithmic techniques for finding near-stationary points of convex finite-sums. Our main contributions are several algorithmic discoveries: (1) we discover a memory-saving variant of OGM-G based on the performance estimation problem approach (Drori and Teboulle, 2014); (2) we design a new accelerated SVRG variant that can simultaneously achieve fast rates for minimizing both the gradient norm and function value; (3) we propose an adaptively regularized accelerated SVRG variant, which does not require the knowledge of some unknown initial constants and achieves near-optimal complexities. We put an emphasis on the simplicity and practicality of the new schemes, which could facilitate future work.
APA
Zhou, K., Tian, L., Man-Cho So, A. & Cheng, J.. (2022). Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:3684-3708 Available from https://proceedings.mlr.press/v151/zhou22a.html.

Related Material