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 d0. 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 d0 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