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

arXiv: https://arxiv.org/abs/2204.04970 · HTML: https://mlsanity.com/paper/2204.04970/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 16 references that are in the map.
- First posted on arXiv 11 Apr 2022.

## Builds on (most cited first, 5 of 5)

- [Non-parametric Models for Non-negative Functions](https://mlsanity.com/paper/2007.03926/) (2020)
- [Finding Global Minima via Kernel Approximations](https://mlsanity.com/paper/2012.11978/) (2020)
- [PSD Representations for Effective Probability Models](https://mlsanity.com/paper/2106.16116/) (2021)
- [A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation](https://mlsanity.com/paper/2101.05380/) (2021)
- [Infinite-Dimensional Sums-of-Squares for Optimal Control](https://mlsanity.com/paper/2110.07396/) (2021)

## Built on by (most cited first, 2 of 2)

- [Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation](https://mlsanity.com/paper/2303.03237/) (2023)
- [GloptiNets: Scalable Non-Convex Optimization with Certificates](https://mlsanity.com/paper/2306.14932/) (2023)

## Abstract (arXiv)

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.