PaperlayerView exact revision on arXiv

Source-linked AI summary

Living on the edge: Phase transitions in convex programs with random data

Dennis Amelunxen, Martin Lotz, Michael B. McCoy, Joel A. Tropp

arXiv:1303.6672v2cs.IT

TL;DR

The paper addresses why random convex optimization problems exhibit sharp success transitions and how to predict their location and width. It develops conic-geometric tools centered on statistical dimension and intrinsic-volume concentration, yielding probability bounds for random cone intersections. These results cover random inverse, demixing, and cone-program settings, with transition-width analysis more limited for two cones.

  • Problem

    A complete explanation of phase-transition phenomena in random convex optimization, including their location and width, was lacking despite extensive research.

  • Method

    The paper uses conic geometry, introducing statistical dimension and proving concentration of a cone’s intrinsic volumes around their mean.

  • Results

    The analysis gives sharp transition behavior for random subspace–cone intersections and cone–cone ray-sharing probabilities, governed by statistical dimensions and related geometric quantities.

  • Takeaways & Limitations

    The framework provides a geometric account of phase transitions across random linear inverse problems, demixing problems, and random cone programs.

  • Takeaways & Limitations

    For two cones, the transition width is bounded only by the larger of the two relevant transition-width quantities.

Abstract

from arXiv · show

Recent research indicates that many convex optimization problems with random constraints exhibit a phase transition as the number of constraints increases. For example, this phenomenon emerges in the $\ell_1$ minimization method for identifying a sparse vector from random linear measurements. Indeed, the $\ell_1$ approach succeeds with high probability when the number of measurements exceeds a threshold that depends on the sparsity level; otherwise, it fails with high probability. This paper provides the first rigorous analysis that explains why phase transitions are ubiquitous in random convex optimization problems. It also describes tools for making reliable predictions about the quantitative aspects of the transition, including the location and the width of the transition region. These techniques apply to regularized linear inverse problems with random measurements, to demixing problems under a random incoherence model, and also to cone programs with random affine constraints. The applied results depend on foundational research in conic geometry. This paper introduces a summary parameter, called the statistical dimension, that canonically extends the dimension of a linear subspace to the class of convex cones. The main technical result demonstrates that the sequence of intrinsic volumes of a convex cone concentrates sharply around the statistical dimension. This fact leads to accurate bounds on the probability that a randomly rotated cone shares a ray with a fixed cone.

1. MOTIVATION

Random convex programs can change sharply from likely failure to likely success as problem parameters vary. This paper seeks a geometric explanation and rigorous predictions for the transition’s existence, location, and width.

  • Phase transitions are sharp changes in computational behavior as problem parameters vary, and they appear in many random convex optimization problems.
  • Compressed sensing: Compressed sensing illustrates the phenomenon: ℓ1 minimization uses sparse structure to recover an unknown vector from fewer measurements than its ambient dimension.The measurements have the form z0 = Ax0, with A an m × d random Gaussian matrix.
  • Compressed sensing: Experiments vary sparsity s and measurements m to estimate ℓ1 recovery success, with brightness encoding empirical probability across ambient dimensions d = 100 and d = 600.The estimates use 50 independent trials for each parameter pair.
  • Open questions: The motivating questions concern whether a separating curve exists, where the success threshold lies, how probable success is, and how wide the transition region becomes.
  • Open questions: Despite extensive prior research, a complete explanation was lacking; the paper aims to explain these transitions geometrically and extend the reasoning beyond compressed sensing.

2. CONIC GEOMETRY AND PHASE TRANSITIONS

