Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity

Jingzhao Zhang, Hongzhou Lin, Subhro Das, Suvrit Sra, Ali Jadbabaie
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:26347-26361, 2022.

Abstract

We study oracle complexity of gradient based methods for stochastic approximation problems. Though in many settings optimal algorithms and tight lower bounds are known for such problems, these optimal algorithms do not achieve the best performance when used in practice. We address this theory-practice gap by focusing on instance-dependent complexity instead of worst case complexity. In particular, we first summarize known instance-dependent complexity results and categorize them into three levels. We identify the domination relation between different levels and propose a fourth instance-dependent bound that dominates existing ones. We then provide a sufficient condition according to which an adaptive algorithm with moment estimation can achieve the proposed bound without knowledge of noise levels. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation as it achieves improved instance complexity.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-zhang22r, title = {Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity}, author = {Zhang, Jingzhao and Lin, Hongzhou and Das, Subhro and Sra, Suvrit and Jadbabaie, Ali}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {26347--26361}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/zhang22r/zhang22r.pdf}, url = {https://proceedings.mlr.press/v162/zhang22r.html}, abstract = {We study oracle complexity of gradient based methods for stochastic approximation problems. Though in many settings optimal algorithms and tight lower bounds are known for such problems, these optimal algorithms do not achieve the best performance when used in practice. We address this theory-practice gap by focusing on instance-dependent complexity instead of worst case complexity. In particular, we first summarize known instance-dependent complexity results and categorize them into three levels. We identify the domination relation between different levels and propose a fourth instance-dependent bound that dominates existing ones. We then provide a sufficient condition according to which an adaptive algorithm with moment estimation can achieve the proposed bound without knowledge of noise levels. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation as it achieves improved instance complexity.} }
Endnote
%0 Conference Paper %T Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity %A Jingzhao Zhang %A Hongzhou Lin %A Subhro Das %A Suvrit Sra %A Ali Jadbabaie %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-zhang22r %I PMLR %P 26347--26361 %U https://proceedings.mlr.press/v162/zhang22r.html %V 162 %X We study oracle complexity of gradient based methods for stochastic approximation problems. Though in many settings optimal algorithms and tight lower bounds are known for such problems, these optimal algorithms do not achieve the best performance when used in practice. We address this theory-practice gap by focusing on instance-dependent complexity instead of worst case complexity. In particular, we first summarize known instance-dependent complexity results and categorize them into three levels. We identify the domination relation between different levels and propose a fourth instance-dependent bound that dominates existing ones. We then provide a sufficient condition according to which an adaptive algorithm with moment estimation can achieve the proposed bound without knowledge of noise levels. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation as it achieves improved instance complexity.
APA
Zhang, J., Lin, H., Das, S., Sra, S. & Jadbabaie, A.. (2022). Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:26347-26361 Available from https://proceedings.mlr.press/v162/zhang22r.html.

Related Material