Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares

Blake Woodworth, Francis Bach, Alessandro Rudi
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:4620-4642, 2022.

Abstract

We consider potentially non-convex optimization problems, for which optimal rates of approximation depend on the dimension of the parameter space and the smoothness of the function to be optimized. In this paper, we propose an algorithm that achieves close to optimal a priori computational guarantees, while also providing a posteriori certificates of optimality. Our general formulation builds on infinite-dimensional sums-of-squares and Fourier analysis, and is instantiated on the minimization of periodic functions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-woodworth22a, title = {Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares}, author = {Woodworth, Blake and Bach, Francis and Rudi, Alessandro}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {4620--4642}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/woodworth22a/woodworth22a.pdf}, url = {https://proceedings.mlr.press/v178/woodworth22a.html}, abstract = {We consider potentially non-convex optimization problems, for which optimal rates of approximation depend on the dimension of the parameter space and the smoothness of the function to be optimized. In this paper, we propose an algorithm that achieves close to optimal a priori computational guarantees, while also providing a posteriori certificates of optimality. Our general formulation builds on infinite-dimensional sums-of-squares and Fourier analysis, and is instantiated on the minimization of periodic functions.} }
Endnote
%0 Conference Paper %T Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares %A Blake Woodworth %A Francis Bach %A Alessandro Rudi %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-woodworth22a %I PMLR %P 4620--4642 %U https://proceedings.mlr.press/v178/woodworth22a.html %V 178 %X We consider potentially non-convex optimization problems, for which optimal rates of approximation depend on the dimension of the parameter space and the smoothness of the function to be optimized. In this paper, we propose an algorithm that achieves close to optimal a priori computational guarantees, while also providing a posteriori certificates of optimality. Our general formulation builds on infinite-dimensional sums-of-squares and Fourier analysis, and is instantiated on the minimization of periodic functions.
APA
Woodworth, B., Bach, F. & Rudi, A.. (2022). Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:4620-4642 Available from https://proceedings.mlr.press/v178/woodworth22a.html.

Related Material