The paper develops conic-geometric tools showing that statistical dimension governs phase transitions across random convex optimization problems. Its results cover inverse problems, demixing, cone programs, and foundational properties of convex cones.

  • Foundational conic geometry: Intrinsic volumes of every closed convex cone concentrate sharply around their mean, the statistical dimension.This concentration is the paper’s main technical achievement.
  • Foundational conic geometry: The statistical dimension canonically extends linear-subspace dimension to convex cones and provides an approximate dimension for conic integral geometry.The paper also connects it with metric characterizations and Gaussian width.
  • Linear inverse problems: The inverse-problem transition changes from failure to success across a narrow measurement range, while the theoretical prediction closely matches empirical success isoclines.The paper notes that a more detailed kinematic result is needed to predict tapering near plot corners.
  • Foundational conic geometry: The approximate kinematic formula bounds when a randomly rotated cone shares a ray with a fixed cone using the cones’ total statistical dimension.Two randomly rotated cones are likely to share a ray when their total statistical dimension exceeds the ambient dimension.
  • Linear inverse problems: Regularized linear inverse problems with random measurements exhibit a phase transition at the statistical dimension of the descent cone.The success condition is geometrically equivalent to the descent cone and the measurement null space not sharing a ray.
  • Convex demixing: Under a random incoherence model, convex demixing exhibits a phase transition controlled by the total statistical dimension of two descent cones.The theoretical transition curve again closely matches the empirical 50% success isocline, with corner tapering requiring additional analysis.
  • Further applications: The framework extends to cone programs with random affine constraints, whose transition can be predicted from the statistical dimension of the cone.This result is stated as Theorem 8.1.
  • Further applications: The paper supplies a recipe for estimating descent-cone statistical dimensions and proves that the resulting errors are negligible for important cone families.These estimates rigorously explain why earlier Gaussian-width-based calculations closely matched observed transitions.

3. CALCULATING THE STATISTICAL DIMENSION

This section develops the statistical dimension as a cone analogue of linear dimension and gives equivalent formulations, structural laws, and calculations for representative cones.

  • Basic properties: The statistical dimension has intrinsic, Gaussian, spherical, polar, and mean-squared-width formulations, and is invariant under cone orientation.It equals the dimension on subspaces and obeys complementarity and direct-product laws.
  • Basic examples: For a self-dual cone in R^d, the statistical dimension equals d/2.This follows from rotational invariance and complementarity.
  • Permutahedra: The normal cone of the signed permutahedron does not depend on its generator when the generator entries are distinct.The figure compares generators (3,−1) and (3,−2).
  • Circular cones: Circular-cone statistical dimensions admit accurate asymptotic expressions, with an error term approximately equal to cos(2α).The formula remains an excellent approximation in moderate dimensions.
  • Permutahedra: For a vector with distinct entries, the normal cone at a signed permutahedron vertex has an exact statistical-dimension formula.The calculation connects conic geometry with classical combinatorics and supports a signal-processing application.

4. THE STATISTICAL DIMENSION OF A DESCENT CONE

The section gives a recipe for estimating descent-cone statistical dimensions through subdifferentials and establishes error bounds that support phase-transition calculations.

  • General recipe: The descent-cone recipe minimizes an auxiliary function J by solving its stationary equation, then uses the minimizer to estimate statistical dimension.The approach applies under stated subdifferential regularity assumptions.
  • General recipe: The function J is strictly convex, continuous at zero, differentiable for nonnegative τ, and has a unique minimizer.These analytic properties underpin the recipe.
  • Error control: Theorem 4.3 supplies an error estimate explaining why the descent-cone recipe gives accurate upper bounds for norms.The estimate is essential for calculating statistical dimensions correctly when locating phase transitions.
  • Limitations: An optimal error estimate for the descent-cone recipe remains open because existing bounds operate under different assumptions and regimes.The comparison concerns the bounds of this paper and Foygel & Mackey.
  • Applications: For the ℓ1 norm at an s-sparse vector, the resulting bounds provide the exact phase-transition location in high-dimensional Gaussian inverse problems.The error is vanishing relative to ambient dimension when s is proportional to d.
  • Applications: For the Schatten 1-norm at a low-rank matrix, the statistical dimension has an asymptotically exact expression that identifies the phase-transition location.This result applies as the ambient dimension tends to infinity.

5. CONIC INTEGRAL GEOMETRY AND THE STATISTICAL DIMENSION

This section develops conic integral geometry and shows that intrinsic volumes provide rotation-invariant geometric data from which statistical dimension can be characterized and computed.

  • Foundations: Conic integral geometry answers questions about distances to cones and ray intersections after random rotation using conic intrinsic volumes.These invariants remain relevant under rotations, reflections, and embeddings.
  • Intrinsic volumes: In two dimensions, a cone with solid angle α has intrinsic volumes v2(C)=α/(2π), v1(C)=1/2, and v0(C)=(π−α)/(2π).The three values correspond to the two-dimensional face, boundary rays, and origin.
  • Intrinsic volumes: For polyhedral cones, intrinsic volumes are probabilities that the projection of a standard normal vector lies in a k-dimensional face.They form a probability distribution over dimensions 0 through d.
  • Intrinsic volumes: Intrinsic volumes extend from polyhedral to general closed convex cones by approximation in the conic Hausdorff metric, independently of the approximating sequence.The spherical Steiner formula provides an alternative interpretation.
  • Kinematic formula: The conic kinematic formula gives the exact probability that a randomly rotated cone shares a ray with a fixed cone using intrinsic-volume data.In d dimensions, each cone is summarized by d+1 numbers.
  • Canonical extension: Statistical dimension is the unique continuous, rotation-invariant, localizable valuation extending linear dimension from subspaces to closed convex cones.It also has equivalent characterizations developed through the spherical Steiner formula.

