# Finding Global Minima via Kernel Approximations

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Dec 2020.

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

- [Information Theory with Kernel Methods](https://mlsanity.com/paper/2202.08545/) (2022)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [PSD Representations for Effective Probability Models](https://mlsanity.com/paper/2106.16116/) (2021)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation](https://mlsanity.com/paper/2303.03237/) (2023)
- [SOBER: Highly Parallel Bayesian Optimization and Bayesian Quadrature over Discrete and Mixed Spaces](https://mlsanity.com/paper/2301.11832/) (2023)
- [Adaptive Batch Sizes for Active Learning A Probabilistic Numerics Approach](https://mlsanity.com/paper/2306.05843/) (2023)
- [Handling Hard Affine SDP Shape Constraints in RKHSs](https://mlsanity.com/paper/2101.01519/) (2021)
- [Non-Parametric Learning of Stochastic Differential Equations with Non-asymptotic Fast Rates of Convergence](https://mlsanity.com/paper/2305.15557/) (2023)
- [Kernel Sum of Squares for Data Adapted Kernel Learning of Dynamical Systems from Data: A global optimization approach](https://mlsanity.com/paper/2408.06465/) (2024)
- [A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Lifting](https://mlsanity.com/paper/2404.12219/) (2024)
- [Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems](https://mlsanity.com/paper/2407.17200/) (2024)
- [Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares](https://mlsanity.com/paper/2204.04970/) (2022)
- [Approximation of optimization problems with constraints through kernel Sum-Of-Squares](https://mlsanity.com/paper/2301.06339/) (2023)
- [Stein Boltzmann Sampling: A Variational Approach for Global Optimization](https://mlsanity.com/paper/2402.04689/) (2024)
- [Estimating the Spectral Moments of the Kernel Integral Operator from Finite Sample Matrices](https://mlsanity.com/paper/2410.17998/) (2024)
- [Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models](https://mlsanity.com/paper/2303.17109/) (2023)
- [Scalable and adaptive prediction bands with kernel sum-of-squares](https://mlsanity.com/paper/2505.21039/) (2025)
- [Lifting Biomolecular Data Acquisition](https://mlsanity.com/paper/2512.15984/) (2025)
- [Nonparametric estimation of continuous DPPs with kernel methods](https://mlsanity.com/paper/2106.14210/) (2021)
- [Measuring dissimilarity with diffeomorphism invariance](https://mlsanity.com/paper/2202.05614/) (2022)
- [GloptiNets: Scalable Non-Convex Optimization with Certificates](https://mlsanity.com/paper/2306.14932/) (2023)
- [Distributionally Faithful Imputation via Positive Semi-Definite Kernel Density Estimation](https://mlsanity.com/paper/2607.07767/) (2026)

## Abstract (arXiv)

We consider the global minimization of smooth functions based solely on function evaluations. Algorithms that achieve the optimal number of function evaluations for a given precision level typically rely on explicitly constructing an approximation of the function which is then minimized with algorithms that have exponential running-time complexity. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum. This is done by using infinite sums of square smooth functions and has strong links with polynomial sum-of-squares hierarchies. Leveraging recent representation properties of reproducing kernel Hilbert spaces, the infinite-dimensional optimization problem can be solved by subsampling in time polynomial in the number of function evaluations, and with theoretical guarantees on the obtained minimum. Given n samples, the computational cost is O(n3.5) in time, O(n2) in space, and we achieve a convergence rate to the global optimum that is O(n-m/d + 1/2 + 3/d) where m is the degree of differentiability of the function and d the number of dimensions. The rate is nearly optimal in the case of Sobolev functions and more generally makes the proposed method particularly suitable for functions that have a large number of derivatives. Indeed, when m is in the order of d, the convergence rate to the global optimum does not suffer from the curse of dimensionality, which affects only the worst-case constants (that we track explicitly through the paper).