GloptiNets: Scalable Non-Convex Optimization with Certificates

Summary

This paper focuses on non-convex global optimization on the hypercube. The 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. The 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.

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. One can also increase the accuracy of the certificate by considering bigger nets.

Weaknesses

Some technical explanation are not easy to follow (see the questions below). The title of the paper is slightly misleading, I suggest to emphasize that the optimization is performed on the hypercube. The 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. In 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. I 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: 1) 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. 2) 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. Similarly 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. So I strongly suggest to the authors to either reformulate this statement or to justify it with rigorously established statements. The 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. There is a potentially high source of conservativeness for the resulting lower bound because of the difference between the L-infinity and Fourier norms.

Questions

l123: each z_i is a vector of T^d so shouldn't we have Z \subset T^d? l124: which norm is used? After 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). Figure 1 is not mentioned in the text and I could not understand it. The F norm color is displayed in orange, not in red. (8) The expectation notation differs from (7) as there is no sub-index anymore. In Figure 2, I cannot see any red. Could 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?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

There is a clear section dedicated to limitations with an explicit list: - an extensive hyper-parameter search is required - the structure is not exploited - the setting is restricted to the hypercube - the benchmarks are somehow artificial To 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.

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. Nonconvex 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. GloptiNets 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.) The 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). The 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.

Strengths

- The paper tackles the important problem of nonconvex optimization with certificates. - 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). I would encourage more experiments where the optimality certificates are indeed valuable (for example recently in [robotics](https://arxiv.org/abs/2109.03349)).

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 - increase the number of samples $x_1,\dots, x_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) - let the neural networks train for longer time - increase the number of samples $\omega_1,\dots,\omega_n$ If 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?).

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations are clearly stated.

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). As I understand it, the certificate computation utilizes the Fourier basis. They 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.

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. The 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. Also, 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. Since I am not familiar with this branch of optimization, I cannot assess the novelty that much.

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? Also, the high value of the certificate and lack of hyperparameter tuning, except model size, weakens the paper (see questions). Additionally, 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).

Questions

1. currently the certificate seems very loose at $O(10^{-2})$. Is this a good number? 2. 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? 3. 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)? 4. Baseline methods seem very limited. Is TSSOS the only viable alternative? 5. In Fig 2, no red curve is presented, but mentioned in the caption.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

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.

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.

Strengths

1. The paper is clear and beautifully written. It is a pleasure to read. 2. 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. 3. 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

No major weaknesses identified. Below are some minor suggestions that I hope the authors consider, but should not be taken as criticism towards the work. ## Minor suggestions 1. Add x and y labels to Figure 1. 2. 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. ## Typos L244: eventhough -> even though L245 optimisation -> optimization (since American spelling is used elsewhere) L93: "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

Questions

1. What is Z_d in eq. (1)? I don't think it has been defined before. 2. 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.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

I believe the limitations have been correctly addressed by the author in the Limitations section.

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.

Strengths

The paper is clearly written and the theory is interesting.

Weaknesses

The experimental results are not abundant.

Questions

No.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No.

Thanks for the reply

Thank you for clarifying the points. I guess for most problems of interest the bases you used are general enough. And thank you for the new experiments. The choice of optimizer seems to impact the certificate value significantly.

Thanks for the detailed rebuttal.

Thanks for the detailed rebuttal. It solved my concerns. I will keep my score.