PaperlayerView exact revision on arXiv

Source-linked AI summary

On the SoS Certifiability of Log-Concave Distributions

Aleksandr Storozhenko

arXiv:2609.30105v2cs.LGcs.CCmath.PR

TL;DR

The paper seeks universal-loss sum-of-squares certificates for log-concave moment bounds, which support efficient robust estimation. It establishes certificates at every even order with dimension-free, optimal moment scale.

  • Problem

    Existing Poincaré-based certificates introduce logarithmic dimension dependence, while matching the information-theoretic guarantee requires only a universal-constant loss in the moment bound.

    Source: §1 · p. 3, §1.1 · p. 4

  • Method

    It proves certifiable moment bounds that enable low-degree sum-of-squares proofs of statistical identifiability for robust estimation.

    Source: §1 · p. 3, §1.1 · p. 3

  • Results

    Every isotropic log-concave distribution is (Cm, m)-certifiably bounded for every even m ≥2, with optimal dimension-free scale Bm = O(m).

    Source: §1.1 · pp. 3–4

  • Takeaways & Limitations

    For fixed m, certifiable moment bounds yield polynomial-time robust mean estimation with error Om(Bmε1−1/m).

    Source: §1 · p. 3

    The overview assumes bounded support for simplicity, but Section 4 removes this assumption.

    Source: §1.4 · p. 5

Abstract

from arXiv · show

We prove that for every isotropic log-concave distribution $P$ on $\mathbb{R}^d$ and every even $m\ge2$, the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares, where $C>0$ is a universal constant. This improves on the Poincar\'e-dependent bounds (Kothari and Steinhardt, 2017), recovering the optimal moment bounds for log-concave distributions. As an immediate corollary, we obtain computationally efficient algorithms with dimension-free error guarantees for a wide range of statistical estimation problems. Our proof proceeds by using stochastic localization to decompose $P$ as an average of strongly log-concave measures, whose centered moments admit the subgaussian certificates (Diakonikolas et al., 2025). With a covariance-adapted choice of localization, we show that a fourth-moment certificate derived from the variance inequality for quadratic forms (Letwin, 2026) suffices to control this averaging at every even degree.

1 Introduction

The introduction presents degree-m SoS moment certificates for isotropic log-concave distributions, their extension to general covariance, applications to robust estimation, and the covariance-adapted stochastic-localization proof outline. It situates these results among prior SoS moment bounds and KLS, notes a limitation under the Small Set Expansion Hypothesis, and previews the paper’s organization.

1 Introduction

  • For robust mean estimation, a fourth-moment certificate gives error O(B4ε^(3/4)), versus O(B2√ε) from the covariance bound, motivating certificates with universal-constant loss.Certifiable moment bounds enable low-degree SoS estimation algorithms; matching the information-theoretic guarantee requires controlling the certified moment scale.Source: §1 · p. 3

1.1 Main Results

  • Every isotropic log-concave distribution is (Cm, m)-certifiably bounded for every even m ≥2, with universal C and no dimension dependence.This attains the optimal moment scale Bm = O(m), replacing the Poincaré-based scale Bm = O((log d)^(1/4)).Source: §1.1 · pp. 3–4

1.2 Certifiable Hypercontractivity

  • Every log-concave distribution is (Cm, m)-certifiably hypercontractive for every even m ≥2, with the same universal C as in Theorem 1.3.Centering and whitening on the span of the centered support identify hypercontractivity with boundedness and certifiable boundedness.Source: §1.2 · p. 4

1.3 Algorithmic Applications

  • For every fixed γ > 0, an algorithm on corrupted samples achieves Oγ(ε^(1−γ)) errors for robust mean and covariance estimation in polynomial time.The mean guarantee is in Mahalanobis norm, and covariance error is measured in relative spectral norm.Source: §1.3 · pp. 4–5

1.4 Overview of Techniques

  • For higher moments, the prior Poincaré iteration leaves a factor σ^(2k−4), so dimension-free certificates by that route require the Poincaré bound conjectured by KLS.The iteration applies Poincaré k−2 times to reduce the problem to centered quadratic entries.Source: §1.4 · p. 5

