GloptiNets: Scalable Non-Convex Optimization with Certificates
Authors: Gaspard Beugnot
Julien Mairal
Alessandro Rudi
Venue: NeurIPS 2023 spotlight (2023)
Keywords: non-convex optimization
polynomial optimization
kernel sum-of-squares
TL;DR: Fast and scalable polynomial optimization on the torus with kernel sum-of-squares and overparametrized models

Abstract: We present a novel approach to non-convex optimization with certificates, which handles smooth functions on the hypercube or on the torus. Unlike traditional methods that rely on algebraic properties, our algorithm exploits the regularity of the target function intrinsic in the decay of its Fourier spectrum. By defining a tractable family of models, we allow {\em at the same time} to obtain precise certificates and to leverage the advanced and powerful computational techniques developed to optimize neural networks. In this way the scalability of our approach is naturally enhanced by parallel computing with GPUs. Our approach, when applied to the case of polynomials of moderate dimensions but with thousands of coefficients, outperforms the state-of-the-art optimization methods with certificates, as the ones based on Lasserre's hierarchy, addressing problems intractable for the competitors.

GloptiNets: Scalable Non-Convex Optimization with Certificates
Gaspard Beugnot
gaspard. beugnot@inria.
Inria, École normale supéricure, CNRS, PSL Research University, 75005 Paris, France
Julien Mairal
julien. Julien.mairal mwiraamilaaaalammm Cinria.fri
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France
Alessandro Rudi
al alessandro rudiiinnia.ff
Inria, École normale supérieure, CNRS, PSL Research University, 75005 Paris, France
Abstract
We present a novel approach to non-convex optimization with certificates, which handles smooth functions the hypercube methods that rely on algebraic properties, our algorithm exploits the regularity the target function intrinsic in the decay of its Fourier spectrum. By defining tractable family of models, we allow at the same time to obtain precise certificates and to leverage the advanced and powerful computational techniques developed optimize neural networks. In this way the scalability of our approach naturally enhanced by parallel computing with GPUs. Our approach, when applied the case of polynomials of moderate dimensions but with thousands of coefficients, outperforms the state-of-the-art optimization methods with certificates, as the ones based on Lasserre's 's hierarchy, addressing problems intractable for the competitors.
the torus. Unlike traditional
Introduction
Non-convex optimization is difficult and crucial task. this paper, we aim at optimizing globally non-convex function defined on the hypercube, by providing a certificate of optimality on the resulting solution. Let be a smooth function on [-1, 1]d. Here we provide an algorithm that given G. an estimate of the minimizer x. of ht
arg min h(x),
=E|-1,1]4
produces an e, that constitutes an explicit certificate for the quality of T, of the form
[}(x.)) - h())) S ca.
with probability 1- 8. The literature abounds of algorithms to optimize non-convex functions. Typi- cally they either (a) heuristics, very smart, but with guarantees of global convergence Moscato ct al. [1989]. Horst and Pardalos [2013] (b) variation of algorithms used in convex optimization. which can guarantee convergence only to local minima Boyd and Vandenberghe 2004 (c) algorithms with only asymptotic guarantees convergence to a global minimum, but no explicit certificates Van Laarhoven et al. [1887] In general, the methods recalled above quite fast to produce some
Moscaatoo
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

solution, but don't 't provide guarantees on its quality, with the result that the produced point can be arbitrarily far from the optimum, so they are used typically where non-reliable results can be accepted.
On the contrary, there are contexts where an explicit quantification of the incurred error is crucial for the task at hand (finance, engineering, scientific validation, safety-critccal scenarios Lasserre (2009). D. In these cases, more expensive methods that provide certificates are used, such as polynomial sum-of-squares (poly-SoS) Lasserre| 2001 2009]. These kinds of techniques are quite powerful since they provide certificates in the form above, olten with machine-precision error. However, (a) they have reduced upplicability since h must be a multivariate polynomial (possibly sparse, low-degree) and must be known in its analytical form (b) the resulting algorithm is a cemi-definite programming optimization on matrices whose size grows very fast with the number of variables and the degree of the polynomial, becoming intractable already in moderate dimensions and degrees.
Our approach builds and extends the more recent line of works kernel sum-of-squares, and in particular the work of WWoodworhh et al. 2022] based on the Fourier analysis. It mitigates the limitations of poly-SoS methods in both aspects: (a) we can deal with any function h (not necessarily a polynomial) for which the Fourier transform is known and (b) the resulting algorithm leverages
the smoothness properties of the objective function as Woodworth et al. [2022] rather than relying on its algebraic structure leading to way more compact representations than poly-SoS. Contrary to
Woodworth et al. 2022]. J. we fully leverage the power of the certificate allowing for a drastic reduction
of the computational cost of the method. Indeed. we cast the minimization in terms of way smaller problem, similar to the optimization of small neural network that, albeit again non-convex, produces efficiently a good candidate on which we then compute the certificate.
Notably, our focus lies on a posteriori guarantees: define family of models that allow for efficient computation of certificates. Once the model structure is established, we have ample flexibility in training the model, offering various possibilities achieve good certificates in practical scenarios, while still using well-established and effective techniques in the field of deep neural networks (DNN) Goodfellow et al. [016)] to reduce the computational burden of the approach.
Our contributions can be summarized as follows:
We propose a new approach to global optimization with certificates which drastically extends the applicability domain allowed by the state of the art, since it can be applied to any function for which we can compute the Fourier transform (not just polynomials).
The proposed approach naturally tailored for GPU computations and provides a refined control of time and memory requirements of the proposed algorithm, contrary to poly-SoS methods (whose complexity scales dramatically and in a rigid way with dimension and degree of the polynomial).
From technical viewpoint, we improve the results in Woodworth et al. [022]] by develop-
ing a fast stochastic approach to recover the certificate in high probability (theorem 33, and we generalize the formulation of the problem to allow the use of powerful techniques from DNN, still providing a certificate on the result (section 3 in particular alg. M
In practical applications, we are able to provide certificates for functions in moderate dimen- sions, which surpasses the capabilities of current tfth-offt techniques. Specifically, as shown in the experiments we can handle polynomials with thousands of coefficients. This achievement marks an important milestone towards utilizing these models to provide certificates for more challenging real-life problems.
1.1 Previous work
Polynomial SoS. In the field of certificate-based polynomial optimization, Lasserre's 's hicrarchy plays a pivotal role Lasserre [200]] 2009). This hierarchy employs sequence of SDP relaxations with increasing size proportional to (r")) (where d is the dimension of the space and is parameter that upper bounds the degree of the polynomial) and that ultimately converges to the optimal solution when r - co. While Lasserre's 's hierarchy is primarily associated with polynomial optimization, its applicability extends beyond this domain. It offers a specifie formulation for the more general moment problem, enabling a wide range of applications; see Henrion et al. (2020) for an introduction.
For polynomial optimization problems such as in eq. ([). a significant amount of research has been dedicated to leveraging problem structure to improve the scalability of the hicrarchy. This research

---

has predominantly focused on exploiting very specific sparsity patterns among the variables of the polynomial, enabling the handling in these restricted scenarios of instances ranging from a few variables to even thousands of variables Waki et al. (2006). Wang et al. 2021b al. There have been theoretical results regarding optimization on the hypercube Bach and Rudi 2023 Laurent and Slot [2022]. , but there are no algorithms handling them natively. Furthermore, alternative approaches exist that exploit different types of structure, such as the constant trace property Mai et al. [2022].
Kernel SoS. Kernel Sum of Squares (K-SoS) is an emerging research field that originated from the introduction of novel parametrization for positive functions in Marteau-Feree et al. [2020] This
approach has found application in various domains, including Optimal Control Berthier et al. [2022).
Optimal Transport Muzellec et al. [2021] and modeling probability distribution Rudi and Ciliberto
[02T]_ In the context of function optimization, two types of theoretical results have been explored:
priori guarantees Rudi et al. [2020] and a posteriori guarantees Woodworth al. [2022] A priori guarantees offer insights into the convergence rate towards a global optimum of the function, giving a rate on the number of parameters and the complexity necessary to optimize a function up to a given error. For example, |Rudi et al. (2020) proposes a general technique to achieve the global optimum, with error e of function that is 8-times differentiable, by requiring a number of parameters essentially in the order of O */d), allowing to avoid the curse of dimensionality in the rate, when the function is very regular, i.c., s 2 d. while typical black-box optimization algorithms have complexity that scales as e e-d A A-posteriori guarantees focus on providing a certificate for the minimum found by the algorithm. In particular, Woodworth et al. (2022). provides both a-priori guarantee and a- t-posteriori certificates; however, the model considered makes it computationally infeasible to provide certificates in dimension larger than 2.
To conclude, approaches based on kernel-SoS allow to extend the applicability of global optimization with certificates methods to a wider family of functions and on exploiting finer regularity properties beyond just the number of variables and the degrees of polynomial. By comparison, we focus on making the optimization amenable to high-performance GPU computation while retaining an a posteriori certificate of optimality.
2 Computing certificates with extended k-SoS
Without loss of generality (see next remark), with the goal of simplifying the analysis and using powerful tools from harmonic analysis, we cast the problem in terms of minimization of a periodic function f over the torus, [0, 1]d (we will denote it also as T In particular, we are interested in minimizing periodic functions for which we know (or can easily compute) the coefficients of its Fourier representation, i.e.
f. min f(2), =ET4
-(=)=- - Σ 2 E
WE24
where Z is the set of integers. This setting is already interesting its own, as it encompasses large class of smooth functions. It includes notably trigonometric polynomials, i.e. functions which have only finite number of non-zero Fourier coefficients fa. Optimization of trigonometric polynomials arises in multiple research areas, such as the optimal power flow Van Hentenryck [18] or quantum mechanics Hilling and Sudbery (2010). Note that this problem is already NP-hard, as it encompasses for instance the Max-Cut problem Waldspurger et al. (203). Even so, we will consider the more general case where we can evaluate function values of f. along with its Fourier coefficient fu, and we have access to its norm in certain Hilbert space. This norm can be computed numerically for trigonometric polynomials, and more generally reflects the regularity (degree of differentiability) of the function, and thus the difficulty of the problem.
Remark (No loss of generality in working on the torus). Given a (non-periodic) function h: 1-1, 1|d + R we can obtain a periodic function whose minimum is exactly h. and from which we can recover x.. Indeed, following the classical Chebychev construction, define cos(2 as the com- ponentwise application of cos to the elements of 2T, i.e. cos(2nz)= := (2os(221)))) .... cos (2 and define as f(z) == h(cos(2Tzz) for E [0, 1]d. It is immediate to see that (a) f is peri- odic, and, (b) since c2s(2 is invertible on [0, 1]a and its image is exactly [-1, 1]d, we have h. = h(x.) = (z,) where
I. = cos(2Tz2)) and 2. = min f(z).
zETU
3

---

We discuss efficient representation of these problems in section 3.3
2.1 Certificates for global optimization and k-SoS
A general "recipe" for obtaining a certificates was developed in Woodworth et al. 2022 where, in particular, it was derived the following bound [Woodworth et al. 2022, see Thmm
sup I- ر|و
(2)
C,RR gEG+
where |/ is the & norm of the Fourier coefficients a periodic function u, i.e.
|| :- Σ
Mwl
(3)
WEZ
and the sup is taken over G4 that is class of non-negative functions. The paper Woodworth et al. [2022] then chooses G4 to be the set of positive semidefinite models, leading to a possibly expensive convex SDP problem. Our approach instead starts from the following two observations: (a) the lower bound in eq. (2) holds for any set G+ of non-negative functions, not necessarily convex, moreover (b) any candidate solution (g, c) of the supremum in eq. (2) would constitute lower bound for f-, so there is no need to solve eq. (2 exactly. This yields the following theorem
Theorem 1. Given point 7 E T and non-negative and periodic function 9o : T - R.,, we have
If( - f(x)) S llf f(²) - gul
(4)
Proof. Since r, is the minimizer of then (axx) S fz).. Moreover, since co- f(3) and go are feasible solutions for the r.h.s. eq. (2). we have
f(3) 2 f(x,) cER, gE9+
sup c |lf c - g|lو 2 co |f cu- -9olF
from which we derive that 0 S ( (x.) $ |l f()) goll
In particular, since any good candidate go is enough to produce a certificate, we consider the following class of non-negative functions that can be seen fwo-layer neural network.
Definition 1 (extended K-SoS model on the torus). Let K T T > R be periodic function
the first variable and let m, r N. Given a set of anchors = (Z1....,2w)) C Tdd and a matrix R E Brxm, we define the K-SoS model with
E g(x) = |x)22xx)12, and Kz(x)
"())),,,,,,,,,,,,,,,,,,,,__,,_), Zm)) E ER..
(5)
The functions represented by the model above are non-negative and periodic. The model is an extension of the k-SoS model presented in Seateau--eeeyy et al. [2020), where the points (Z)...., 7m) cannot be optimized. Moreover has the tollowing benefits at the expense of the convexity in the parameters:
1. The extended k-SoS models benefit of the good approximation properties of k-SoS models described in Marteau-Ferey et al. (2020) and especially Rudi and Ciliberto| [202I). since they are super-set of the k-SoS, that have optimal approximation properties for non-negative functions.
2. The extended model can have a reduced number of parameters, by choosing a matrix R with = 1 or r < This will drastically improve the cost of the optimization, while not impacting the approximation properties of the model, since good approximation still possible with already proportional d Rudi al. 2020 see Thm. 3].
3. The extended model does not require any positive semidefinite constraint on the matrix (contrary the base model) that is typically well-known bottleneck scale up the optimization in the number of parameters Marteau-Feree et al. [2020). In the extended model we trade the positive semidefinite constraint with non-convexity. However this allows to use all the advanced and effective techniques we know for unconstrained (or box- constrained) non-convex optimization for (two-layers) neural networks Goodfellow et al. [2016].

