Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares
This addresses optimization challenges in machine learning and applied mathematics, offering a method with theoretical guarantees for non-convex problems.
The paper tackles non-convex optimization by proposing an algorithm that achieves near-optimal computational guarantees and provides a posteriori certificates of optimality, with results demonstrated on minimizing multivariate periodic functions.
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.