S-SOS: Stochastic Sum-Of-Squares for Parametric Polynomial Optimization

Summary

This paper is concerned with the following natural generalization of polynomial optizimation: Given a distribution $\nu(\omega)$ and a polynomial $f(x,\omega)$, find the tightest (in expectation) function $c(\omega)$ that lower bounds $f(x,\omega)$ everywhere. Given the computational hardness of the problem, the authors focus on the sum-of-squares relaxation (of a given degree $s$). For trigonometric polynomials, they show a $O(\frac{\log s}{s})$ convergence of the error of the relaxation w.r.t. the optimum (here we hide factors depending on the input in the $O$ notation). Under stronger assumption on the optimal solution they further achieve fast error convergence. Finally, they complement these results with experimental evaluations (in which they apply certain SDP sparsification techniques to improve the scalability).

Strengths

I find the question investigated in this paper and the two main theorems (2.1 and 2.2) valuable and non-obvious. The "Cluster basis hierarchy" is also a non-trivial original contribution. Finally, I believe the experiments included in the paper will be of interest to the wider NeurIPS' audience.

Weaknesses

In my opinion, the main weakness of the paper lies in the fact that it fails to explain the *core* ideas behind its results. There is not a careful discussion of the theorems, their limitations and the insight required to prove them. This makes the paper easy to follow but also quite frustrating to read. I believe significant improvements can be made in this sense. Such improvements could greatly improve the quality of the manuscript. The theoretical analysis result is limited to trigonometric polynomials. This is an important restriction, but a discussion addressing this topic, possible extensions and related obstacles is not present. The cluster basis hierarchy (henceforth CBH) used to scale up the SDP is non-trivial and interesting. However it is never discussed in-depth and no theoretical result is provided. I understand that convergence results for CBH may be hard to prove, but a more comprehensive discussion seems needed.

Questions

What can the authors say for other classes of polynomials?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

I encourage the authors to further discuss the limitations of their theoretical results.

Summary

