ICML 2022spotlight1 citations
Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity
Jingzhao Zhang, Hongzhou Lin, Subhro Das, Suvrit Sra, Ali Jadbabaie
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
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