6. INTRINSIC VOLUMES CONCENTRATE AT THE STATISTICAL DIMENSION

The intrinsic volumes of a closed convex cone concentrate near its statistical dimension, producing a sharp transition whose width depends on intrinsic cone geometry.

  • Main concentration result: The intrinsic volumes concentrate near the cone’s statistical dimension over a transition width determined by the statistical dimension.Theorem 6.1 formalizes this concentration through tail-function bounds.
  • Transition behavior: The tail functionals drop from one to zero near δ(C), while intrinsic volumes are negligible except at indices close to δ(C).The transition spans O(ω(C)) indices.
  • Tail behavior: For sufficiently large deviations, the tail bounds first decay like a Gaussian tail and later like an exponential tail.The crossover occurs around λ≈4ω(C) and λ≈ω^2(C), respectively.
  • Proof intuition: Concentration of spherical projections and tropic functions explains why the transition occurs when the index k is approximately δ(C).Projection norms are typically close to δ(C)/d, while tropic functions switch near k=εd.
  • Proof strategy: The proof combines the spherical Steiner formula, projection tail bounds, and polarity to establish upper and lower bounds on the tail functionals.Polarity reverses intrinsic volumes and supplies the lower bound.

7. APPROXIMATE KINEMATIC BOUNDS

The paper derives approximate kinematic bounds showing that statistical dimension locates transitions in random cone intersections, while intrinsic-volume concentration controls their width.

  • 7. APPROXIMATE KINEMATIC BOUNDS: Theorem 7.1 uses intrinsic-volume concentration and the exact conic kinematic formula to obtain approximate intersection bounds.The proof combines the exact kinematic formula with concentration of intrinsic volumes.
  • 7.1. Discussion.: A random subspace is unlikely to share a ray with a fixed cone above codimension δ(C), and likely to do so below δ(C).The transition occurs when codimension changes by about ω(C).
  • 7.1. Discussion.: For two randomly oriented cones, intersection is unlikely when their total statistical dimension is below d and likely when it exceeds d.The bound follows from the conic kinematic formula, interlacing, and tail-functional estimates for cone products.
  • 7.1. Discussion.: The two-cone transition width is bounded by the larger of the cones’ parameters ω(C) and ω(K).The probability bounds depend on the sum of the two tail functionals, so the larger width controls the guarantee.
  • 7.2. Proof of Theorem 7.1.: The argument assumes the cones may be treated as closed because the relevant touching probability is unchanged by closure.This closure step relies on a subtle property of touching probabilities.

8. APPLICATION: CONE PROGRAMS WITH RANDOM CONSTRAINTS

Random cone programs undergo a feasibility transition governed by the cone’s statistical dimension: fewer constraints favor feasibility, while more constraints favor infeasibility. Numerical experiments with random second-order cone programs support this prediction.

  • 8.1. Cone programs.: Theorem 8.1 states that random affine constraints induce a phase transition in cone-program behavior at statistical dimension δ(C).The model fixes nonzero b and uses independent standard normal entries for u and A.
  • 8.1. Cone programs.: m ≥ δ(C)+λ implies infeasibility with probability at least 1−pC(λ).The complementary regime m ≤δ(C)−λ implies unboundedness with probability at least 1−pC(λ).
  • 8.1. Cone programs.: The intrinsic-volume identity P{(8.1) is unbounded}=tm+1(C) links cone-program behavior to tail functionals.These tail functionals are close to one below the statistical dimension and close to zero above it.
  • 8.2. Numerical examples.: For three cones in dimension d=396, the computed statistical dimensions are δ(C1)≈66.67, δ(C2)≈51.00, and δ(C3)≈35.50.The values are obtained using the product rule and numerical quadrature for circular-cone statistical dimensions.
  • 8.2. Numerical examples.: The empirical success curves and logistic fits compare closely with theoretical transition locations marked by δ(Ci).The experiment repeats random draws and CVX solutions 50 times for each cone and constraint count.