A Random Decomposition

  • Covariance-adapted localization makes directional variances control both centered moments and means; multiplying a fourth-moment certificate by powers of a nonnegative quadratic form lifts it to degree 2k.Stochastic localization decomposes the original distribution into strongly log-concave measures whose moments can be certified and averaged.Source: A Random Decomposition · pp. 6–7

1.5 Related and Prior Work

  • After earlier certificates for product, rotationally invariant subgaussian, and Poincaré distributions, Theorem 1.3 answers Diakonikolas, Hopkins, Pensia, and Tiegel's [DHPT25] question with certificates for log-concave distributions.Source: §1.5 · p. 7
  • For isotropic log-concave distributions, Hopkins and Tiegel obtain O(md^1/4−1/(2m)), versus Theorem 1.3’s O(m), from a single order-m moment bound.Their result gives degree-O(m) SoS certificates for every (Bm, m)-bounded distribution and the same guarantee for hypercontractive moment bounds.Source: §1.5 · p. 8
  • Under the Small Set Expansion Hypothesis, the theorem cannot extend to all distributions satisfying only a fixed number of moment bounds.Constant-factor approximation of moment-tensor injective norms remains hard even for distributions with subgaussian moment bounds up to any fixed order [BBHKSZ12].Source: §1.5 · p. 8
  • The theorem unconditionally establishes a consequence of KLS, but its linear-projection moment certificates do not yield variance bounds for general nonlinear functions.For isotropic log-concave measures, KLS is equivalent to a dimension-free variance bound for every 1-Lipschitz function; the authors report no improvement to known KLS bounds from their result.Source: §1.5 · p. 8
  • The paper develops background in Section 2, proves the localization transfer theorem in Section 3, and uses it to prove Theorem 1.3 in Section 4.Appendices A and B provide further SoS and stochastic-localization details, while Appendix C explains applications to robust mean and covariance estimation.Source: §1.5 · p. 8

2 Preliminaries

The preliminaries set the notation for sum-of-squares proofs and collect the moment and variance bounds used later. Strong log-concavity supplies certifiable subgaussian moments, while a variance bound for quadratic forms provides a separate input for controlling covariance fluctuations.

2 Preliminaries

  • The notation distinguishes operator and Hilbert–Schmidt norms, orders symmetric matrices by positive semidefiniteness, and treats polynomial expectations coefficientwise.For stochastic localization, E_pt integrates under the current density and E_W averages over Brownian motion.Source: §2 · p. 8

2.1 Sum-of-Squares Proofs and Certificates

  • A degree-t sum-of-squares implication represents each target inequality using sums of squares whose summands have degree at most t.The notation also expresses polynomial upper bounds by certifying that the difference is nonnegative in the sum-of-squares proof system.Source: §2.1 · pp. 8–9

2.2 Moment and Variance Bounds

  • Every s-subgaussian distribution is (C_sg s√m, m)-certifiably bounded for even m ≥ 2, and strongly log-concave distributions provide such subgaussian moment bounds.Every 1-strongly log-concave distribution is 1-subgaussian; the matrix-parameter version gives a degree-2k certificate for B-strongly log-concave distributions by a linear change of variables.Source: §2.2 · p. 9
  • A variance bound for quadratic forms under isotropic log-concave distributions is used to control covariance fluctuations and derive a fourth-degree certificate.The cited result is Letwin’s variance bound.Source: §2.2 · p. 9

3 Moment Certificates via Stochastic Localization

The section transfers certificates from strongly log-concave distributions to isotropic log-concave distributions with an O(k) loss at degree 2k. A fourth-moment certificate controls covariance fluctuations during stochastic localization, enabling the transfer.

3 Moment Certificates via Stochastic Localization

  • Theorem 3.1 transfers (Lk, 2k)-certifiability for 1-strongly log-concave distributions to (4ekLk, 2k)-certifiability for compactly supported isotropic log-concave densities.The transfer holds for every T > 0.Source: §3 · p. 10

