General Tail Bounds for Non-Smooth Stochastic Mirror Descent

Khaled Eldowa, Andrea Paudice
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:3205-3213, 2024.

Abstract

In this paper, we provide novel tail bounds on the optimization error of Stochastic Mirror Descent for convex and Lipschitz objectives. Our analysis extends the existing tail bounds from the classical light-tailed Sub-Gaussian noise case to heavier-tailed noise regimes. We study the optimization error of the last iterate as well as the average of the iterates. We instantiate our results in two important cases: a class of noise with exponential tails and one with polynomial tails. A remarkable feature of our results is that they do not require an upper bound on the diameter of the domain. Finally, we support our theory with illustrative experiments that compare the behavior of the average of the iterates with that of the last iterate in heavy-tailed noise regimes.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-eldowa24a, title = {General Tail Bounds for Non-Smooth Stochastic Mirror Descent}, author = {Eldowa, Khaled and Paudice, Andrea}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {3205--3213}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/eldowa24a/eldowa24a.pdf}, url = {https://proceedings.mlr.press/v238/eldowa24a.html}, abstract = {In this paper, we provide novel tail bounds on the optimization error of Stochastic Mirror Descent for convex and Lipschitz objectives. Our analysis extends the existing tail bounds from the classical light-tailed Sub-Gaussian noise case to heavier-tailed noise regimes. We study the optimization error of the last iterate as well as the average of the iterates. We instantiate our results in two important cases: a class of noise with exponential tails and one with polynomial tails. A remarkable feature of our results is that they do not require an upper bound on the diameter of the domain. Finally, we support our theory with illustrative experiments that compare the behavior of the average of the iterates with that of the last iterate in heavy-tailed noise regimes.} }
Endnote
%0 Conference Paper %T General Tail Bounds for Non-Smooth Stochastic Mirror Descent %A Khaled Eldowa %A Andrea Paudice %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-eldowa24a %I PMLR %P 3205--3213 %U https://proceedings.mlr.press/v238/eldowa24a.html %V 238 %X In this paper, we provide novel tail bounds on the optimization error of Stochastic Mirror Descent for convex and Lipschitz objectives. Our analysis extends the existing tail bounds from the classical light-tailed Sub-Gaussian noise case to heavier-tailed noise regimes. We study the optimization error of the last iterate as well as the average of the iterates. We instantiate our results in two important cases: a class of noise with exponential tails and one with polynomial tails. A remarkable feature of our results is that they do not require an upper bound on the diameter of the domain. Finally, we support our theory with illustrative experiments that compare the behavior of the average of the iterates with that of the last iterate in heavy-tailed noise regimes.
APA
Eldowa, K. & Paudice, A.. (2024). General Tail Bounds for Non-Smooth Stochastic Mirror Descent. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:3205-3213 Available from https://proceedings.mlr.press/v238/eldowa24a.html.

Related Material