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

04/11/2022
by   Blake Woodworth, et al.
0

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 multivariate periodic functions.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset