acceptodds
Under review as a conference paper at ICLR 2027

Recovering Lower-Dimensional Semialgebraic Support of a Measure from its Moments

Abstract

Recovering probability measures from their moments has numerous applications, esp. in connection with the method of moments in statistics and optimization. In the setting where measure need not be finitely atomic, but its support is known to be compact and semialgebraic with codimension at least one, the problem is still open. We combine moment-matrix kernel information with the Christoffel–Darboux kernel to provide a discrete approximation of the support. To validate the proposed approach, we test our algorithm on analytically computed moments and pseudo-moments arising from polynomial optimization problems without unique global minimizers. This complements well-known recent work on recovery of measures with algebraic support, where the kernel of a moment matrix can reveal polynomials vanishing on the support, and on recovery of sufficiently regular full-dimensional supports, where estimators constructed by thresholding the Christoffel–Darboux kernel are known to converge asymptotically to the support.

Primary area:
learning theory
Keywords:
Semialgebraic support, Measure, Moments

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_1NEUOpenReview ↗
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
AuthorsOpenReview ↗

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|x|_\infty\le1 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

Thanks for the clarifications. Unfortunately, the relevance to the ICLR community remains questionable and I maintain my score. Best

Reviewer_8sAPOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the problem of recovering probability measures from their moments when the measure need not be atomic but its support is known to be compact and semialgebraic with codimension at least one. Specifically, given only the moments of μ\mu up to degree 2d2d, but no samples, this paper aims to compute a finite set of points which are at a small Hausdorff distance from supp(μ)\mathrm{supp}(\mu). The solution is an elegant 3 step procedure: a) using the moments and the degree, form the moment matrix, then find the kernel of the moment matrix, and then compute a real zero set Z\mathcal{Z} containing the Zariski closure of supp(μ)\mathrm{supp}(\mu), b) using random slicing [BM20] sample from Z\mathcal{Z}, and c) given a threshold τd\tau_d, compute a quadratic form with respect to the pseudoinverse of the moment matrix for samples drawn from Z\mathcal{Z}, and find all points where the quadratic form is less than τd\tau_d, and return all such point. The algorithm is tested on some polynomial optimization problems without global minimizers.

Critical strengths
  1. The problem discussed here is novel and the idea of sampling from only the moments is appealing as often these moments are available and would be good to be able to generate/sample points from the underlying distribution.
  2. This work complements some recent work on recovery of measures with algebraic support e.g., Vu et al. (2022) and Bentancur et al. (2026).
Critical weaknesses
  1. Since τd\tau_d is not known in advance, the performance of the algorithm seems to rely on how it is chosen, as a weaker upper bound will lead to a drastically poor sampler. E.g., in Figure 1, while points sampled represent both rims, the points near the center of the cone are not sampled. Say one wants to use this method as a generator for some synthetic data, missing points near the boundary of the classifier or some cluster boundary can affect the apparent geometry of the space in which the data is drawn from.
  2. Given no comparable methods it becomes somewhat unclear how the method performs. Maybe I missed the comparison in the main paper, but can we have some comparisons to other methods that tackle a somewhat similar problem (however contrived the comparison)? I am asking this, as without any lower bounds, it is unclear how efficient the algorithm is.
  3. Also no runtime analysis has been provided for Algorithm 1. Any such addition would allow us to judge the practical applicability of the method introduced in this paper.
Questions for authors

Please see the weaknesses section. Also:

  1. For pseudo-moments of Section 5.3 can we run some sort of subspace approximations to approximate kerMd(y)\mathrm{ker} M_d(y)?
2 comments
AuthorsOpenReview ↗

Response to the questions

Thank you for the constructive questions about threshold selection, comparisons, computational cost, and pseudo-moments. We address these points below.

Comparisons and computational cost. We have added Appendix H, “Ablation study and comparison with other methods.” It compares all six combinations of three candidate-generation strategies—ambient grid, ambient Monte Carlo, and sampling on the recovered carrier—and two filters: the standard relative CD score and the regularized CD score of Marx et al. (2021). Appendix H.1 considers a product of five segments in $ \mathbb R^{10} $ using pseudo-moments, and Appendix H.2 considers a product of five semicircles using analytic moments.

The Figures 10 and 11 report Hausdorff error, together with its two directed components, against runtime. The runtime includes both the sampling and the filtering. In these experiments, the main improvement comes from sampling on the carrier, with a particularly substantial reduction in the “worst fake positive” error from equation (12). We also include the performance of using unfiltered samples from the carrier to illustrate the contribution of the filtering.

The reported timings include sample generation and filtering. The experiments were performed on a normal office laptop with 32 GB RAM and an AMD Ryzen 7 PRO 7840U processor 3.30 GHz.

Interpretation of the cone example in Figure 1. We apologize that the figure did not make the intended support sufficiently clear. In this experiment, the target is