9. APPLICATION: VECTORS FROM LISTS?

For recovering a vector from its unordered entries and random linear measurements, the paper’s theory predicts a transition near the ambient dimension. Experiments confirm that distinct-entry vectors require nearly complete measurement information.

  • 9.1. Vectors from lists?: The theory gives a negative result: resolving the ordering uncertainty requires a near-complete set of linear measurements, though not all measurements are necessary.The paper identifies vectors with duplicated entries as an open direction for possible improvement.
  • 9.1. Vectors from lists?: The unordered-list inverse problem combines the sorted entries y0 with random measurements z0=Ax0 to recover x0.A convex regularizer based on the permutahedron exploits the information in y0.
  • 9.1. Vectors from lists?: For distinct entries, reliable recovery requires about d−1/2 Hd random measurements.This result applies to the proposed convex recovery method under standard normal measurement matrices.
  • 9.2. Numerical experiment.: For d=100, the predicted transition at statistical dimension d−Hd closely matches the empirical 50% success mark.The experiment uses 50 trials for each m from 85 through 100 and logistic regression to estimate the midpoint.

10. RELATED WORK

This section situates the paper among geometric, conic-integral, Gaussian-process, and statistical-decision approaches to phase transitions. It highlights broader applicability, sharper transition results, and a connection between statistical dimension and Gaussian width.

  • Research context: Prior work used polytope-angle calculations, conic integral geometry, Gaussian-process inequalities, and statistical decision theory to study random convex optimization.The paper traces four lines of thought and places its results in relation to them.
  • Compressed sensing literature: Earlier compressed-sensing analyses established weak and strong measurement thresholds, but some bounds lacked reliable evidence about the actual transition behavior.The cited work includes asymptotic lower bounds, numerical sharpness evidence, and unresolved questions about strong phase transitions.
  • Limitations of prior methods: Polytope-angle methods are limited to polyhedral cones, require detailed intrinsic-volume information, and rarely yield definitive zero-to-one transition statements.These limitations make many existing results asymptotic and difficult to extend beyond highly symmetric examples.
  • Extensions: The paper extends phase-transition analysis to weighted ℓ1, nonnegative ℓ1, ℓ∞-regularized, and strong-transition settings.The authors state that these extensions are accessible to their methods but omit the material for brevity.
  • Main conceptual connections: The analysis obtains failure conditions for random linear inverse problems and connects statistical dimension with Gaussian width as equivalent cone summary parameters.This connection bridges integral-geometric and Gaussian-process perspectives and is described as new even for ℓ1 minimization.
  • Minimax risk: Combining the paper’s theorem with Oymak and Hassibi’s result shows that minimax risk coincides with phase-transition location in some regularized random linear inverse problems.The supporting results apply under mild conditions on the regularizer and settle the cited conjecture nonasymptotically for many regularizers.

APPENDIX A. COMPUTER EXPERIMENTS

This appendix documents numerical experiments for compressed sensing and low-rank matrix recovery, together with computational procedures for evaluating statistical-dimension formulas. It also records numerical stability and experiment-specific issues.

  • Experimental setup: The experiments estimate empirical success probabilities for compressed sensing and low-rank matrix recovery using repeated random trials and convex optimization.The appendix states that the experiments use CVX with MATLAB’s default settings.
  • Compressed sensing: For compressed sensing, the procedure varies sparsity and measurements, draws Gaussian matrices, solves the ℓ1 program, and declares success when the reconstruction error is at most 10^-5.The d = 100 experiment repeats each setting 50 times; the d = 600 experiment uses a coarser grid.
  • Numerical reliability: The compressed-sensing probability estimates are supported by concentration, and success tolerances from 10^-3 through 10^-7 produce essentially the same results in limited tests.Numerical problems at d = 600 caused a few spurious failures in Figure 1.1[right].
  • Low-rank recovery: For low-rank recovery, the procedure samples rank-r matrices, applies Gaussian measurements, solves the recovery program, and repeats settings 50 times.The experiment fixes n = 30 and varies rank and measurement counts; an elementary degrees-of-freedom condition can declare failure directly.
  • Numerical evaluation: Statistical-dimension formulas for the ℓ1 and Schatten 1-norm descent cones are evaluated numerically by rootfinding monotone stationary equations and numerical integration.The implementation uses fzero for the stationary equations and erfc for the integral in the ℓ1 formula.
  • Numerical limitations: Evaluating the statistical-dimension formulas can become numerically unstable when proportional sparsity, proportional rank, or aspect ratio approaches zero or one.The appendix nevertheless reports that relatively simple code is usually reliable and provides software online.

