Research map / Optimization / Nonconvex and smooth optimization
S-SOS: Stochastic Sum-Of-Squares for Parametric Polynomial Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes S-SOS, a stochastic sum-of-squares hierarchy of SDPs that jointly lower-bounds parametric polynomial minima and extracts parameterized minimizers, with a convergence proof and a cluster-basis sparsification for sensor network localization.
Problem
Global minimization of polynomials that depend on random parameters, where one needs a deterministic lower bound c(ω) on the minimum and candidate parameterized minimizers, which becomes intractable for large numbers of variables.
Approach
Extends the Lasserre/moment-SOS hierarchy to parametric polynomials by searching for a polynomial lower bound c(ω) such that f(x,ω)-c(ω) is SOS in (x,ω) jointly, with the dual giving a minimizing distribution matching the noise marginal; adds a cluster (n-body) basis that keeps only low-body-order monomials to sparsify the SDP.
Key results
- On the quadratic toy problem, the S-SOS optimal value converges exponentially to p*≈0.1187 as degree increases (Figure 1).
- On 1D sensor network localization with 8 hard-constrained sensors, S-SOS achieves median Mahalanobis distance 0.04 versus 0.31 for MCPO.
- For 2D SNL with 820 basis elements, cluster basis reduces the SDP by 2.6x and S-SOS achieves median δM 3.25 versus 1848.65 for MCPO; the proven convergence rate is O(ln s / s) in L1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use S-SOS instead of MCPO | Sensor network localization · SNL (ℓ=1, r=0.5, ϵ=0.3, NH=0) | Mahalanobis distance: 2.61 ± 3.86 -> 0.94 ± 0.22 | Helped |
| Use S-SOS instead of MCPO | Sensor network localization · SNL (ℓ=1, r=1.0, ϵ=0.3, NH=0) | Mahalanobis distance: 1.10 ± 0.58 -> 0.29 ± 0.16 | Helped |
| Use S-SOS instead of MCPO | Sensor network localization · SNL (ℓ=1, r=1.5, ϵ=0.3, NH=0) | Mahalanobis distance: 0.86 ± 0.52 -> 0.11 ± 0.11 | Helped |
| Use S-SOS instead of MCPO | Sensor network localization · SNL (ℓ=1, r=1.5, ϵ=0.3, NH=2) | Mahalanobis distance: 1.06 ± 1.28 -> 0.24 ± 0.37 | Helped |
| Use S-SOS instead of MCPO | Sensor network localization · SNL (ℓ=1, r=1.5, ϵ=0.3, NH=4) | Mahalanobis distance: 0.61 ± 0.41 -> 0.10 ± 0.03 | Helped |
| Use S-SOS instead of MCPO | Sensor network localization · SNL (ℓ=1, r=1.5, ϵ=0.3, NH=6) | Mahalanobis distance: 0.48 ± 0.32 -> 0.06 ± 0.04 | Helped |
| Use S-SOS instead of MCPO | Sensor network localization · SNL (ℓ=1, r=1.5, ϵ=0.3, NH=8) | Mahalanobis distance: 0.31 ± 0.17 -> 0.04 ± 0.02 | Helped |
| Use S-SOS instead of MCPO | Sensor network localization · SNL (ℓ=2, r=1.5, ϵ=0.1, NH=0, N=9) | Mahalanobis distance: 1562.39 ± 596.29 -> 2.86 ± 0.94 | Helped |
| Use S-SOS instead of MCPO | Sensor network localization · SNL (ℓ=2, r=1.5, ϵ=0.1, NH=0, N=15) | Mahalanobis distance: 1848.65 ± 650.45 -> 3.25 ± 1.19 | Helped |
| Increase the number of hard equality constraints from NH=0 to NH=8 (ablation) | S-SOS · SNL (ℓ=1, r=1.5, ϵ=0.3) | Mahalanobis distance: 0.11 ± 0.11 -> 0.04 ± 0.02 | Helped |
Surprising findings
- The proven convergence rate for parametric S-SOS (ln s / s) is slower than the 1/s^2 rate of the standard SOS hierarchy without parameters.
- On the 2D SNL instances, the MCPO baseline has much larger Mahalanobis distances (over 1500) than S-SOS, indicating large failures of the pointwise local-solver approach.
Limitations
- Scaling to large numbers of variables remains an open problem; the cluster basis is a heuristic without a full convergence proof.
- Experiments are limited to low-dimensional uniform noise with small n and d, and the convergence proof is restricted to trigonometric polynomials on compact domains.
- Strong duality is assumed in practice rather than verified analytically.
Experimental setup
Benchmarks: sensor network localization instances (ℓ=1, ℓ=2) quadratic SOS toy function
Metrics: Mahalanobis distance optimality gap p*-p*_2s
Baselines: Monte Carlo pointwise optimization (MCPO)
Builds on: Lasserre hierarchy Joint and Marginal approach Moment-SOS hierarchy Putinar Positivstellensatz
Closest papers by meaning
- Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers (ICLR 2026 · similarity 0.85)
- Stochastic Subspace Cubic Newton Method (ICML 2020 · similarity 0.84)
- S-D-RSM: Stochastic Distributed Regularized Splitting Method for Large-Scale Convex Optimization Problems (AAAI 2026 · similarity 0.83)
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 2024 · similarity 0.82)
- Stochastic Optimization with Random Search (NeurIPS 2026 · similarity 0.82)
- Decentralized Projected Riemannian Stochastic Recursive Momentum Method for Nonconvex Optimization (AAAI 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.