x \in \mathbb{R}^3 : x_3^2 = x_1^2 + x_2^2, \quad x_3 \in [-1,-0.5] \cup [0.5,1] \right\\}.$$ Thus, the central region \$ |x_3|<0.5 \$ is deliberately absent from the true support. Its absence from the retained cloud is the intended behavior, rather than a failure to sample a region of positive mass. The target comprises two truncated conical surface patches, not the entire cone. In Figure 1 on the left, there are samples on the cone before filtering and the heatmap shows that the CD kernel grows outside the actual support. There is nevertheless finite approximation error near the boundaries, which we do not wish to obscure. Section 5.2 reports an accepted vertical range of approximately $$[-0.958,-0.489]\cup[0.489,0.958],$$ compared with the true range above, and a Hausdorff error of approximately (0.09). **Choice of $\tau_d$.** We agree that threshold selection is an important limitation. Changing $\tau_d$ can alter both boundary accuracy and the number of connected components of the estimated sublevel set. Sections 4.3–4.4 comment on the current heuristic choices, and Section 6 explicitly leaves a general principled threshold rule open. There is also a fundamental issue of identifiability from finite moments. Tchakaloff’s theorem guarantees a finitely atomic measure matching the moments of a given measure through any prescribed finite degree. For a non-atomic measure, applying that theorem yields infinitely many distinct atomic representations. Those atomic alternatives alone do not establish non-identifiability within our non-atomic model. However, ambiguity in the number of components can also occur within that model. For example, the uniform probability measures on $$[-1,1] \quad\text{and}\quad [-b,-a]\cup[a,b], \qquad a=\tfrac14,\quad b=\tfrac{\sqrt{61}-1}{8},$$ both have moments $m_0=1$, $m_1=0$, and $m_2=1/3$. Embedding these intervals on a line in $\mathbb R^2$ gives lower-dimensional semialgebraic supports with positive intrinsic densities, but with one and two connected components respectively. Consequently, reliable selection among competing support geometries requires additional structural information. An expected number of connected components is one useful example: a practitioner can sweep thresholds, examine the resulting semialgebraic estimates, and reject those inconsistent with that prior knowledge. Known feasibility constraints provide another check in polynomial optimization, as discussed in Section 4.3. Component count alone need not determine a unique or accurate threshold, and apparent connectivity in a finite cloud also depends on sampling resolution. This finite-moment ambiguity does not rule out asymptotically consistent threshold rules under additional assumptions. Establishing such guarantees for our estimator remains open. **Subspace approximations for pseudo-moments.** Yes. A natural approach is to approximate the kernel using the eigenspace associated with near-zero eigenvalues, or the corresponding right singular vectors, and interpret those vectors as approximate polynomial relations. Our numerical implementation already requires a singular-value cutoff, whose selection is acknowledged in Section 6.
Reviewer_8sAPOpenReview ↗

response to rebuttal

Thank you to the authors for responding to my reviews.

I am perhaps confused now regarding the paper. It clearly seems to pitch itself as a theoretical paper which a large part of the algorithm requires heuristic evaluations (for which no guarantees can be provided).

The explanations to Figure 1 should be added to the paper. Furthermore, τd\tau_d seems to impact the performance pretty significantly. Ideally, under some assumptions, the impact can be theoretically studied, and I believe such a result would have helped the cause of this paper. Finally, the singular-value cutoff is decided heuristically (seems). So then one can study guarantees on some fixed singular value and provide guarantees. As such, I feel the novelty and the theoretical justification remain insufficient for acceptance and would keep my original score.

Reviewer_aGwBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the process of estimating the support for a probability measure. The support here is assumed to be compact and semi-algebraic with co-dimension at least 1. The work uses moment matrix kernel to recover the algebraic carrier. Then random-slicing method is used for sampling and only the points are retained for which the CD kernel is below a certain threshold. Hence, the semi-algebraic inequality described as the sub-level set is an estimate of the support.

Critical strengths

The paper studies an important problem. The use of sampling technique is interesting here since it samples directly on the algebraic carrier. It yields a cloud of points in a relevant lower dimensional geometry. Then application of CD kernel helps to obtain an estimate of the support set. A sample is basically a cloud of points that provides knowledge about the location of the variety. The method avoids explicitly recovering the degree and the coefficients of the original inequality constraints of the support set as it is difficult to estimate them.

Critical weaknesses

When I was checking the literature, I found that a closely related paper exists Marx et al. (2021). Although this paper is cited, the manuscript does not explain how the carrier recovery and sampling techniques differ from this work. Also, the practical advantage of the technique in the manuscript is not clearly established.

I would request to do an ablation study and highlight the differences and novelty of the current technique compared to this prior work. Additionally in the experiments, more baselines should be added. It might be also interesting to record compute time and compare it with Marx et al. (2021) compute time and record their performance.

Questions for authors

Please address the critical weakness section.

2 comments
AuthorsOpenReview ↗

Response to the questions