B.4. Proof of Proposition 3.1.

This section verifies elementary properties of statistical dimension using Gaussian projections, spherical decomposition, polarity, orthogonal decomposition, and direct-product structure.

  • Equivalent formulations: The Gaussian formulation of statistical dimension follows from its intrinsic definition and expresses it through projection of a standard normal vector.The proof also derives a spherical formulation by writing g = Rθ with independent radial and spherical components.
  • Polarity: Polarity and the distance formula yield the complementarity identity relating the statistical dimensions of a cone and its polar.The argument uses the relation between projection onto a cone and distance to its polar.
  • Projection characterization: The supremum formulation follows from the Pythagorean decomposition and the defining inequality of the polar cone.Choosing the unit vector in the projection direction completes the characterization.
  • Invariance and products: Rotational invariance of the standard normal distribution establishes rotational invariance of statistical dimension.The direct-product rule follows because projection splits over products and orthogonal components of a Gaussian vector are independent.
  • Subspaces: For a subspace, projecting a standard normal vector produces a standard normal vector supported on that subspace, so expected squared projection norm equals subspace dimension.This establishes that statistical dimension extends ordinary dimension for linear subspaces.
  • Monotonicity: Polarity reverses inclusion, which yields monotonicity of statistical dimension through the polar-cone identities.The proof applies the polarity identity twice.

APPENDIX C. THEORETICAL RESULTS ON DESCENT CONES

This appendix develops the analytic machinery behind statistical-dimension calculations for descent cones. It establishes convexity, continuity, differentiability, and unique minimization properties for expected distances to dilated convex sets.

  • Purpose: The appendix proves Proposition 4.1 and Theorem 4.3, providing the theoretical basis for calculating statistical dimensions of descent cones.These results support the paper’s computational recipe for descent-cone dimensions.
  • Assumptions: The descent-cone analysis relies on subdifferentials that are nonempty, compact, convex, and exclude the origin.These hypotheses enable the abstract expected-distance lemma used in the proof.
  • Distance to dilated sets: For a compact convex set avoiding the origin, the distance-squared function to its dilation is convex and attains a minimum on a bounded interval.The bounded interval is controlled by the norm of the input and a positive lower bound on set radii.
  • Differentiability: The distance-squared function is continuously differentiable, with its derivative obtained from projection and squared-distance formulas.Continuity of projections and a right derivative at zero complete the regularity argument.
  • Technical control: Projection nonexpansiveness supplies derivative bounds and Lipschitz control needed for the analytic results.The proof derives the bounds from projection optimality and the nonexpansiveness of I−πτS.
  • Expected distances: Expected distance to a dilated compact convex set is convex, continuous at zero, differentiable, and strictly convex under the stated assumptions.Strict convexity implies a unique minimizer.

C.2. Error bound for descent cone calculations.

The section derives an error bound by analyzing minimizers of convex functions and controlling Gaussian fluctuations through Lipschitz variance estimates. It then applies the bound to compute statistical dimensions for ℓ1 descent cones.

  • C.2. Error bound for descent cone calculations.: Gaussian Poincaré variance bounds and nonexpansiveness of projections control the fluctuations of selected minimizers and complete inequality (4.3).The minimizer selection uses the cone K := cone(S) and projection ΠK(u).
  • C.2. Error bound for descent cone calculations.: Theorem 4.3 provides an error bound for Proposition 4.1 by comparing expected random minima with the deterministic minimum.The proof seeks a reverse inequality to the upper bound supplied by Proposition 4.1.
  • C.2. Error bound for descent cone calculations.: Linearization around function minimizers, convexity, zero-mean terms, and Cauchy–Schwarz reduce the proof to estimating two error terms.The formulation enables variance control through Lipschitz properties of the relevant random variables.
  • ℓ1 descent cones.: The ℓ1 descent-cone calculation uses the subdifferential-distance bound and shows the resulting expression matches the upper bound in (4.4).The descent cone depends, up to isometry, only on the sparsity s, not on the nonzero magnitudes.
  • Schatten 1-norm descent cones.: The Schatten 1-norm calculation follows an analogous subdifferential-distance approach, with a nonasymptotic statistical-dimension bound and a stationary equation for its asymptotic expression.The supplied passages state that the low-rank calculation uses random matrix theory and that the normalized error converges to zero.

