Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares
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
Text
Woodworth et al. "Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares." Conference on Learning Theory, 2022.Markdown
[Woodworth et al. "Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares." Conference on Learning Theory, 2022.](https://mlanthology.org/colt/2022/woodworth2022colt-nonconvex/)BibTeX
@inproceedings{woodworth2022colt-nonconvex,
title = {{Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares}},
author = {Woodworth, Blake and Bach, Francis and Rudi, Alessandro},
booktitle = {Conference on Learning Theory},
year = {2022},
pages = {4620-4642},
volume = {178},
url = {https://mlanthology.org/colt/2022/woodworth2022colt-nonconvex/}
}