Thank you for highlighting the need to clarify the relationship with Marx et al. (2021) and to establish the practical benefit of our approach. We have added Appendix H, “Ablation study and comparison with other methods,” specifically to address these concerns. Our positioning is best explained by separating two choices: where to generate candidate points, and how to filter those points. We recover polynomial equations from the moment matrix, generate candidates directly on the resulting algebraic carrier, and then apply a CD-based filter. We build on established methods for sampling on algebraic variety; our contribution is applying them to estimate the support.

Marx et al. (2021) develop regularized CD methods for reconstructing functions from moments of measures supported on graphs. Our setting is different because the structure of the support assumed in Problem 1 is more general than a function of a graph. However, we adapt their regularized score as a valid alternative for our filtering method. Our comparison therefore uses this score within the support-recovery pipeline; it should be understood as an adaptation of their method to our task.

The new ablation crosses three candidate-generation strategies—an ambient grid, ambient Monte Carlo sampling, and sampling on the recovered carrier—with two filters: the standard relative CD score and the adaptation of regularized CD score by Marx et al. (2021) (using ε=0.01\varepsilon=0.01). This gives six methods, which we compare on 2 examples in dimension 10. Appendix H.1 studies a product of five segments in R10\mathbb R^{10}, using pseudo-moments from polynomial optimization; Appendix H.2 studies a product of five semicircles, using analytic moments. Please, see Figure 10 and Figure 11 for the time evolution of the accuracy of recovery for each method.

The main empirical finding is that, in these experiments, sampling on the carrier has a larger effect on Hausdorff accuracy than switching between the two filters. In particular, it reduces the contribution from retained points lying away from the true support. Moreover, the unfiltered-carrier comparison in Appendix H.2 also shows why filtering remains necessary: the carrier contains regions outside the support (see Figure 12).

The spectral decomposition in Appendix H (namely equation (11)) explains the relationship between the regularized (Marx et al. (2021) ) and standard CD kernel. Regularization introduces a penalty for violating the recovered carrier equations. This penalty vanishes on the carrier itself, where the remaining difference concerns the weights assigned to positive eigendirections. Explicit carrier sampling can therefore be combined with either filter but the penalty part of the regularized CD score vanishes on the carrier.

The new Figures 10 and 11 report Hausdorff error and both directed error components against runtime. These timings include sample generation and filtering. All experiments were run on a normal office laptop with 32 GB RAM and an AMD Ryzen 7 PRO 7840U processor 3.30 GHz.

Thank you to the authors for addressing my comments. The novelty is mainly combination of different existing tools into one pipeline to solve the problem. Moreover, some components of the proposed framework are heuristic and lack theoretical guarantees. So as a theory paper, I feel the novelty and the theoretical justification remain insufficient for acceptance. I maintain my current score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions

We thank the reviewers for their constructive feedback. In response, we have added new experimental evaluation, clarified the novelty of our approach relative to existing work, and provided further discussion of its theoretical and numerical limitations. The main revisions are summarized below.

1. New ablation study and additional baselines (Appendix H).

We have added Appendix H, “Ablation Study and Comparison with Other Methods,” which systematically compares three candidate-generation strategies—ambient grid sampling, ambient Monte Carlo sampling, and sampling on the recovered algebraic carrier—with two filtering methods: the classical relative Christoffel–Darboux (CD) kernel and a regularized CD kernel adapted from Marx et al. (2021). This yields six combinations, together with an additional unfiltered-carrier ablation to isolate the contribution of CD filtering.

2. New experiments in dimension ten and runtime comparisons (Figures 10–12).

We evaluate the methods on two examples in R10\mathbb R^{10}: a product of five diagonal segments using pseudo-moments obtained from polynomial optimization (Appendix H.1), and a product of five upper semicircles using analytic moments (Appendix H.2).

Figures 10 and 11 compare approximate Hausdorff errors and their two directed components as functions of runtime, including sampling and filtering. The experiments demonstrate that sampling directly on the recovered carrier provides a substantial improvement over ambient sampling or Monte Carlo. The unfiltered-carrier experiment further illustrates why CD filtering is necessary to exclude portions of the algebraic carrier lying outside the true support.

The experiments were performed on a laptop equipped with 32 GB RAM and an AMD Ryzen 7 PRO 7840U processor.

3. Clarification of novelty and relationship to Marx et al. (2021).

We have clarified that our contribution lies in combining moment-matrix kernel recovery, sampling on the algebraic carrier, and CD filtering into a procedure for reconstructing lower-dimensional semialgebraic supports.

Unlike the function-reconstruction setting studied by Marx et al. (2021), our framework does not require the support to be represented as the graph of a function. We also explain how their regularized CD score can be adapted as an alternative to the standard CD filtering oracle.

The spectral decomposition in Appendix H, Equation (11), clarifies the relationship between the classical and regularized CD kernels, particularly the fact that the regularization penalty associated with nullspace directions vanishes on the exact algebraic carrier.

Overall, these revisions provide a more comprehensive comparison with existing methods, demonstrate the practical benefit of sampling directly on the algebraic carrier, and clarify both the scope and the limitations of our support-recovery procedure.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.