3.1 Fourth-Degree Certificates

  • An isotropic log-concave vector has a fourth-moment certificate, and its law is (3, 4)-certifiably bounded.The proof uses Letwin’s variance bound for quadratic forms.Source: §3.1 · p. 10

3.2 The Random Reweighting

  • Stochastic localization represents a log-concave density as an average of strongly log-concave densities, with covariance-adapted inverse-covariance control.The covariance evolution’s stochastic part involves the third centered-moment tensor; the fourth-moment certificate controls the relevant covariance fluctuations.Source: §3.2 · pp. 10–11

3.3 Certifying the Covariance Tensor Powers

  • A degree-four certificate for covariance fluctuations can be multiplied by (v⊤Atv)^(k−2) and averaged to obtain a degree-2k certificate for the covariance tensor powers.The argument applies Itô’s formula to (v⊤Atv)^k and uses the covariance-fluctuation bound.Source: §3.3 · pp. 11–12

3.4 Bounds on the Mean and B−1

  • The proof bounds moments of the localization mean using the covariance tensor-power bounds, and controls B−1 through the time integral of v⊤Atv.These inequalities have degree-2k certificates.Source: §3.4 · pp. 12–13

3.5 Averaging the Certificates

  • Averaging the centered strongly log-concave certificates with the mean bounds yields the degree-2k certificate for the original density.Choosing T = 1/[4(k−1)] gives the transfer bound asserted in Theorem 3.1.Source: §3.5 · p. 13

4 Certifiable Moments of Log-Concave Distributions

The paper establishes certifiable moment bounds for isotropic log-concave distributions at every even degree. It obtains them by applying the localization transfer to strongly log-concave moment certificates.

4 Certifiable Moments of Log-Concave Distributions

  • Every isotropic log-concave distribution P on R^d is (Cm, m)-certifiably bounded for all even m ≥ 2, with universal C > 0.The proof reduces to compactly supported distributions and applies Theorem 3.1 to the strongly log-concave certificate bound.Source: §4 · p. 14

A Sum-of-Squares Toolkit

The appendix records polynomial inequalities and closure properties used to average moment certificates; certificates are unconstrained unless stated otherwise.

A Sum-of-Squares Toolkit

  • The appendix’s toolkit collects polynomial inequalities and closure properties for averaging moment certificates, with certificates unconstrained unless stated otherwise.Source: A Sum-of-Squares Toolkit · p. 17

A.1 Basic Sum-of-Squares Facts

This subsection lists basic sum-of-squares facts used in the paper, including spectral comparison, Young’s inequality, Jensen’s inequality, and the even-power triangle inequality.

A.1 Basic Sum-of-Squares Facts

  • Spectral comparison gives a polynomial inequality when real symmetric matrices satisfy M ⪯ N.The fact applies to polynomial vectors z(v) of degree at most r.Source: §A.1 · p. 17
  • Young’s inequality bounds 2k a^(k−1)b by (k−1)a^k + b^k for nonnegative quadratic forms and integer k ≥ 2.Source: §A.1 · p. 17
  • Jensen’s inequality bounds the kth power of an average of nonnegative quadratic forms by the average of their kth powers.The stated fact assumes integrable coefficients of the kth powers.Source: §A.1 · p. 17
  • The subsection also lists the even-power triangle inequality for pairs of linear forms.Source: §A.1 · p. 17

A.2 Projection onto Linear Functions

This appendix establishes a projection bound and gives tools for preserving sum-of-squares structure under averaging and integration. The arguments use closure and convexity of the sum-of-squares cone.

A.2 Projection onto Linear Functions

  • For isotropic Y with finite fourth moments, the projection-bound proof expresses the relevant expectation as a degree-four sum of squares.For fixed Y, the integrand is the square of a quadratic form in u.Source: §A.2 · p. 17

A.3 Averaging and Limits

  • In a fixed number of variables, coefficientwise limits and integrable averages of sum-of-squares polynomials of degree at most 2k remain in the cone.The proof uses closedness and convexity of the cone.Source: §A.3 · p. 18