The manuscript considers variants of stochastic-SOS hierarchy for parametric polynomial optimization (POP), which had been previously considered using similar (joint+marginal) methods (https://arxiv.org/abs/0905.2497). Unfortunately the (joint+marginal) methods did not work very well, perhaps because parametric POP is known to have a very complicated structure (https://doi.org/10.1287/moor.2021.0097). While the numerical experiments are not exactly conclusive, the present manuscript provides guarantees on the rate of convergence, which improve upon the joint+marginal method somewhat. The "cluster basis" variant of the hierarchy could be of independent interest.

Strengths

-- The convergence rate results are neat, although limited to 1-periodic trigonometric polynomials over compact sets. -- The manuscript cites a number of interesting recent preprints (such as https://theses.hal.science/LAAS-POP/hal-04201167v1).

Weaknesses

-- The numerical experiments are poorly designed. The sensor network localization problem is known to be reducible (https://arxiv.org/abs/1002.0013) to trivial sizes. Even early papers (https://link.springer.com/article/10.1007/s10107-009-0338-x) considered n=10000 senosrs. The 2010 paper tests on instances with n = 20000 to 100000 sensors, while the present authors consider instances on less than n=15 sensors. This is 4-5 orders of magnitude less than the state of the art. -- It is not clear how the objective of the heuristically extracted solution (A.7.6) differs from the objective function of the relaxation.

Questions

Could you explain the application of the joint+marginal method as a starting point? Could you comment on the rates of convergence of the joint+marginal method? Could you demonstrate the behaviour of your S-SOS on the more complicated behaviours from https://doi.org/10.1287/moor.2021.0097? Cf. Definition 3.9 (Irregular accumulation point), but also Definition 3.7 (Discontinuous non-isolated multiple point) and Definition 3.6 (Discontinuous isolated multiple point).

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The discussion of the limitations is misleading. It claims that all SDP-based algorithms fail to scale, while there clearly are (https://arxiv.org/abs/1002.0013) SDP-based algorithms that scale well.

Summary

This work proposes a new sum of squares (SOS) based relaxation for stochastic polynomial optimization,called Stochastic SOS (S-SOS). For a class of problems where the cost function $f$ can depend on variables $x$ as well as randomly drawn parameters $\omega$, the authors propose a hierarchy of relaxations whose solutions yield strict lower bounds on the optimal value of $f$. For a degree $s$ relaxation, it is shown that the obtained lower bound is $\log(s)/s$ and $1/s^2$ for different parameterizations of the parametric lower bound function $c(\omega)$. Finally, the proposed methods are applied to sensor network localization problems, where S-SOS outperforms the stated baseline.

Strengths

1. This proposes S-SOS, a novel heirarchy of relaxations for solving stochastic polynomial optimization problems. 2. The paper provides asymptotic convergence results for the sequence of relaxations - that is, as the degree of the SOS program increases, the error between the lower bound obtained via the relaxation and the true optimal value reduces to 0. In particular, the finding that by using piecewise constant approximation of $c(\omega)$ achieves the $1/s^2$ convergence rate, outperforming the polynomial parameterization of $c(\omega)$, is quite interesting and surprising to me. 3. The paper is written quite clearly, with no major typos that I could find. 4. The proofs appear to be correct, with a couple of small typos such as in equation 6.

Weaknesses

1. In equation (6), I believe the polynomial in question should be $f(x,\omega) = (x-\omega)^2 + (\omega x)^2$. Otherwise, the correct solution should be $c^*(\omega) = -\omega^4/(1-\omega^2)$. 2. Perhaps in the related work section, a little space could be devoted to other approaches to polynomial optimization, such as the LP/SDP relaxations constructed using the Polya and Handelman theorems, and the LP/SOCP relaxations obtained by using DSOS and SDSOS polynomials.

Questions

1. Are there problems for which the exact lower bound can be achieved in a "single step"? That is, suppose the polynomial cost and constraint functions are of degree $s$, are there problems for which a degree $s$ relaxation suffices to obtain the true minimum? Do such problems arise in practical circumstances? 2. While the DSOS/SDSOS hierarchies do not, in general, converge to global optima, have the authors considered using the associated LP relaxations, particularly in the context of the sensor localization problem? This is salient since the LP/SOCP relaxations can be used to solve much larger problems than the SDP solutions. 3. Is there any intuition as to how the result stated in Prop. 2.2. can be extended to the multivariate case?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

The limitations of the work are discussed, though they aren't stated in a single section. It would be helpful to add such a section, perhaps in the appendix.

Summary

In their study, the authors investigate parametric polynomial optimization where the function to be minimized is \( f(x, \omega) \). Here, \( x \) represents the decision variable, and \( \omega \) signifies a noise parameter. The primary goal is to approximate the best lower bound, \( c^*(\omega) = \inf_x f(x, \omega) \), for each value of \( \omega \). To manage this setup, the Sum-Of-Squares (SOS) hierarchy is adapted, an approach first introduced by Lasserre in his seminal ``Joint and Marginal'' work in the late 2000s. The paper elaborates on the derivation of this hierarchy and its dual, as well as discussing the rates of convergence under suitable assumptions about the optimal solution \( c^* \), and includes some applications towards the end of the paper. From a technical standpoint, the work seems correct and presents a rigorous approach to handling stochastic variables in polynomial optimization. However, it does not significantly deviate from established methodologies, which may limit its appeal in terms of novelty. Regarding its relevance to the NeurIPS audience, while the modified hierarchy certainly adds practical value, the paper does not address applications that align closely with the core interests of the community. The experiments, focusing on sensor network localization, seem peripheral to the main areas of interest at NeurIPS, which typically centers around more direct applications to machine learning and artificial intelligence technologies. In conclusion, although the paper is technically proficient and might captivate a niche audience interested in theoretical optimization, it appears to fall short of the high innovation standards and relevance to ML typically expected for NeurIPS publications.

Strengths

-- Modification of the SOS hierarchy to incorporate noisy parametric problems -- Error bounds under assumptions

Weaknesses

-- Relevance -- Novelty

Questions

In your paper, you discuss the adaptation of the Sum-Of-Squares (SOS) hierarchy to handle stochastic parameters in polynomial optimization, which is a significant theoretical advancement. However, the practical applications presented, such as sensor network localization, seem somewhat tangential to the core interests of the NeurIPS community, which often focuses on direct applications in machine learning and artificial intelligence. Could you elaborate on how the methodologies developed in your study could be applied to more central problems in machine learning? Additionally, are there potential modifications or extensions to the SOS hierarchy that could make it more directly applicable to common challenges in neural network training or optimization under uncertainty?

Rating

3

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

NA

Summary

The Sum of Squares (SOS) technique is well-known in polynomial optimization studies. This paper studies its variant, in which the function to be lower bounded has random parameters drawn from some probability distribution. The main contribution is a cluster-based SDP hierarchy for the Stochastic-SOS (S-SOS) method and a convergence proof for this and the standard Lasserre. Experiments demonstrate the effectiveness of the new hierarchy in the sensor network localization problem (SNL).

Strengths

- One strength lies in the convergence results on S-SOS, which is a vital generalization of the standard SOS. The proof and arguments in the Appendix seem non-trivial and thorough. - The cluster-basis hierarchy is novel and practically relevant. Although SOS has good theoretical performance, the SDPs could be expensive to solve in real-world engineering problems. The proposed hierarchy reduces the sizes of the SDPs that need to be solved. - Applications to the SNL problem complement the theoretical results in convergence and demonstrate the advantage of leveraging the S-SOS technique over standard Monte Carlo methods.

Weaknesses

- It would be better if the authors presented the assumptions in a subsection and explained their restrictiveness. For example, Theorem 2.1 assumes the objective polynomial to be trigonometric. I wonder how challenging it is to extend the results to more general polynomial families. - The paper uses only two paragraphs to introduce and illustrate the cluster-basis hierarchy, a vital part of its contributions. A more comprehensive discussion of the hierarchy could enhance the paper's content and readability. Besides, I would suggest the authors polish the main paper more. - Novelties in the proof techniques would often attract independent interests. I wonder if the convergence proof is established by applying only the standard techniques and existing results. - The experiments seem to contain, at most, $N=15$ sensors, which are suitable for synthetic validation but may not be sufficient to demonstrate the technique's practical advantage.

Questions

Please check the comments on the paper's strengths and weaknesses. The authors should also feel free to point out any inaccuracy or misunderstanding. Thanks.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

It may be beneficial if the authors could explain more about the paper's limitations in theory (restrictiveness of the assumptions) and practice (practicality of the experimental settings). But I do not find the current presentation concerning. Similarly, I do not think the paper would have any negative societal impact.

Huh?

The authors write: **We observe that in the regular SOS hierarchy, if one starts with a degree-2s SOS polynomial then you will find exact convergence when using the hierarchy at degree-2s.** I would suggest that the authors review https://arxiv.org/abs/2403.08329, which analyzes the following: \[ \begin{array}{rl} \min_{x \in R} & x \\ \mathrm{s.t.} &1-x^2 \geq 0 \textrm{ and } & x+(1-\varepsilon)x^2 \geq 0 ,\\ \end{array} \] parametrized by a scalar $\varepsilon \in [0,1]$. There, the convergence of the moment-SOS hierarchy is finite, but arbitrarily slow as $\varepsilon$ goes to zero.

Thank you!

Many thanks for having worked out the example. I see the distinction between the separated and non-separated parametric problems, where Bellon considered the former and you are consider the latter. Thank you!