D.3. Descent cones of the Schatten 1-norm.

The section calculates the statistical dimension of Schatten 1-norm descent cones using subdifferential bounds and random matrix theory. The normalized error vanishes asymptotically under fixed-ratio growth, yielding the main asymptotic result.

  • Fixed-dimensional calculation: The descent cone of the Schatten 1-norm at a fixed low-rank matrix is analyzed with the same basic strategy as the ℓ1 descent-cone calculation.The proof uses classical random matrix theory to obtain the final expression and a sharp asymptotic estimate.
  • Fixed-dimensional calculation: The subdifferential bound reduces statistical dimension estimation to expected distances from a Gaussian matrix to dilated subdifferentials.The Gaussian matrix is partitioned conformally with the low-rank matrix, with G22 carrying the complementary block.
  • Asymptotic calculation: The exact formula is difficult to evaluate because it involves the joint singular-value density of a Gaussian matrix.The paper instead establishes a framework using classical random matrix theory for a sharp asymptotic result.
  • Asymptotic calculation: As r, m, and n grow with fixed ratios r/m = ρ and m/n = ν, a Marčenko–Pastur-law argument identifies the limiting expectation.Strict convexity supports convergence of the infimal values, beyond pointwise convergence alone.
  • Asymptotic calculation: The normalized statistical-dimension error is at most 2/(npmr) and converges to zero, producing the asymptotic result (4.7).The stationary equation (4.9) follows by differentiating the limiting objective and setting its derivative to zero.

E.2. Bounds for tropic functions.

The section bounds tropic functions by representing them through beta random variables and approximating their distributions. Gaussian exponential-moment bounds then yield projection-tail estimates and transition-width control.

  • Beta approximation: For the relevant beta distributions, the normal approximation satisfies P{X ≤ x} = Φ(y) + ε(x) with |ε(x)| ≤ 5·10^-3.Φ denotes the cumulative distribution of a standard normal random variable.
  • Beta approximation: The tropic function is represented as P{X < E[X]} for a beta random variable with E[X] = k/d.The proof seeks to show this probability is at most 0.7.
  • Beta approximation: The remaining parameter range is handled by separating large-dimension cases from d ≤ 12 and verifying the latter numerically.The numerical verification establishes a probability bound below 0.7 in the enumerated cases.
  • Gaussian bounds: Gaussian exponential-moment inequalities are applied to centered functions of a standard normal vector, including squared cone projections.For F(g) = ∥ΠK(g)∥2 − δ(K), the gradient satisfies ∥∇F(g)∥2 = 4∥ΠK(g)∥2.
  • Projection tails: Combining Laplace-transform bounds for a cone and its polar yields probability bounds whose transition width is identified as ω2(C).The proof uses the Pythagorean identity and complementarity law for the polar cone.
  • Product cones: For product cones, intrinsic-volume distributions become sums of independent variables, allowing tail functionals of the product to be bounded from those of the factors.The intrinsic-volume probabilities are represented as P{X = k} = vk(C) and P{Y = k} = vk(K).

APPENDIX F. STATISTICAL DIMENSION AND GAUSSIAN WIDTH

The appendix proves that statistical dimension and Gaussian width are closely related for convex cones. It establishes upper and lower bounds connecting δ(C) with w(C)^2.

  • Statistical dimension and Gaussian width: For a closed convex cone C, statistical dimension dominates the squared Gaussian width.The proof enlarges the supremum range and then applies Jensen’s inequality.
  • Statistical dimension and Gaussian width: The Gaussian-width supremum is 1-Lipschitz, so Gaussian variance control bounds its fluctuations around its expectation.The random variable is Z(g) := supy∈C∩Sd−1 〈y, g〉 and w(C) = EZ.
  • Statistical dimension and Gaussian width: The resulting estimate gives δ(C) ≤ w(C)^2 + 1 after identifying an expected squared projection with the statistical dimension.The identification uses the cone’s polar complement and the intrinsic formulation of statistical dimension.
Loading 1303.6672v2…