A.4 Integrating Polynomial Differential Inequalities

  • A polynomial differential inequality can be integrated with a positive integrating factor while preserving sum-of-squares structure.The proof averages the integrating-factor identity with a positive weight and applies the averaging lemma.Source: §A.4 · p. 18

B Stochastic Localization

This section records remaining properties of the process in Definition 3.5 and proves Fact 3.6.

B Stochastic Localization

B.1 Density Evolution and Averaging

The density evolution yields strongly log-concave measures at positive times and an averaging identity. The process also preserves the expected measure for bounded test functions.

B.1 Density Evolution and Averaging

  • For t > 0, the density p_t is B_t-strongly log-concave.The density formula represents it as a log-concave right-hand side, establishing the stated strong log-concavity.Source: §B.1 · p. 19
  • The density equation gives the averaging identity used in the proof of Theorem 3.1.Source: §B.1 · p. 19
  • For measurable f bounded on the support of p_0, E[p_t f] is a square-integrable martingale.The proof obtains a local martingale after stopping and uses the bound |E[p_t f]| ≤ ||f||_L∞(p_0).Source: §B.1 · p. 19

B.2 Mean and Covariance Equations

The appendix gives mean and covariance evolution facts and justifies exchanging expectation with time integration in moment equations. It also constructs compactly supported isotropic log-concave approximations that converge on polynomial expectations.

B.2 Mean and Covariance Equations

  • Bounds on the moment-equation drift and Brownian coefficients make finite-interval stochastic integrals square-integrable with mean zero, allowing expectation to commute with time integration coefficientwise.Source: §B.2 · p. 20

B.3 Truncation and Affine Normalization

  • Every isotropic log-concave X admits compactly supported isotropic log-concave approximations Y_R whose polynomial expectations converge to those of X.The construction conditions on ||X||_2 ≤ R, then recenters and applies covariance normalization; conditioning on a convex set and affine maps preserve log-concavity.Source: §B.3 · pp. 20–21

C Outlier-Robust Mean and Covariance Estimation

The section gives an outlier-robust procedure for estimating a log-concave distribution’s mean and covariance from an adversarially corrupted sample. It uses moment constraints to compare candidate clean samples, then strengthens those constraints with sum-of-squares certificates for efficient estimation.

Strong Contamination Model

  • The estimator models corruption by allowing an adversary to replace at most εn points after seeing the clean sample, without revealing which points were replaced.The target is simultaneous estimation of the mean and covariance.Source: C Outlier-Robust Mean and Covariance… · p. 21

Corollary 1.6

  • With even m ≥ 4 and m^2ε^(1−2/m) ≤ c′, the algorithm estimates the mean and covariance from an ε-corrupted log-concave sample with probability at least 0.9.The theorem assumes ε < c and a sample size n ≥ (md/ε)^{C0m}.Source: C Outlier-Robust Mean and Covariance… · p. 21
  • Covariance estimation achieves (1−δ)Σ ⪯ bΣ ⪯ (1+δ)Σ for δ ≲ m^2ε^(1−2/m).The target errors are mean error in Mahalanobis norm and covariance error in relative spectral norm.Source: C Outlier-Robust Mean and Covariance… · p. 21
  • For fixed m, sample complexity and runtime are polynomial in d and 1/ε; choosing m = Θ(log(1/ε)) yields errors O(ε log(1/ε)) and O(ε log^2(1/ε)) with quasipolynomial complexity.These guarantees hold for sufficiently small ε.Source: C Outlier-Robust Mean and Covariance… · p. 21

Proof sketch

  • A candidate clean sample must satisfy directional moment bounds for every v and even degree, with bounds relative to its own empirical covariance.This makes the constraints usable when the population covariance is unknown.Source: C Outlier-Robust Mean and Covariance… · pp. 21–22
  • The comparison controls mean and covariance errors by exploiting that candidate samples differ only on a small set, then applies degree-ℓ SoS certificates to make the constraints efficiently enforceable.The covariance comparison uses pairwise differences; the semidefinite relaxation yields estimates satisfying the stated bounds.Source: C Outlier-Robust Mean and Covariance… · p. 22
Loading 2609.30105v2…