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

Blake Woodworth (1) , Francis Bach (1) , Alessandro Rudi (1)

1 SIERRA - Statistical Machine Learning and Parsimony

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.

Domaines: Apprentissage [cs.LG]; Optimisation et contrôle [math.OC]

Blake Woodworth, Francis Bach, Alessandro Rudi. Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares. Conference on Learning Theory 2022, Jul 2022, London, United Kingdom. pp.4620-4642, ⟨10.48550/arXiv.2204.04970⟩. ⟨hal-03635236⟩