- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper considers the recovery of the support of a measure given only its moments. This is an important step in polynomial optimization by sums-of-squares. It tackles the difficult situation where the support is not finite and has codimension at least one. This is the case which is common in practice and for which no existing algorithm can achieve it. This is done in two main steps: recovering the algebraic carrier and then use CD kernels on it.
Critical strengths
- The paper considers the recovery of a measure in mixed scenarios that are common in practice.
Critical weaknesses
- I think the paper is out of scope for the vast majority of attendees of ICLR and of machine learning in general (in fact the search for the word "learning" retrieves zero results), so, given its technicity, this will not interest many persons. I would favor venues in optimization.
- Because of the conference paper length, the paper is hard to follow and a few more pages would be needed to make the paper adapted to the ICLR community.
Questions for authors
- Would it be possible to use constraint that ||x||2 \leq 1 instead of | x|\infty \leq 1 in (3)? This is often needed in practice and often considered as a way to make the set compact in SOS problems.
- Does the algorithm come with any form of guarantees for the four steps (beyond what Theorem 1 gives for one of the steps)?
2 comments
Thanks for the clarifications. Unfortunately, the relevance to the ICLR community remains questionable and I maintain my score. Best
Response to the questions
We thank the reviewer for the feedback on the submission.
We have added Appendix H, “Ablation study and comparison with other methods,” to make the practical contribution more apparent and easier to access. It separates candidate generation from filtering and compares six combinations: ambient grid, ambient Monte Carlo, or carrier sampling, each followed by standard or regularized CD filtering. The experiments indicate that explicitly sampling the recovered algebraic carrier can substantially improve Hausdorff accuracy in the examples studied. They also report error against runtime, with sample generation and filtering performed on a normal office laptop.
Replacing the box by a Euclidean ball. Yes. The constraint ∣x∣∞≤1 serves as a convenient bounding and normalization convention but can be replaced by an euclidean norm. However, one has to take into consideration that the true support of the underlying measure might change.
Guarantees for the four steps. We do not currently provide a general convergence guarantee for the complete algorithm. The status of the individual steps is as follows:
1. Carrier recovery. For exact moments, the proposition in Section 4.1 establishes that under assumptions of Problem 1, the moment-matrix kernel consists precisely of the polynomials vanishing on the support at the appropriate degree. Its common zero set contains the support. Identifying this zero set with the full algebraic carrier additionally requires a sufficiently large degree to capture the necessary defining relations.
2. Carrier sampling. The random-slicing method has a distributional guarantee under its smoothness and finite-volume assumptions, with the prescribed weighting and exact intersection computations; see Section 4.2 and Appendix B. These assumptions and numerical requirements matter when applying it to recovered or singular carriers.
3.Relative CD construction. For genuine moments, the pseudoinverse defines the relative CD kernel on the recovered variety, as described in Section 4.3. This algebraic construction is well defined, but does not by itself establish that a chosen sublevel set approximates the support.
4.Thresholding and the final approximation. The returned sublevel set is semialgebraic by construction. We do not yet have a general computable threshold sequence guaranteeing Hausdorff convergence in the setting of the paper. The sampling comparison in Section 5.4 and Appendix C isolates the effect of candidate placement and uses idealized selection assumptions; it does not prove convergence of the implemented CD thresholding procedure.
We explicitly identify convergence guarantees, principled threshold selection, and robustness to pseudo-moments as open problems in Section 6