Accelerated Parameter-Free Stochastic Optimization

Itai Kreisler, Maor Ivgi, Oliver Hinder, Yair Carmon
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3257-3324, 2024.

Abstract

We propose a method that achieves near-optimal rates for \emph{smooth} stochastic convex optimization and requires essentially no prior knowledge of problem parameters. This improves on prior work which requires knowing at least the initial distance to optimality $d_0$. Our method, \textsc{U-DoG}, combines \textsc{UniXGrad} (Kavis et al., 2019) and \textsc{DoG} (Ivgi et al., 2023) with novel iterate stabilization techniques. It requires only loose bounds on $d_0$ and the noise magnitude, provides high probability guarantees under sub-Gaussian noise, and is also near-optimal in the non-smooth case. Our experiments show consistent, strong performance on convex problems and mixed results on neural network training.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-kreisler24a, title = {Accelerated Parameter-Free Stochastic Optimization}, author = {Kreisler, Itai and Ivgi, Maor and Hinder, Oliver and Carmon, Yair}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {3257--3324}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/kreisler24a/kreisler24a.pdf}, url = {https://proceedings.mlr.press/v247/kreisler24a.html}, abstract = {We propose a method that achieves near-optimal rates for \emph{smooth} stochastic convex optimization and requires essentially no prior knowledge of problem parameters. This improves on prior work which requires knowing at least the initial distance to optimality $d_0$. Our method, \textsc{U-DoG}, combines \textsc{UniXGrad} (Kavis et al., 2019) and \textsc{DoG} (Ivgi et al., 2023) with novel iterate stabilization techniques. It requires only loose bounds on $d_0$ and the noise magnitude, provides high probability guarantees under sub-Gaussian noise, and is also near-optimal in the non-smooth case. Our experiments show consistent, strong performance on convex problems and mixed results on neural network training.} }
Endnote
%0 Conference Paper %T Accelerated Parameter-Free Stochastic Optimization %A Itai Kreisler %A Maor Ivgi %A Oliver Hinder %A Yair Carmon %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-kreisler24a %I PMLR %P 3257--3324 %U https://proceedings.mlr.press/v247/kreisler24a.html %V 247 %X We propose a method that achieves near-optimal rates for \emph{smooth} stochastic convex optimization and requires essentially no prior knowledge of problem parameters. This improves on prior work which requires knowing at least the initial distance to optimality $d_0$. Our method, \textsc{U-DoG}, combines \textsc{UniXGrad} (Kavis et al., 2019) and \textsc{DoG} (Ivgi et al., 2023) with novel iterate stabilization techniques. It requires only loose bounds on $d_0$ and the noise magnitude, provides high probability guarantees under sub-Gaussian noise, and is also near-optimal in the non-smooth case. Our experiments show consistent, strong performance on convex problems and mixed results on neural network training.
APA
Kreisler, I., Ivgi, M., Hinder, O. & Carmon, Y.. (2024). Accelerated Parameter-Free Stochastic Optimization. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:3257-3324 Available from https://proceedings.mlr.press/v247/kreisler24a.html.

Related Material