---

To conclude the picture on the k-SoS models, a critical aspect of the model is the choice of K, since it must guarantee good approximation properties and at the same time we need to compute easily its Fourier coefficients since we need to evaluate | g|l F. To this aim, a good candidate for K are the reproducing kernely defined on the torus Steinwart and Christmann) 2008). We use shift-invariant kernels, enabling a convenient analysis of the associated RKHS through their Fourier Transform.
Definition (Reproducing kernel on the torus), Let q be a real function on Td,, with positive Fourier Transform and q(0) = 1. Let K be the kernel defined with
Vx, TV, K(r,y) q(x () v)
Σ WEZA
qwe (2eiiiii((e0))
(6)
Then, K is a rk bounded by 1. We denote H its Reproducing kernel Hilbert Space (RKHS) and by Il the associated RKHS norm
1f
Σ /
WEZ
Define ((x) = q(x)). We assume that we can compute (and sample from, see next section) Rua, i.e. the Fourier transform of X, corresponding (q * f)r-for all Zd
By choosing such a K, the models inherit the good approximation properties derived in Marteau Ferey al. 2020), Rudi and Ciliberto [2021). We conclude by recalling that shift-invariant r.k kernel have a positive Fourier translorm due to Bochner's 's theorem Rudin [1990]. The fact that is bounded by 1 can be with K (xx = (0()) En Tu 1. Finally, note that the Fourier coefficients of an extended k-SoS model can be computed exactly, as in shown e.g. later in lemma
2.2 Providing certificates with the F-norm
As discussed in the previous section our ap- proach for providing certificate on relies on first obtaining T using fast algorithm without guarantees and solving approximately eq. (2) to obtain the certificate (see theorem []. With this aim, now we need an efficient way to compute the norm ||.. We use here a stochastic ap- proach. Introducing a probability X (that later will be chosen as rescaled version of X. in definition 2
0.20
Lox norm
F-norm Our bound (Thm. 3)
0.15
0.10
0.05
0.00
N
103
10
10a
on 2d we rewrite the F-norm
Figure 1: f /- f. is trigonometric polynomial approximated by an extended k-SoS model g. The Loe norm of the difference (blue) is upper-bounded by the F-norm (red), which is itself upper bounded by the MoM inequality in theorem B] with probabil- ity 98%, here showed with respect to the number N of sampled frequencies. Shaded area shows min/max values across 10 estimations.
N X
Σ WEZ
=B B
(7)
which yields an objective that is amenable to stochastic optimization. From there, Woodworth cct al. [2022] computes a certificate by truncating the sum to hypercube (w: || N) of size
dd and bounding the remaining terms with smoothness assumption enables to control the decay of u... We want to avoid this cost exponential in the dimension so we proceed differently.
f g, which
Probabilistic estimates with the H norm. Given that the F-norm can be written as an expectation in eq. 77) we approximate it with an empirical mean S given with N i.i.d samples (wi) ~ X Now, note that the variance of Š can be upper bounded by Hilbert norm, as
1
Σ Muul
1 so that Var S < N
2
Tue 2
8 5= N Xo.
E
(8)
X
WE 7
with He the RKHS from definition with kernel K(x, = Eweze quantify the deviation of S from E[S] = ||u|| with e.g. Chebychev's inequality, as shown in next theorem.
2riiwww This allows to
5

---

Theorem 2 (Certificate with Chebychev Inequality). Let (Rw) w be a probability distribution on Z", 8 E (0.1) 1) and a positive function. Let N > O and S be the empirical mean of [ --wl/ Xo obtuined with N samples wi ~ Pu. Then, certificate with probability 1 is given with
N Pa.. --llw=- Dwc
fa f - ollas 3
1 N
VNO
Aus
Proof. From definition eq. 7 we see that an unbiased estimator of the F-norm is given by S. Then, Chebychev's inequality states that |s ||u|| 1 S Var S/5 with probability at least
Using the computation of the variance in eq. 8 it follows that || S $ + Il gllx, ns /
with probability at least 8. Plugging this expression into eq. 2 we obtain the result.
L
Note that the norm in Hy can be developed with (assuming for conciseness that (-c) is comprised in the O-frequency of f)
Po - 22g) + -19111A S (ll + 1191lxx) Au
(10)
WE24
Thus, theorem 2 provides a certificate of f. as long as we can (i) evaluate the Fourier transform Z. of and (ii) compute its Hilbert norm in some r.k Hy induced by o In next section, we detail the choice we make to achieve this efficiently, with kernels amenable to GPU computation, scaling to thousands of coefficients.
Remark 2 (Using RKHS norm instead of the F-norm). Note that since (Rw)s sums to 1, the associated kernel is bounded by Hence | < ||ul| and the latter could be used instead of the F -ooorm in eq. ( There
reasons for taking our approach instead. Firstly, the F F-norm is always tighter that a RKHS norm (see e.g. (Woodworth et al. 2022 Lem. 4]); secondly, we cannot compute ||u]| H. efficiently and have to rely instead another upper bound. However, taking the number of samples N = O(11ul12e)) alleviates this issue.
Exponential concentration bounds with MoM. The scaling in 1/Vō in theorem can be pro- hibitive if one requires high probability on the result (6 < 1). Hopefully, alternative estimator exist for those cases. The Median-of-Menn -f-Mean estimator is an example, illustrated in theorem 3
Theorem (Certificate with MoM estimator). Let (Rw) be a probability distribution on Zd, and 5 E (0, 1). Draw N > 0 frequencies wi Ru. Define the MoM estimator with the following: for K S.t. 8 = e K/8 and N = Kb. 6 2 1, write BI...,, Bx a partition of [N]; then
1P clw,=0 - Twel
MoMa((ūw.l/A..)) = median
(11)
Xu.
YEB;
ISiSK
A certificate on f. with probability follows, with
log(1/8)
f. 2 c MoM, 4v211f c alln,
(12)
N
Proof. Using e.g. Theorem 4.1 from Devroye al. [0166] get that the deviation of the MoM
estimator from the expectation is bounded by
(1g(1/)) N
|| MoMa C(... 1/>.,) & 2 Vaw
with proba. 1 1 8. (13)
Using the upper bound on the variance with the Hy norm given eq. expression into eq. (2), obtain the result.
( and plugging the resulting

---

To conclude this section, bounding the Lo norm from above with the F-norm in eq. (3) enables obtain a certificate on f. as shown theorem [ The F-norm requires an infinite number of computation in the general case, but can be bounded efficiently with probabilistic estimate, given by theorem 2 or theorem 3 This is summed up in fig. [ Note that the difference |I-II,- || II-1l is source of conservatism in the certificate which we do not quantify yet, the F-norm is optimal for class of norms, see Woodworth et al. 2022
Lemma 3].
Algorithm and implementation
3.1 Bessel kernel
We now detail the specific choice of kernel we make in order to compute the certificate theorem or theorem 3 efficiintly. Our first observation is to use kernel stable by product, so that we can easily characterize a Hilbert space the model belongs to. This restricts the choice to the exponential family. That's why define, for parameter O,
Vo E T, (x() = ((com((7m)
Σ E WEZ
(s)
2wi
(14)
with (-](() the modified Bessel function of the first kind [Watson 1922 p.181J. Then, define K2 (2,x, (xr y) as in definition 2 and take a tensor product to extend the definition of K to multiple dimension, i.e. yx TT= Ks (xe, for any x, E Td. We refer to this kernel as the Bessel kernel, and the associated RKHS as Hy. It is stable by product This is key to compute the Fourier transform of the model g. and in contrast to previous approaches which used the exponential kernel with Tw x -lw Woodworth et al. 2022 Bach and Rudi 22023
(z, y) K5/2(1, (I, 2)²
In the following, is a K-SoS model defined as in definition I with the Bessel kernel of parameter s E Rd defined eq. (14)
Lemma 1 (Fourier coefficient of the Bessel kernel), For u E Zd, the Fourier coefficient of g in w can be computed in (drm²² time with
m
Σ
R
R
II
e
| (28 n ((is - 2ze))e -iu
(15)
Proof. From its definition in eq.
5
we rewrite g as
d R II K2 K,,
g(x) = Σ R
(16)
8=1
have that for any (x, y, 2) E T. By definition of the modified Bessel function, the Fourier coefficient of this expression are given by [[] cos - 2)/2)). Using this into eq. 16 get the result.
Now, from the definition of the Bessel kernel in eq. 14 K(x, K (2, 2) e 2s cos =)/21 cos 2rr(= (v+
The second necessary ingredient for using the certificate of theorem 2 is computing RKHS norm for g. relies the inclusion of H2s into the bigger space of symmetric operator S(Ha). l[g] Hew is bounded by the Lemma 2 (Bound on the RKHS norm of g). belongs to H2s, and [|g]] Hilberr-Schmidt norm of ((H)), which can be computed in O + mr²) time, with
l P2. S [1 Tr TRK,,,. y²
(17)
Proof. Assume that d 1; the reasoning can be extended to multiple dimensions with the tensor product. From the computation the Fourier coefficient lemma I and the fact that Inl (2s coscccsssc (2T-)) < [2s), we have that &. = ((]]] (2s)) hence E Azg. Finally, since the kernel is stable by product, H2s H. @ Hes so we can use e.g. [Paulsen and Raghu
pathi 2016 Thm. 5.16]. with H4 He H. and S(H.) H. H. with the operator ((z.)) S(H.).
A (p((z) ....,
(((())))..,,,((m.)))) (Z
7

---

With lemma
we have that the model belongs to H2s so we will naturally use X IT= e (2s;) in theorem 2 said differently, the space Hy introduced in eq. (8) is simply
H2s defined in eq. 14).
3.2 The algorithm: GloptiNets
We can now describe how GloptiNeet yields certificate on f. The key observation is that matter how obtained our model g R, 2) from definition [ we will always be able to compute certificate with theorems 2 and Thus, even though optimizing eq. (9) w.r.t (c, R, z) is highly non-convex, we can use any optimization routine and check empirically its efficiency by looking at the certificate. Finally, thanks to its low-rank structure it is cheaper to evaluate g than evaluating its Fourier coefficient. This is formally shown in proposition appendix A where a block-diagonal structure for the model is also introduced. That's why we first optimize supa.9 |Iʃ where ||-Il_ a proxy for the Lox norm, e.g. the log log-sum-exp on a random batch of N points
|| c- gllz.. max EE[M]
[xx;)) c s(x:) ~ LSE(J - c g(x:))
(18)
This optimization be carried out by any deep learning libraries with automatic differentiation and any flavour of gradient ascent. Only afterwards do we compute the certificate with theorems 2 and This procedure summed up in alg.
Algorithm I: GloptiNets
Data: A trigonometric polynomial f. a candidate 2 s.t. c c= f(z), a model g. and probability d. Result: A certificate If. [2)1 S cs with proba. 1- 5.
** Optimize with function values
for epoch = 1:nepochs do
Sample 21, .1...., EN E T
I, V L = (LS()))((LSE(((()) c --------00 g(xx))
z, R optimizer(V1)) (LL):
Compute certificate
X: probability distribution on nd with Tu = II -25: I (28i);
Sample Q (Wi,...,, .N) Aw:
Compute M = MoMa(Ifan - -clw Dw.l // and ō = [|gll
Returns En = c- M - 4v20 ViV2oooogiin /og(1/61/N;
Remark 3 (Providing a candidate). In alg. 1 candidate estimate for the minimum value f(xx)) is necessary. However, it is possible to overcome this requirement by incorporating e as a learnable parameter within the training loop. Moreover, x. can be learned using techniques similar to those in Rudi et al. (2020]: : by replacing the lower bound e with a parabola centered at z, z becomes candidate for x, with precision corresponding to the tightness of the certificate. Note however that this method introduces additional hyperparaaeters.
3.3 Specific implementation for the Chebychev basis
As already observed in Bach and Rudi 2023) a result on trigonometric polynomial on T directly ex- tends to a real polynomials on [-1, 1 The reason for that is that minimizing h on [], amounts minimizing the trigonometric polynomial f = h((cos 2 cos 2Txz)) on T Note however that / is even function in all dimension, as for any approximating f- f- f. with a K-SoS model of definition i suboptimal, in the sense that we could approximate only on [0, 1/2]d, which is 2-d smaller. Put differently, the Fourier coefficient of are real by design: it would be convenient to enforce this structure in the model g. This is achieved with proposition
Td. f(x) = f(
Tay.... ..a) Thus,
Another detail of practical importance is that this loss can be efficiently backpropagated through; on the other hand, the certificate is not easily vectorized, and the Bessel function involved would require specific approximation to be efficiently backpropagated through.

---

Proposition 1 (Kernel defined on the Chebychev basis), Let q be real, even function on the torus, bounded by as in eq. (6). Let K be the kernel defined on [-1, by
1 (a(u + + (()--))..
V(u, v) E (0, 1/2,, K (cos 2Tu, cos 2TT)
(19)
Then K is a symmetric, p.d., hence reproducing kernel, bounded by with explicit feature map given by
V(z,g) [-1,1], 9) qo Σ (z)
(20)
WEN
The proof available in appendix B It simply relies on expanding the definition of K in eq. 19 The resulting expression in eq. (20) exhibits only cosine terms (in the decomposition of K (cos ZT y)). This enables to directly extend the PSD models from definition | with such kernels. Finally, when used with the Bessel kernel of eq. (14). we recover an easy computation of the Chebychev coefficient, as shown lemma in (ddrm²) time. This enables to approximate any function expressed the Chebychev basis. Note that polynomials expressed in other basis can be certified too, by first operating a change of basis.
Experiments
The code to reproduce these experiments is avail- able
Certificate
poly, |A| 1
github. cetbub..oom/aspparra/a wwtp://aaapparbbblggptielleeeeee jjl
poly, [A]
kernel, |/A|| 1
Settings. Given a function h, we compute candidate with gradient descent and multiple initializations. The goal is then to certify that f is indeed global minimizer of h. This common setup in the Polynomial-Son literature Wang and Magron 2022). J. To illustrate the influ- ence of the number of parameters, the positive model y defined in definition T for GloptiNets designates either small model GN-small with 1792 parameters, or a bigger model GN-big with 22528 parameters. The latter should have higher expressivity and better interpolate posi- tive functions, leading tighter certificates. All results for GloptiNets are obtained with confi- dence 1 - 5 = 1 e 2 98%. All other details regarding the experiments are reported in appendix C
kemnel, ||Al| 2
10-2
10a
10a
10a
# params
Figure 2: Certificate vs. number of parameters in g. for given function h. The higher the RKHS norm of h, the more difficult is to approximate uni- formly and the looser the certificate, independently of the function type. The more parameters in the k-SoS model, the tighter the certificates obtained with theorem
Polynomials. We first consider the case where is a random trigonometric polynomial. Note that this is restrictive analysis, as GloptiNets can handle any smooth functions (i.e. with infinite non-zero Fourier coefficients). Polynomials have various dimension d, degree p, number of coefficients n, but constant RKHS norm H211- We compare the performances of GloptiNets to TSSOS, in its complex polynomial variant Wang and Magron [2022]. The latter is used with parameters such that it executes the fastest, but without guarantees of convergence the global minimum f.. Table I shows the certificates h(xx) ) ( and the execution times (lower is better, in seconds) for TSSOS, GN-small and GN-big, Figure provides certificate random polynomial, function of the number of parameters in g.
Kernel mixtures. While polynomials provide ground for comparison with existing work, GloptiNets is not confined to this function class. This is evidenced by experiments on kerne mixtures, where our approach stands as the only viable alternative we are aware of. The function we certify are of the form h((x)) Σi= a (,,,,,, #),, where is the Bessel kernel eq. (14). Kernel mixtures are ubiquitous in machine learning and arise e.g. when performing kernel ridge regression. Certificates obtained on mixtures are compared with those obtained on polynomials in fig. function of the model size

---

Table 1: GloptiNets and TSSOS on random trigonometric polynomials. While TSSOS provides muchine-precissin certificates, its running time grows exponentially with the problem size, and eventually fails on problems 3 and On the other hand, GloptiNets has constant running time no matter the problem size, and its certificates can be tightened by increasing the model size.
TSSOS
GN-small
GN-big
d
p
Certif.
t
Certif.
t
Certif.
85
5.3
10-11
3
8.35
10-1
6 10
2.64
2.64-10-1
9 10
3
7
231
4.7 10-13
120
100 9.51
6. 10
2.90 10
9. 10
489
out of memory!
1.18 10-3
6- 10a
3.34 10-4
9. 10a
3
33
3.1-10
0.1
2.46
10-2
1 1.10*
3.45-10*
2 10*
4
225
4.8 10 10-12
53
3.71
1.10*
3.59- 10
2. 10
833
out of memory!
4.76-10-1
1 1.101
4.85 10-3
2 10a
Results. There are two key hindsight about the performances of GloptiNets. Firstly, its certificate does not depend on the structure of the function to optimize. Thus, although GloptiNets does not match the performances of TSSOS on small polynomials, it can tackle polynomials which cannot be handled by competitors, with arbitrarily as many coefficients (n = oo). For instance, TSSOS cannot handle problems with E {489, 833} in table More importantly, GloptiNets can certify richer class of functions than polynomials, among which kernel mixtures. The performances of GloptiNets mostly depends on the complexity of the function to certify, measured with its RKHS norm.
Secondly, note that bigger model yields tighler certificate. This is detailed in fig. 2 where the same function f is optimized with various models. The dependency of the certificate on the norm of f is shown in fig. appendix C along with experiments with Chebychev polynomials.
Limitations
One limitation of GlostiNets is the trade-off resulting from its high flexibility for obtaining certificate as alg- []] While this flexibility offers numerous advantages, also introduces the need for an extensive hyperparameter search. Although we have identified a set of hyperparameters that align with deep learning practices utilizing a Momentum optimizer with cosine decay and a large initial learning rate the optimal settings may vary depending the specific problem at hand.
In the same vein, the certificates given by GloptiNets are of moderate accuracy. While adding more parameters into the k-SoS model certainly helps (as shown in fig. 2 alternative optimization scheme interpolate h h()) with g might provide easier improvement. For instance, we found that using approximate second-order scheme in alg. iis key to obtaining good certificates.
In the specific settings of polynomial optimization, we highlight that our model is not competitive on problems which exhibits some algebraic structure, as for instance term sparsity or the constant trace property. Typically, problems with coefficients of low degrees (less or equal than 2), which encompass notably the OPF problem, are really well handled by the family of solvers TSSOS belongs to. Finally, GloptiNets does not handle constraints yet.
Conclusion
The GloptiNets algorithm presented in this work lays the foundation for a new family of solvers which provide certificates to non-convex problems. While our approach does not aim to replace the well-established Lasserre's 's hierarchy for sparse polynomials. it offers fresh perspective on tackling a new set of problems at scale. Through demonstrations on synthetic examples, we have showcased the potential of our approach. Further research directions include extensive parameter tuning obtain tighter certificates, with the possibility of leveraging second-order optimization schemes, along with warm-restart schemes for application which requires solving multiple similar problems sequentially.
10

---

Acknowledgments. AR acknowleges support of the French government under management of Agence Nationale de la Recherche as part of the "Investissemenns d' d'avenir" program, reference ANR- 19-P31A-0001 (PRAIRIE 31A Institute). AR acknowledges support of the European Research Council (grant REAL 947908). JM was supported by the ERC grant number 101087696 (APHE-LAIA project) and by ANR 31A MIAI @ Grenoble Alpe -AR-119-31A-00003)
References
Francis Bach and Alessandro Rudi. Exponential convergence of sum-of-squares hierarchies for trigonometric polynomials. SIAM Journal on Optimization, 33(3):2137-2159, 2023.
Eloise Berthier, Justin Carpentier, Alessandro Rudi, and Francis Bach. Dininit-DDieniinnall Sums- of-Squares for Optimal Control. In 2022 IEEE 6'st Conference on Decision and Control (CDC), pages 577-582, December 2022. doi: 10.1 0BCB9CCDDS11059222229999999
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Luc Devroye, Matthieu Lerasle, Gabor Lugosi, and Roberto I. Oliveira. Sub-Gaussian Mean Estimators. The Annals of Statistics, 2666)22695- 2016.
Dinh Dūng, Vladimir N. Temlyakov, and Tino Ullrich. urXiv:2211.04889 April 2017.
Hyperbolic Cross Approximation.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Didier Henrion, Milan Korda, and Bean-Beraard Lasserre. The Moment-SOS Hierarchy, volume 4 of Optimization and Its Applications. World Scientific Publishing Europe Ltd., December 2020. doi: 10.1 10.11422
Joseph J. Hilling and Anthony Sudbery. The geometric measure of multipartite entanglement and the singular values of a hypermatrix. Journal of Mathematical Physics, 51(7):072102, July 2010.
Reiner Horst and Panos M Pardalos. Handbook of global optimization, volume 2. Springer Science & Business Media, 2013.
Cédric Josz and Daniel K. Molzahn. Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables. SIAM Journal on Optimization, 2802):1017-1048, January 2018.
Jean B. Lasserre. Global Optimization with Polynomials and the Problem of Moments. SIAM Journal Optimization, 11(3):796-817, January 2001. doi: 10. 00.11377510522234003666880
Jean Bernard Lasserre. Moments, Positive Polynomials and Their Applications, volume of Series Optimization and Its Applications. October 2009. doi: 10. 10.1114.00 10.1112//665.
Monique Laurent and Lucas Slot. An effective version of schmüdgen's 's positivstellensatz for the hypercube. Optimization Letters, September 2022. doi: 10.1007/s 590-0022-0992---5
Ngoc Hoang Anh Mai, J. B. Lasserre, Victor Magron, and Jie Wang. Exploiting Constant Trace Property in Large-scale Polynomial Optimization. ACM Transactions Mathematical Software, 48(4):40:1-40:: December 2022.
Ulysse Marteau-Ferey, Francis Bach, and Alessandro Rudi. Non-parametric Models for Non-negative Functions. H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 128 12816-12826 Curran Associates, Inc., 2020.
Pablo Moscato et al. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech concurrent computation program, C3P Report, 826(1989):37, 1989.
Boris Muzellec, Adrien Vacher, Francis Bach, François-Xavier Vialard, and Alessandro Rudi. Near- optimal estimation of smooth transport maps with kernel of-s-of-square. (rXiv:2/12.01900) December 2021.
11

---

Vern I. Paulsen and Mrinal Raghupathi. An Introduction to the Theory of Reproducing Kernel Hilbert Spaces. Cambridge Studies Advanced Mathematics. Cambridge University Press, Cambridge, 2016. doi: 10.1017/CB00988111222222
Alessandro Rudi and Carlo Ciliberto. PSD Representations for Effective Probability Models. In Advances in Neural Information Processing Systems, volume 34, pages 19411-19422. Curran Associates, Inc., 2021.
Alessandro Rudi, Ulysse Marteau-Ferey, and Francis Bach. Finding Global Minima via Kernel Approximations. arXiv:2012. 19978, December 2020.
Walter Rudin. The Basic Theorems of Fourier Analysis. In Fourier Analysis on Groups, chapter 1, pages 1-34. John Wiley & Sons, Ltd, 1990. doi: 10.1002297811181656622
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science Business Media, 2008
Pascal Van Hentenryck. Machine Learning for Optimal Power Flows. INFORMS Tutorials in Operations Research, October 18.
Peter JM Van Laarhoven, Emile HL Aarts, Peter JM van Laarhoven, and Emile HL Aarts. Simulated annealing. Springer, 1987.
Hayato Waki, Sunyoung Kim, Masakazu Kojima, and Masakazu Muramatsu. Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity. SIAM Journal on Optimization, 17(1):218 242, January 2006. doi: 10. 13/05022000223.0..
Irène Waldspurger, Alexandre d' Aspremont, and Stéphane Mallat. Phase Recovery, MaxCut and Complex Semidefinite Programming, July 2013.
Jie Wang and Victor Magron. Exploiting Sparsity in Complex Polynomial Optimization. Journal of Optimization Theory and Applications, 192(():335-335 January 2022.
Jie Wang, Victor Magron, and Jean-Bernard Lasserre. Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension. SIAM Journal on Optimization, 31(1): 114-141, January 2021a. doi: 10.1 00.1137/00M3223564
Jie Wang, Victor Magron, and Jean-Bernard Lasserre. TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity. SIAM Journal on Optimization, 31(1):30-58 January 2021b. doi: 10.1137/19M1307771.
G. N. Watson. A Treatise the Theory of Bessel Functions. Cambridge University Press, 1922.
Blake Woodworth, Francis Bach, and Alessandro Rudi. Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares. In Proceedings of Thirty Fifth Conference on Learning Theory, pages 4642. PMLR, June 2022.
12

---

A
Extensions
We explore additional extensions of GloptiNets that further enhance its appeal. We first describe a block diagonal structure for the model for faster evaluation, a theoretical splitting scheme for optimization, and finally a warm-start scheme.
A.1 Block diagonal structure for efficient computation
Without any further assumption, we see that a model from definition | can be evaluated in O(drm) time; its Fourier coefficient given by lemma I in O(dmPr): the bound on the RKHS norm is computed
in (dm + mer² time thanks to lemma 2 all that enables to compute a certificate, as stated in theorem 2 in O(Ndm²r mr²) time, where N is the number of frequencies sampled. If the function to be minimized has big Hs norm, we might need large model size to have f f f+ g. Hence, we introduce specific structure on G which makes
diagonaa and better conditioned.
PSD model). Let g be a PSD model as in definition 7 with m = bs anchors. Split them into b groups, denoling them Zij. E [b] and j E [s). Compule the Cholesky factorization of each kernel matrix T: T, K2; E Raxx Then, define G as diocknda matrix, with blocks defined G, R,R,J. R. = T Rs and R₁ E &R Equivalently,
Proposition 2 (Block-diagone
R1 RT
G
s.t. g(x) Σ
R Kz (1)) (x) K K(zij, r)isis.-
(21)
Then g can be evaluated in O(rbs* d) time, Iw in (bss² (dr + s)) time, and I19l in Orb2(rs²+
r²)) + bs²) time. The model has (r + dibbs real parameters.
Proof. Having G defined as such, it is psd, of rank at most rb S sb = m. Written g(x)
Ea [. K2, (x))?, we can compute the Fourier coefficient by applying lemma 1 to each of the component. Adding the cost of computing G; RR results in complexity of Obss + s)). Finally, note that [|0l)s(H.) [| where
A = ((e(z))))ett)..... ................................ })({() ( (Diag G.)aej ((p(()))()) (p((z))))))..,()))))) )E((s))
Then, defining Q the matrix of x b blocks of size s.t. for j, k [b]. Q5a K(2j, (z) E Bexs, we have
|| ( = Tr Q(Diag Gi) Q(Diag (D Gi)ve(y- =
Σ 1.k=1
Tr G,Q
(22)
and each term in the sum can be written Tr 2, Ro, (T) 1R computed in O(rs² + r2s) time, plus (bs²²) to compute the Cholesky factor.
1 Q, R which is
Denoting Px; = -(((Zig) Isis. note that
P2, G = PT R.R (Po, 11 E.R.R E7
(23)
an orthonormal basis of Span( )isis as E, = I, Thus, each model's s coefficient is defined on an orthonormal basis, which makes the optimization easier. Of course, this comes at an added S complexity, which could be alleviated by using e.g. incomplete Cholesky factorization instead.
with E, = T T
Remark 4 (Relation Term Sparsity in POP). The successful application of polynomial hierarchies to problems with thousands of variables rely on making the moment matrix M having block structure Wang et af.) ( (202Tbla). If the monomial basis has size m, the constraint M Z replaced with M- (Diag Ma)aE and M; = 0. This enables to solve b SDP of size at most instead of one of size m. Our model in proposition follows a similar route for having a lower computational budget.
13

---

A.2 Global optimization with splitting scheme
While GloptiNets can provide certificates for functions, it falls behind local solvers in terms of competitiveness. The challenge lies in the fact that finding certificate is considerably more difficult than finding a local minimum, as it necessitates the uniform approximation of the entire function. However, we present novel algorithmic framework that has the potential to enhance the competi- tiveness of GloptiNets with local solvers while simultancously delivering certificates. Our approach involves partitioning the search domain into multiple regions and computing lower bounds for each partition. By discarding portions of the domain where we can certify that the function exceeds a certain threshold, the algorithm progressively simplifies the optimization problem and removes areas from consideration. Moreover, such an approach is naturally well suited to parallel computation.
The algorithm relies on a divide-and and-conquer mechanism. First, we split the hypercube (-1, 1)d in N regions, where N is the number of core available. We compute an upper bound with a local solver. For each region, we run GloptiNets in parallel, computing a certificate at regular interval. As soon as the certificate bigger than the upper bound, we stop the process: we know that the global minimum is not in the associated region. We can then reallocate the freed computing power by splitting the biggest current region, which yields an easier problem. We stop as soon as the region considered are small enough. This is summarized in alg. 2 where P indicates the loop run parallel.
Note that minimizing f on hypercube of center and size a amounts to minimizing x x f((x w)/o) on []1, which is another Chebychev polynomial whose coefficients can be evaluated efficiently thanks to the order-2 relation every orthonormal polynomial satisfy. For Chebychev polynomials, that is H (x) = (x) Hw-1(z).
Algorithm 2: Splitting scheme with GloptiNets
Data: A Chebychev polynomial f with unique global optimum, probability 6, number of cores N and a volume < 1/N.
Result: A certificate f: f. 2 C&(f) with proba. - 8.. /* Initialization: upper bound and partition
11 = 1 0;
P ub minæen (localsolver.e= Iterate over the partition
for ı E II, While length(II) > 1 do
while Cs(f+) < ub do
L Continue optimization;
Split biggest part: Ao arg max Vol(T); (2) partition(To. 2):
If ()) < p: end this process:
Update upper bound: ub = min {ub, localsllee.nen,/(())
Update search space and &, IT = IT\ mo) U [m,, T2). , 8x = - (11-)))1 - -8);
(2),T2))
/* A single region in π remains Returns II = (T), 8.;
A.3 Warm restarts
Our model distinguishes itself by leveraging the analytical properties of the objective function, rather than relying solely on algebraic characteristics. This approach offers a notable advantage, as closely related functions can naturally benefit from warm restart. For example, if we already have certificate for function ff using a PSD model g. and we seek to compute a certificate for a similar function f z f, we can readily employ GloptiNets by initializing the PSD model with g. Indeed, f- = g, we can expect f- = g. so we can expect the optimization to be faster.
In contrast, P-SoS methods, which rely on SDP programs, cannot directly adapt to new problems without significant effort. For instance, if a new component is introduced, an entirely new SDP must be solved. Our model's ability to accommodate related yet distinct problems could prove highly valuable in domains with a frequent need to certify different but closely related problems. In the industry, the Optimal Power Flow (OPF) problem requires periodic solves every 5 minutes
14

---

Van Hentenryck] (18), With GloptiNets, once the initial challenging solve is performed, subsequent solves become easier assuming minimal changes in supply and demand conditions.
A.4 Optimizing the certificate directly
As explained section 3.2 where GloptiNets is introduced, we optimize a proxy of the Los norm rather than the certificate of theorems 2 and This proxy is the log-sum-exp N points. The reason for this that evaluating an extended k-SoS model g(z) on x E T requires (ddrs) time, while evaluating 9e on w E zd requires (dds²² time. Yet, optimizing the certificate directly could probably help obtaining a method to reduce the computational cost of the Fourier computation from ((s²) to O(s).
random batch of
certificate. Lemma 4 in appendix sketches
B Kernel defined on the Chebychev basis
In this section we describe the approach we take to model functions written in the Chebychev basis. For such polynomial, a naive approach would simply model f cos(2 as trigonometric polynomial. However, note that the decomposition of only has cosine terms. Thus, approximating f- f. efficiently requires a PSD model which only cosine terms its Fourier decomposition. This is achieved by using kernel written in the Chebychev basis, introduce in proposition [ for which we now provide a proof.
Proof of proposition] 7 Let y E [-1.1] and u, E [0, 1/2] s.t. 2 cos(2 cos() by bijectivity of the cosine function on (0, T). From the definition of in eq. (19) and the definition of in eq. (6). we have that
Σ Iw (2miu(utt)) + 2niw(u-
K(x v) 2
WEZ
Σ
Twe 2niwn cos( (2Tww)
WEZ
90 + 2
Tu cos (2Twwr) cos( (2Twe)
WEN
= 90 + Σ T (w)
WEN
Since has positive Fourier transform, this makes the feature map of K explicit with K(x, v)
((u) p(v), p(u) ((1 + Lwza) Hu, for N. Hence the kernel is reproducing kernel.
We now use this kernel with the Bessel function (cco(((T=)) 1), i.e. we define the kernel K on [-1, 1] to satisfy
Vu, v E (0,)/2), ((cos(2Tu), cos(22u)) 1
( ((ccs((7((utt)) ((xos((7(xx))))
(24)
As it was the for the torus, this kernel enables easy characterization of RKHS in which associated PSD model g lives.
Lemma 3 (Chebychev coefficient of the Bessel kernel). Let g be PSD model in desinition with the kernel K of eq. (24p. Then, the Chebychev coefficient w E Nid of g can be computed in O(rdm²)
time with
d
-2c
9N
R
R
1 wxy) (1
In,, (2s Hu, (o+eis)
(25)
2
2
E=1
(2s:0 H (o-
where
O=tij = =o0m(27m4)))) m26i = (uei uer)/2, and cos 2T Zgis-
Proof.
15

---

Expanding and definition of Chebychev coefficient. have
From the definition of in eq. we
9(x)
Σ
R
R II 8=1
Ks, (x, 2 an)Ks, (xe: Ztz).
(26)
We consider y, E (-1,1) and 0. We denote u, v, w E (0, 1/2) s.t.
I; y cos 2 cos 2To cos 2
with the bijectivity x + cos (2T on (0, 1/2). We now compute the Chebychev coefficient of + K, (z, v) K 2). Denoted Pu. this is
Yo E, P= = + 1
[
da
K K, v) 2)
v1 x²
or equivalently
Ve N, Pa (1 + lwyo) /
Ka Ka(cos 2Tu cos 2TT) (atroKK(e (c 2TT cos 2mw) cos (20(wi)uddu. (27)
Chebychev coefficient of kernel product. With the definition of the kernel in proposition | eq. 199 we have
(2 (xx, (p(u + v) + p(u v)) x (p(u + w) + p(u - ww)
28
e (=cos2T(utt))
x ( ((()))
(c + con 2 (u
Now use the sum-te to- 00-produuct formula with the cosines to obtain
e c22 20
(2 v) (z,,2)
28 2a 2 (nt =
+ 28 2scos221 " cos 27 211)
4
t 20co (24=)) (10_2==)0002222 20 + 20cos 2a (=tz)) co 2
(28)
We simplify this expression by introducing
m+ = =/ (v + w) and a= cos 2mm
(29)
Then, eq.
28 hecomes
2s
250 nos 2n(u+m==) + 200 cos 20((mm4)4)
(30)
4
t 2004 cos 2m(umm-) + e 2504 cos cos
We recognize the definition of the kernel (which is not a surprise as we chose the kernel to be stable by product). However, need variables in (0, 1/2) to retrieve the proper definition of the kernel. Instead, we use lemma 5 on eq. (30) combined with eq. (27), to obtain
2*
Pa = (1 1 1ww
(4.
Mus
con(2mmumm) (2
which gives
20
Pa = (1 1w (m0m))
cos(22wmm (2s0
(31)
Equation 31 contains the Chebychev coefficient of the product of two kernel function defined
eq. 27 P Plugging this result into the definition y in eq. (26). and noting that cos (2mwm.))
(cos 2 = (.) we obtain the result.
16

---

10-1.2
Certificate
10-1.5
20
109
3
2
Figure 3: Certificate vs. RKHS norm of f. for given model with a fixed number of parameters, f has 1146 coefficients and g has 22528 parameters. Best certificate kept among set of optimization hyperparameters. As the norm of decreases, fitting f f. with is easier and the certificate becomes tighter.
Thanks to lemma 3] we see that a model g defined as in definition I with the Bessel kernel K₃ of eq. (24) as its Chebychev coefficients decaying in O(T (2s)). Hence, it belongs to H2s, the RKHS associated K2s-
C Additional details on the experiments
Tuning the hyperparameters. The time reported in section does not take into account the experiments needed to find good set of hyperparameters. The parameters tuned were the type of optimizer, the decay of learning rate, and the regularization on the Frobenius norm of
Regularization. Regularization is performed by approximating the HS norm with proxy which faster compute. We use RR R& Hs instead of || R2J Ru in eq. 22
Hardware. GloptiNets was used with NVIDIA V100 GPUs for the interpolation part, and Intel Xeon CPU E5-2698 v4 @ 2.20GHz for computing the certificate. TSSOS was run on Apple M1 chip with Mosek solver.
We use the lowest possible relaxation order (i.e. [deg f/2)). along with Chordal sparsity. We use the first relaxation step of the hierarchy. In these settings, TSSOS is not guaranteed to converge to but will executes the fastest.
Configuration of TSSOS.
Certificate vs. number of parameter for given function. In fig. 2 the target function is random polynomial of norm or 2, or kernel mixture with 10 coefficients of norm 1 or 2. The models forming the blue line are defined as proposition ] with rank, block size and number of blocks equal to (1, bs, 1) respectively, with bs the block size we vary. The number of frequencies sampled to compute the certificate is 1.6 107, and accounts for the fact that the bound on the variance becomes larger than the MOM estimator for large models.
Certificate vs. problem difficulty for a given model. We have 3 related parameters: the quality of the optimization (given by the certificate), the expressivity of the model (given by its number of parameters), and the difficulty of the optimization (given by the norm of the function). In fig. 3 we fix the latter and plot the relation between the first two. Here, we fix the model with parameters (8, 16, 128), and we optimize polynomial in 3d of degree 12, with RKHS norm ranging from 1 to 20. The certificates obtained are given fig. 3 The resulting plot exhibits clear polynomial relation between the certificate and the norm of the function, with a slope of -0.88. This suggest that the certificate behaves II
Comparison with TSSOS on the Fourier basis. In table 1 the polynomials f all have RKHS norm of The small model defined in proposition 2 with rank, block size and number of blocks equal to 4, 32, 8 respectively. For the big models, those values 8, 128, 16. The certificate is the
17

---

Table 2: GloptiNets and TSSOS on random Chebychev polynomials. The same conclusion in table applies.. While TSSOS is very efficient on small problems, its memory requirements grow exponentially with the problem size. GloptiNets has less accuracy, but a computational burden which does not increase with the problem size.
TSSOS
GN-small
GN-big
p
Certif.
t
Certif.
Certif.
t
3
255
3.4 10-7
6
1.1 10-2
2 102
4.1 10-3
1 103
4
624
2.1 10
153
2.5
10-2
2. 102
3.6 10-3
1-
5
1295
Out of memory!
1.8 10
2 10
4.2 10
2 1-
maximum of the Chebychev bound of theorem 2 and the MoM bound of theorem frequencies sampled is 3.2 10".
3 The number of
Comparison with TSSOS on the Chebychev basis. We compare GloptiNets with TSSOS on ran- dom Chebychev polynomials in table similarly the comparison with trigonometric polynomials in table Minimizing polynomials defined on the canonical basis is easier: contrary to trigonometric polynomials, there is need to account for the imaginary part of the variable. If is the dimension, complex polynomials are encoded in a variable dimension 2d TSSOS, following the definition of Hermitian Hum-of-Squaree introduced in Josz and Molzahn (2018). Hence, the random polynomials we consider are characterized by the dimension d and their number of coefficients nı instead of bounding the degree, we use all the basis elements (x) I Hu,, (xe) for which ||w|| S p. The maximum degree is then dp. The RKHS norm of f is fixed to As with the comparison on Trigonometric polynomial table 1 see that GloptiNets provides similar certificates no matter the number of coefficients in f. Even though it lags behind TSSOS for small polynomials, handles large polynomials which are intractable to TSSOS. The "small" and "big" models have the same structure as for the trigonometric polynomials experiments.
Sampling from the Bessel distribution. The function + (s) decays rapidly. In fact, with 2, which is the value used to generate the random polynomials, it falls under machine precision soon as 14. Thus, approximate the distribution with a discrete w s.t. the result above the machine precision. We then extend it to multiple dimension with a tensor product. Finally, use a hash table to store the already sampled frequency, to make the evaluation of million of frequencies much faster. For instance in dimension 5, sampling 10 frequencies from on No yields only ss 10* unique frequencies. This allows
with weights (s) for
the Bessel distribution of parameter for tighter certificates, as it makes the r.h.s of eq. 9 in I/N, much smaller. Note that the time to reported in tables I and 2 and of the order of a few seconds.
generate this hash table
Optimizing a kernel mixture. As it is the case with polynomials, when optimizing a function of the form (xx)= = Ei a,K(,,, (x;, the certificate provided by GloptiNets only depends on the function norm || and not on e.g. the number of coefficients n. This is illustrated in fig.
D Fourier coefficients in linear time
Lemma 4 (Fourier coefficient of the Bessel kernel in linear time). Let g be extended k-Soš model as in definition] 7 Then, its Fourier transform can evaluated linear time in m. with
Φt. (zie) )
R II E=1
Rai
II
De, (Zie)
(32)
k= negd
where
Vn E Z E [d], (2) = Vin. " wi(n=we)
and (s) is defined with lemma
Lemma provides a formula for computing P. which linear in m, but which still requires numerical approximation to compute the n E 2d, For instance, restraining the sum to the hyperbolic
18

---

| = 1, n 10
100
|| 1,
|| 2. 10
Certificate
|| 2. n 100
10-1
10-2
# params
10
10a
10
Figure 4: Certificate vs. number of parameters in when certifying mixture of Bessel functions, characterized by their RKHS norm (1 in blue, red) and their number of coefficients (10 in circles, 100 in rectangles). As with polynomials, this shows that GloptiNets is only sensible to the former, and not to the way the function is represented. We are not aware of other algorithms able to certify this class of functions.
cross Düng et al. 2017
d HC(d, = E zd: II max f1, [ell s
would result in a complexity of O(n(log mr) and should produce reasonably accurate estimate of Iw for low π.
Furthermore, since g is real-even w.r. n, the inner-product in eq. (36) can be simplified by computing only half of the terms.
Proof. From lemma I we have that
d
g-e
R
25c T [wee cos 2zz))e im (mslleet
(33)
+==1
t=1
Introducing
Se(2, v)
28: |wel (28; COS (xx m))e -imws
(34)
eq. 333
simplifies to
J- R
R3 II E=1
(35)
(-==
Using l for any v, T.
2 231 [wel (2sg cos π(x v))
Σ nez
qt min(z-g)
(qe, depends on wi) so that, fr defined in eq. 34 now writes
fe(x,
Σ
e Tin(x- v) riwr(rt))
nEZ
Σ ne mi(n wi)x - -xilntwrly nEZ
dz (x) de (2)
(36)
where, for any é {l,..., d} and 2 T, we defined
Hr (=)
(37)
nEZ
19

---

We then define the embedding @+ T + (Z² enables to write IN in eq. (35 as
C) be the tensor product of the 0e.= Then, eq. 36
Bw
RIi Rkj (z;)) (4)))+((2)) (zz)
y
m
REc (zi)
Σ
R (zi)
m
m
R (2:1) 8 ... 2 Od.- (2rd)
R (2.1) 8 ... @ od.+ (Zra)
d II (=1
R
Φz, (zie)
RR
Il t=1
Φ (Zie)
k= nedd
Am
which is the desired result.
E
Other computation
Lemma 5. Let f be the function defined on (-1,1) with
Vu E (0, 1/2), f(cos 2TT) = e. cos 2x((mm))
(38)
Then, its Chebychev coefficient are given with
fw (1 + lw=eo cos (2TwT) (s).
(39)
Proof. The w E N.. The component of function f on the Chebychev basis is given with
Jw 2 [" (x))
dr V1-12 x2
which we conveniently rewrite, with the classical change of variable x = cos 2T
fw 2== fcoo 2mu) cos(2nuu)ddr
(40)
which is valid for any interval I C IR of length
Now, for O, consider the function f defined (-1,1) with + e cos(prccoo(x)-22r)) equivalently
Vu E (0, 1/2), f(cos 2mr) = e cos 2x((=v))
(41)
Putting into eq. 440 we obtain
La cos (u cos(2nwuidk
2 cos cos (2 (u + v))
2 cos cos cos((2 (2TTu) cos (2nwe)du 2 2o02xK 2xu sin(2mwu) sin(2rwe))d.
The last term is odd, hence integrate to 0 on an interval centered around Hence,
fo = 2 cos(2mww))
e ccce2xu 2xu cos(2nwuuddu.
(42)
We recognize the definition of the modified Bessel function of the first kind, defined in eq. Plugging this into eq. (42). we obtain
14)
for
cos cos(22mwu)LL. Hs,
(43)
w = 0, we add a factor 1/2 into the definition in eq. (40). which yields
fa lo(s).
(44)
20

---

Lemma 6 (Fourier decomposition of Bessel composed with cosine). Lets > 0, E N and 2 E T. Then,
22 (2s cos 2TT E
e
2xins
nEZ
where Vn 2 0, qw
e 28
121
(a/2)ar 2ptw plptwy
(p- -
n
(45)
otherwise.
and qw,-n = qwnn by evenness of the coefficients.
Proof. From the definition of the modified Bessel function of the first kind 21, we have
[Watson 1922 p.77, Eq.
Iu(z) = Σ (2/2) 2ptw
pl + w)!
p20
so that
pppt
I (2s cos 2x²)
cos(2 2ptw
pl(p + w)!
(s/2)2ptu
Σ
(c c 20iz
e-2ria 2 2p-w
pl(p + ww)!
p20
Σ (8/2)2pt> 2ptw Σ
(pp 12p+ar + w
(46)
p!(p + w)!
k
P20
h=0
Using the change of variable n = 2(p k) into eq.
(46). we see that has same parity as w
and
Σ (8/2) 2pt
2p+tw
2p
I (2s cos 2TT2
2ning
(47)
pl (w w))
p
n-
r20
(3p-w)
2
new
Equation
47 can be rewritten
(s/2)2ptw
2p + w
L (2s cos 2Tz)
2min=
1 1- (2ptt)
p1 + ww)!
p -
nEZ
p2u
for which eq.
455 concise rewriting.
21


Reviews:
[{"review_id": "WpmkR5PHj2", "reviewer": "Reviewer_rug7", "summary": "They present a novel approach to non-convex optimization with certificates, which handles smooth functions on the hypercube or on the torus. Unlike traditional methods that rely on algebraic properties, our algorithm exploits the regularity of the target function intrinsic in the decay of its Fourier spectrum. ", "questions": "No.", "limitations": "No.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clearly written and the theory is interesting.", "weaknesses": "The experimental results are not abundant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We direct the reviewer's attention to the new experiments presented in the collective response to all reviewers. Should they have any additional concerns or questions, we would be happy to discuss them further."}, {"review_id": "NcnRTPsJed", "reviewer": "Reviewer_Sbjx", "summary": "This paper develops an approach to compute certificates for non-convex optimization on functions that are optimized over the hypercube or torus. It does so by considering the generic certificate recipe from [7] and then relaxing the positive semi-definite constraint to a class of functions that is easier to optimize that they denote K-SoS. This class of functions depends on the choice of a kernel K, of which they explore different alternatives. The authors consider optimization aspects of this general framework and provide a concrete algorithm that they name GloptiNets. They also provide experiments comparing the tightness of the certificate across the number of parameters and related approaches.", "questions": "1. What is Z_d in eq. (1)? I don't think it has been defined before.\n\n2. It was not clear to me whether the anchor points Z are given by the problem or are part of the choice of the kernel family. Clarification would be appreciated.\n\n", "limitations": "I believe the limitations have been correctly addressed by the author in the Limitations section.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is clear and beautifully written. It is a pleasure to read.\n\n2. Results are sound to the best of my knowledge. The theoretical derivations are clear and give the proper references to understand which steps have been taken.\n\n3. The authors consider all relevant aspects of the implement of this framework: from expressiveness properties of the function approximation, to probabilistic estimates of the certificate, to practical implementation details.", "weaknesses": "\nNo major weaknesses identified. Below are some minor suggestions that I hope the authors consider, but should not be taken as criticism towards the work.\n\n\n## Minor suggestions\n\n1. Add x and y labels to Figure 1.\n2. Some aspects of this paper, such as the lower bound formula (2) or the anchor points Z are introduced assuming the reader knows about the related works. I would encourage the authors to aim for a larger audience. In particular, a few words about the intuition can go a long way towards making the work more accessible.\n\n## Typos \n\nL244: eventhough -> even though\nL245 optimisation -> optimization (since American spelling is used elsewhere)\nL93: \"we focus on the computational performances of our model\" it's unclear what the authors mean here by computational performances, is it run-time? tightness of the certificate? the trade-off between these two? Please make precise", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank this reviewer for the kind and encouraging feedback! \n\nAs you suggest, we will use additional space to provide additional assumption on the derivation of the certificate in Eq. (2). Typically, it relies on the relation \n$$\nf_\\star = \\sup_c c ~~ \\text{ s.t. } ~~ f - c \\geq 0 ~~~~~~~~ \\text{(A)}\n$$\nwhich is a convex problem, albeit with a dense set of constraint. From there, a penalized version of $(A)$ is given with \n$$\nf_\\star = \\sup_{c, g \\geq 0} c - \\lVert f - c - g \\rVert_\\infty ~~~~~ (B)\n$$\nintroduced in [1], which is still untractable (this actually highlights the fact that approximating $f$ is as hard as finding $f_\\star$) but provides a general recipe for computing certificates, by taking any family of positive function $g$ (here, kernel-SoS models), and any surrogate for the $L_\\infty$ norm (here, the F-norm). This yields Eq. $(2)$ in the paper. Adding an efficient way to evaluate it (as the $F$-norm is an infinite sum) and optimize it is the gist of our contribution. \n\n## Questions\n\n$\\mathbb{Z}$ is the set of integers, which was indeed not introduced before. \n\nOur positive function class are functions of the form $x \\mapsto {\\bf v}(x)^\\top G {\\bf v}(x)$, with $G \\succeq 0$ and ${\\bf v}(x) = (v_i(x))_{1 \\leq i \\leq n}$. We realized that optimizing the embedding ${\\bf v}$ is beneficial for the certificate; that is why we take ${\\bf v}$ of the form $v_i(x) = K(z_i, x)$. The setup we tried is $K$ set to the Bessel kernel (l. 217 or Eq. $(14)$) and $z_i \\in \\mathbb{T}^d$ the anchor point tuned during the optimization. In a kernel-learning vocabulary, this is learning the anchor points of a Nyström projection.\n\n\n[1] Blake Woodworth, Francis Bach, and Alessandro Rudi. Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares. In Proceedings of Thirty Fifth Conference on Learning Theory, pages 4620–4642. PMLR, June 2022."}, {"review_id": "zSa5OsSwBC", "reviewer": "Reviewer_RR26", "summary": "This paper introduces a method for certain non-convex optimization problems on a hypercube or torus (i.e. with periodic boundary conditions), which also provides a certificate (a measure of how close the fitted function is to the target). \nAs I understand it, the certificate computation utilizes the Fourier basis. \nThey do two sets of experiments using their model GloptiNet: one on random trigonometric and one on Chebyschev polynomials, with increasing number of coefficients. They compare their method's performance against an existing polynomial solver, TSSOS. Their model's certificates are orders of magnitude less tight (~$10^{-2}$) than TSSOS ($10^{-12}$). But their model has the benefit that it takes almost constant time, independent of the complexity of the polynomial, to get within the certificate's accuracy. They also show that the certificate gets tighter as they increase the number of model parameters, though the drop seems slower than linear.     \n", "questions": "1. currently the certificate seems very loose at $O(10^{-2})$. Is this a good number? \n2. How much does hyperparameter tuning (other than model size) affect the certificate? Is there hope for much better values, or does it need dramatic changes?   \n3. Experiments: How would the model perform on polynomials from a dramatically different basis from the Fourier basis (e.g. $x^p$)? I understand this doesn't work on the Torus (no periodicity), but does the hypercube have a similar limitation (meaning you *have to* use the Chebyshev basis due to boundary conditions)?\n4. Baseline methods seem very limited. Is TSSOS the only viable alternative? \n5. In Fig 2, no red curve is presented, but mentioned in the caption. \n", "limitations": "They discuss the limitations. I would also add discussions about the class of polynomials, if it is currently limited to Chebyshev and trigonometric polynomials. As for societal impact, I don't see any issues, as this is a purely mathematical optimization paper.  ", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper gives a detailed exposition of the derivation of the certificate and discusses existing work extensively. I am no expert in this field, but I could more or less follow the process. \nThe contribution of the work, in addition to providing a certificate, seems to lie in its efficiency. They claim it should work well in higher dimensions, too, and the run time seems to be not affected much by the complexity of the target function. \nAlso, being able to use fast stochastic optimizations of DNN while still providing a certificate for the fit seems to be another benefit of the method. \nSince I am not familiar with this branch of optimization, I cannot assess the novelty that much. \n", "weaknesses": "A big emphasis is on the derivation of the certificate. While I appreciate the details, it makes it difficult to follow the flow of the paper. Instead a little more details on how the extended k-SoS model is implemented and how the optimization is done would be useful. I see discussions of the details in the appendix, but it is brushed over in the main text. For example, is the R matrix optimized, or fixed? \nAlso, the high value of the certificate and lack of hyperparameter tuning, except model size, weakens the paper (see questions). \n\nAdditionally, the target function in the two experiment, trigonometric and Chebyshev, are both related to the Fourier series, which is used in computing the certificate. I wonder how well the model performs on other polynomials with other bases (see questions).\n   ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Quality of the certificate\n\nWe refer the reviewer to the common response on that aspect. \n\n## Implementation details\n\nWe would be happy to include implementation details in the main text, as a lot of attention was dedicated to having a structure which can scale to thousands of parameters. \n\nFor the optimization, we used gradient descent with momentum and a cosine scheduler. This was the most classical configuration we found in the DL literature. We performed the  hyperparameter search on the type of regularization (proxy for the variance or not), the value of the regularization and the learning rate. \n\nFinally, to answer precisely to your question, both the coefficients $R$ and the anchor points $\\mathbf{z}$ are optimized during the training (`for` loop in Algorithm 1). \n\n## Other polynomial basis \n\nSimply put, for polynomial optimization there are no limitations on the basis. Indeed, if the polynomial $h$ is given in another real (resp. complex) basis, we can first perform a change of basis to the Chebychev (resp. Fourier) basis, which is a linear operation. The resulting polynomial would  be handled natively by GloptiNets. More than that, the algorithm applies to the minimization of any function defined on a hypercube $C = [a_i, b_i]_{1 \\leq i \\leq n}$, for which we have access to the Fourier/Chebychev coefficients.  \n\nHere is a more detailed response:\n\n**Hypercube constraints.**\nGiven a function $\\tilde{h}$, what the algorithm requires is a set of constraints $C = [a_i, b_i]_{1 \\leq i \\leq n}$ to localize the minimum. Lassere's polynomial hierarchies do not necessarily need such constraint, but have much better convergence guarantees under similar constraints. For instance, this happens if $\\lVert x \\rVert^2 \\leq R$ is in the constraint set, which is called the \"Archimedean property\"  – this is encompassed in the hypercube constraint $C$ we consider. Thus, let's assume we minimize $h(x) = \\tilde{h}(a_i + (x - a_i) / (b_i - a_i))$ for $x \\in [0, 1]^d$. \n\n**No loss of generality with periodic functions**.\nNow, define $f(x) = h(\\cos(2\\pi u))$. This is a $1$-periodic function, **whose minimum is the same as $h$**. This is detailed in Remark 1, l. 109. This shows that working with trigonometric polynomials is done with no loss of generality. \n\n**Better implementation with the Chebychev basis.**\nOne caveat on the transformation $f(x) = h(\\cos(2\\pi u))$ is that $f$ is an even function in all dimensions: GloptiNets with Fourier series would minimize $f$ on $(0, 1)^d$ whereas looking at $(0, ½)^d$ would be sufficient! Hopefully, we can overcome this bad dependency with the dimension by working directly with Chebychev series. They form an orthonormal basis of (non-periodic) functions defined on $(-1, 1)$. Assume we have access to the coefficients of $h$ on this basis, i.e. $h(x) = \\sum h_\\omega T_\\omega(x)$ where $T_\\omega$ is the Chebychev polynomial of degree $\\omega$. Then, the key property we leverage is that $|T_\\omega(x)| \\leq 1$ on $(-1, 1)$. This implies that \n$$\n\\lVert h \\rVert_\\infty \\leq \\sum_{\\omega} |h_\\omega| := \\lVert h \\rVert_F, ~ \\text{which allows} ~ h_\\star \\geq c - \\lVert h - c - g \\rVert_F, ~~ \\forall c \\in \\mathbb{R}, g \\geq 0.\n$$\nThis is exactly Eq. $(2)$ l.111, which allows for the same analysis as the one with the Fourier series. Note that we could have the same relation with the canonical basis you mentioned (i.e. $|x^p| \\leq 1$ on $(-1, 1)$) but this would likely result in a big gap between the resulting $F$-norm and the $L_\\infty$ norm. \n\n\nTo conclude, an algorithm which handle Fourier series would be enough. However, we obtain a more efficient implementation with the Chebychev basis, for which any polynomials can be converted to. \n\n\n## Other solvers\n\nWe compared to TSSOS as it is the state of the art for fast (approximate) certification of polynomials. On top of that, it handles both complex and real polynomial hierarchies, with well-functioning implementation available. \n"}, {"review_id": "S76vosOpOQ", "reviewer": "Reviewer_rJQd", "summary": "This paper presents GloptiNets, a method to bound the suboptimality of a given candidate solution to the optimization of a smooth (nonconvex) function on the hypercube.\n\nNonconvex optimization with optimality certificates is difficult. Oftentimes it is relatively easy (fast) to compute a candidate solution, but it is much more difficult (computationally expensive) to bound the suboptimality of the solution. A popular way to provide optimality certificates is via polynomial sums of squares (Lasserre's hierarchy), but it (a) can only handle functions that are polynomials and (b) scales poorly to the dimension of the problem due to computational bottlenecks in semidefinite programming.\n\nGloptiNets tries to tackle the drawbacks of poly-SOS. The key observation is that, given a candidate solution, any positive function provides a lower bound, and hence a bound on the suboptimality. With this key observation, and considering the recent success of machine learning, the overall idea of GloptiNets is to seek a positive function parametrized by \"neural networks\" (more precisely the anchor points $z$ and the matrix $R$ in Definition 1.)\n\nThe rest of the paper mostly focuses on choosing the Kernel function and leveraging sampling (and concentration inequalities) to evaluate the loss function more efficiently (for which the reviewer did not check carefully).\n\nThe experiments of this paper compare GloptiNets with TSSOS, a state-of-the-art polynomial SOS toolbox, on computing certificates for random positive trigonometric polynomials. The experiments show that although TSSOS can obtain high-accuracy certificates, GloptiNets is much more scalable.\n\n", "questions": "I notice that in the results table, the best suboptimality GloptiNets can produce is in the order of $10^{-3}$. I wonder if this can be improved by, for example\n- increase the number of samples $x_1,\\dots, x_N$,\n- increase the size of the neural network (Fig. 2 partially answers this, but the accuracy there is still far from, say $10^{-9}$ as can be achieved by TSSOS)\n- let the neural networks train for longer time\n- increase the number of samples $\\omega_1,\\dots,\\omega_n$\n\nIf it is possible to achieve the same certificate accuracy as TSSOS, then it is useful to report the number of sample points and training time required to attain the accuracy; if it is not possible, then an explanation of this should be provided (because the positive function class of GloptiNets should subsume the positive function class of TSSOS, and therefore the NN should be able to achieve the same accuracy as TSSOS if enough parameters are allowed?). ", "limitations": "Limitations are clearly stated.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper tackles the important problem of nonconvex optimization with certificates. \n- The proposed GloptiNets mitigates the drawbacks of existing poly-SOS frameworks, i.e., it can handle non-polynomial problems and it does not rely on semidefinite programming. As a result, it is more scalable.", "weaknesses": "The biggest issue with this paper is that (i) its experiments are rather limited (I believe there are only 6 problems tested), and (ii) the limited experiments are not even related to applications where optimality certificates are desired. Therefore, it is questionable how useful this technique will be in practice (and it kind of defeats the purpose stated in the introduction). \n\nI would encourage more experiments where the optimality certificates are indeed valuable (for example recently in [robotics](https://arxiv.org/abs/2109.03349)). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n## Use of GloptiNets in practice\n\nSynthetic datasets offer the advantage of precise parameter control, including the function's norm and the number of coefficients for polynomials. This allows us to determine that the quality of GloptiNets certificates depends on the former and not the latter.\n\nIt would be very interesting to apply GloptiNets to the example the reviewer gives in robotics; however, their model uses specific functions which exhibit discontinuities: this may require a separate focused effort for efficient certification. \n\nMoreover, while certifying polynomials is a natural application of GloptiNets, its capabilities extend beyond this specific function class. In our response to reviewers, we present new examples of successfully certifying kernel mixtures, for which GloptiNets is the only alternative we are aware of. Kernel mixtures, which represent functions learned by various kernel algorithms, are widely used in the machine learning domain, suggesting that GloptiNets could find substantial applicability there.\n\nTo be more specific on this last point, given some samples $(x_i, y_i)_{1 \\leq i \\leq n}$ from a black-box process, one can fit a model $h(x) = \\sum\\_{i=1}^n \\alpha_i K(x_i, x)$, where $\\alpha$ is given by *e.g.* $\\alpha = (K + \\lambda I)^{-1} y$ for Ridge regression. Then, GloptiNets can certify the minimum of this model, which acts as a certificate on the black-box process with some additional statistical assumptions. \n\nOverall, our work serves as a proof of concept, laying the groundwork for future research to build upon and apply this framework to certify real-world applications.\n\n\n## Tightness of the certificates\n\nWe give a detailed response in the general answer to all reviewers. In there, we detail the influence of all the parameters you mentioned. In a nutshell, increasing the number of samples $x_1, \\dots, x_n$ and the training time will result in better optimization, hence lower estimation error; increasing the size of the network will lower the approximation error; finally, increasing the number of frequencies $\\omega_1, \\dots, \\omega_n$ will result in lower variance."}, {"review_id": "u0Gs1OgpIy", "reviewer": "Reviewer_qa97", "summary": "This paper focuses on non-convex global optimization on the hypercube. \nThe approach is built on top of the framework [7] and relies on non-negativity certificates that are not only restricted to non-negative polynomials since it is applicable to any function with computable Fourier coefficients. \nThe methodology is flexible in the sense that one can increase the certificate of the obtained certificate by relying on the so-called k-SOS method. The approach is naturally compatible with GPU computation thanks to a modular Bessel kernel, which is stable by product. The resulting optimization method, called GloptiNets, can be handled with automatic differentiation. Afterwards the algorithm is benchmarked against the TSSOS library designed for sparse polynomial optimization on six problems of dimension 3 or 4. The performance are similar or less good when the number of coefficients is small, and certificates are obtained with GloptiNets on examples for which the SDP solver used by TSSOS runs out of memory.\n\n", "questions": "l123: each z_i is a vector of T^d so shouldn't we have Z \\subset T^d?\n\nl124: which norm is used?\n\nAfter l154: the matrix R suddenly (re-)introduced in Equation (7) is rather confusing. Where does this matrix come from? I guess that it is related to R from definition (1).\n\nFigure 1 is not mentioned in the text and I could not understand it. The F norm color is displayed in orange, not in red. \n\n(8) The expectation notation differs from (7) as there is no sub-index anymore.\n\nIn Figure 2, I cannot see any red.\n\nCould one obtain estimates of the difference between the L-infinity and Fourier norms? Is there a specific class of examples where this difference is significant?", "limitations": "There is a clear section dedicated to limitations with an explicit list:\n- an extensive hyper-parameter search is required\n- the structure is not exploited\n- the setting is restricted to the hypercube\n- the benchmarks are somehow artificial\n\nTo be more convincing, the framework should be adapted to take into account the structure of real-world problems, e.g., the AC-OPF problem mentioned by the authors.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The methodology allows a certain flexibility as it is not restricted to objective polynomial functions and does not require any assumptions on the structure (e.g., sparsity, symmetry) apart from the hypercube constraint. \nOne can also increase the accuracy of the certificate by considering bigger nets.\n", "weaknesses": "Some technical explanation are not easy to follow (see the questions below). \n\nThe title of the paper is slightly misleading, I suggest to emphasize that the optimization is performed on the hypercube.\n\nThe paper only provides numerical comparisons for low dimensions (the number of variables is either 3 or 4) and the corresponding benchmarks are cooked by hand (called synthetic in the conclusion), thus do not correspond to any concrete optimization problem.  Even if it is promising, I believe that this methodology in its current state is not yet convincing for optimizers interested in either academic or industrial applications. \n\nIn addition, the accuracy of the obtained certificate is low compared to interior-point methods. What would be the amount of computational time required to obtain a similar accuracy with GN? On Figure 2, the number of parameters required to go from 0.1 to 0.02 increases rather quickly. This can also be concluded from the numbers in Table 1. For problem 3, it is approximately 3 times slower to double the accuracy of the resulting certificate (going from 1.3e-2 to 6.9e-3). So one could believe that it would take a rather considerable amount of time to reach an accuracy of 1e-8.\n\nI believe that the statement \"TSSOS is not guaranteed to converge to f* but executes faster, and thus is on an equal footing with GloptiNets\" is quite misleading for two reasons: \n\n1) The efficiency of TSSOS increases when the optimization problem involves sparser polynomials (with low n), which is not the case here for problems 3 and 6.\n\n2) The efficiency of TSSOS relies on the one of the tool used to solve the SDP. An alternative SDP solver such as COSMO would be certainly much more efficient but would also yield certificates with lower accuracy.\n\nSimilarly the sentence \"poly-SoS methods (whose complexity scales dramatically and in a rigid way with dimension and degree of the polynomial)\" is misleading. For a given certificate accuracy, there is no established estimate showing that the complexity of poly-SOS methods is higher. \nSo I strongly suggest to the authors to either reformulate this statement or to justify it with rigorously established statements. \nThe rigidity statement is also not really accurate as any structure-exploiting variant of the Moment-SOS hierarchy comes with a specific computational cost and convergence rates. \n\nThere is a potentially high source of conservativeness for the resulting lower bound because of the difference between the L-infinity and Fourier norms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## About the quality of the certificate\n\nWe refer to the answer to all reviewers where this matter is discussed extensively with new experiments. \n\n## Comparison with TSSOS \n\n> The efficiency of TSSOS increases when the optimization problem involves sparser polynomials (with low n), which is not the case here for problems 3 and 6.\n    \nThis is indeed the point we make. We show that TSSOS is very efficient when the number of coefficients in the polynomials is small, resembling a sparse polynomial (xps 1, 2, 4, 5). However, we show that the added value of our algorithm lies on certifying dense problems, of which xps 3 and 6 are instances of. \n\nWe recall this limitation in the \"Limitations\" section, \"our model is not competitive on problems which exhibit some algebraic structure, as for instance term sparsity\" (l. 306).\n\n> The efficiency of TSSOS relies on the one of the tool used to solve the SDP. An alternative SDP solver such as COSMO would be certainly much more efficient but would also yield certificates with lower accuracy.\n    \nWe thank the reviewer for pointing this out. We will add it to the main text. \n\nHowever, this does not change the conclusion of the experiments: polynomial hierarchies require forming the moment matrix, whose size scales exponentially in the number of coefficients or in the problem's dimension. Term and correlative sparsity leveraged by TSSOS mitigate this issue on sparse polynomials by turning a high-dimensional problem into multiple small-dimensional problems. However, this is not applicable in the \"dense polynomials\" settings we consider in xps 3 and 6. For these ones, allocating enough memory to assemble the moment matrix is not possible, so using COSMO instead of MOSEK will not change anything in those cases. \n\n## Quality of the $F$-norm \n\nThis is indeed a source of conservatism which is hard to quantify. Note however that this is the smallest norm for the norms given by summable, positive operators (Lemma 3 in [1]).\n\n[1] Blake Woodworth, Francis Bach, and Alessandro Rudi. Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares. In Proceedings of Thirty Fifth Conference on Learning Theory, pages 4620–4642. PMLR, June 2022.\n\n## Complexity of TSSOS \n\nWe will reformulate this point: \n- Given a polynomial $f$ and a tolerance $\\epsilon$, neither poly-SoS nor GloptiNets provides a priori guarantees on the time complexity for certifying the positivity of $f$ up to an error $\\epsilon$. \n- However, GloptiNets provides a bound on the complexity of the algorithm (as choosing the model size and the training time is left to the user), whereas poly-SoS, in their standard variant, requires a relaxation order of at least $p_{\\min} = ⌈deg(f)/2⌉$, which requires assembling a (potentially block-diagonal) moment matrix of size $O(\\binom{d + p_{\\min}}{d}) = O(p^d)$. \n\n\n## Answers to questions\n\nWe thank the reviewers for spotting the following typos we will fix in the main text. \n\nl123: Indeed, this is $\\mathbf{Z} \\subset \\mathbb{T}^d$ rather than $\\mathbf{Z} \\in \\mathbb{T}^d$\n\nl124: This is the Euclidean norm, $\\lVert R K_\\mathbf{Z}(\\mathbf{x}) \\rVert_2^2$\n\nAfter l154: $g$ is a K-SoS model introduced in the Definition 1 above. \n\nFig. 1 shows on a random example the possible discrepancy between the $L_\\infty$ norm (what we want to estimate in blue), the $F$-norm (what is tractable to estimate, in orange) and its tractable-to-evaluate probabilistic estimate, in green. This figure is updated in the document attached to the answer to all reviewers. \n"}]

Author rebuttal:
We thank the reviewers for their time and helpful feedback. Individually, we address each of their questions. Furthermore, we showcase new experiments demonstrating two key points: (1) the ability to obtain tighter certificates than the ones reported in the paper and (2) the versatility of our framework beyond polynomial optimization.

## Second-order optimization for tighter certificates

### Motivation

As pointed out by reviewers `RR26`, `rJQd` and `qa97` and detailed in Sec. 5 "Limitations", the certificates obtained by GloptiNets on **small polynomial** optimization task are not as tight as the ones obtained by polynomial solvers (Table 1, lines 1-2,4-5). 

The certificates we compute are of the form `Fnorm_approx + var/√N`, where `N` is the number of frequencies sampled. The second term can be made negligible by choosing $N \gg 1$. The first term measures the quality of the approximation of $f - f_\star$ by out extended k-SoS model $g_\theta$, where $\theta = (R, \mathbf{z})$ as in Definition 1. More specifically, it is the sum of the approximation error and the estimation error. Given the fact that k-SoS models are universal approximators, the former will go to $0$ if we add more parameters to $g_\theta$. To make the latter smaller, we perform **approximate second-order optimization** in Algorithm 1 with L-BFGS. 

### Results

The results for these experiments are available in **Table A** in the new material attached. 

On the bigger model, using L-BFGS enables the bigger model (GN-big) to have a certificate about **one order of magnitude** tighter that the ones presented in the paper. The smaller model also benefits from this procedure, altough marginally. This shows that in the experiments reported in Table 1 in the original submission,  GN-big suffered from a high estimation error. 

To conclude, tighter certificates than the one presented in Table 1 are achievable by GloptiNets. This requires (1) sampling enough frequencies $N \gg 1$ *(to lower the variance term)*, (2) large enough models *(for the approximation error)*, and (3) good enough optimization *(for the estimation error)*. We detailed the first two points in our paper, but will definitely add the third in the discussion of the experiment section. 

We thank the reviewers who motivated these new results. 

## Optimizing Kernel mixture

### Motivation

Although we compared our approach to TSSOS for certifying polynomials, our model is not confined to this function class. This is evidenced by successful experiments on kernel mixtures, where our approach stands as the only viable alternative we are aware of.

In our submission, we carried out experiments with polynomials so that we could compare with existing solvers. The conclusion was that GloptiNets was no match to TSSOS when certifying small polynomials $f$ which exhibits some algebraic structure, but had a complexity independent of the number of coefficients of $f$. This enables GloptiNets to certify polynomials which are out of reach of TSSOS (Table 1, lines 3,5). Here, we go one step further and optimize a kernel mixture, which **has no polynomial structure**. 

### Results 

The results are showcased in **Figure A** in the document attached. 

The function we certify are of the form $f(x) = \sum_{i=1}^n \alpha_i K(x_i, x)$, where $K$ is the Bessel kernel. Such function are ubiquitous in machine learning and arise *e.g.* when performing kernel ridge regression. They are characterized by their number of coefficients $n$ and their RKHS norm $\lVert f \rVert_{\mathcal{H}_s}^2$. Following Algorithm 1 as outlined in the paper, we use GloptiNets and plot the certificate function of the network size.

We can draw the same conclusion as seen in Figure 2 in the paper. 
Firstly, GloptiNets' certificates depend solely on the function's norm, independent of its representation with the number of basis functions $K(x_i, x)$. Secondly, bigger networks provide tighter certificates. 

Thus, even though the criticism that GloptiNets is not as tight as TSSOS is fair, it is only valid when certifying **small polynomials**. For the new showcased experiments, GloptiNets is the only alternative we are aware of. 

## Update Fig. 1

We update Fig. 1 from the paper to add error bars on the random realizations and improve the rendering. 

Meta-review: This paper studies non-convex optimization with certificates, where the output of the algorithm and the estimate minimizer are provided and an explicit precision is constituted by the approach presented in this paper. This paper is theoretically solid. All the reviewers are satisfied with this paper and the revision. I suggest to accept it as a spotlight. The AC had a thorough discussion with the SAC and the SAC agreed on the decision.
Decision: Accept (spotlight)