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

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

503 citations recorded by the source corpus.

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 l_1 minimization method for identifying a sparse vector from random linear measurements. Indeed, the l_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.

Subfields: Applied Mathematics, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/ee0ef3003597a86280bbbb5df4beb12f041831bf

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Tradeoffs Between Convergence Speed and Reconstruction Accuracy in Inverse Problems (2016, unknown): “There is a series of works, which developed convergence and reconstruction guarantees for various methods based on ωC [23], [54], [55], and others that rely on ωK [56], [57].”
Learning Compact Neural Networks with Regularization (2018, background): “Gaussian width is frequently utilized in statistics and optimization community to capture the degrees of freedom of the problem [2, 8, 39].”
Randomized sketches for kernels: Fast and optimal non-parametric regression (2015, result): “Our definition of the statistical dimension may differ from some others in the literature, such as the one for cones in [3].”
Learning ReLUs via Gradient Descent (2017, background): “We note that n0 is exactly the minimum number of samples required for structured signal recovery from linear measurements when using convex regularizers [3, 1].”
Beta polytopes and Poisson polyhedra: f-vectors and angles (2018, background): “We remark that the above sums only contain finitely many non-zero terms and that the Grassmann angles were called the half-tail functionals in [4].”
Nonparametric Shape-Restricted Regression (2017, background): “sart-generic ver. 2014/10/16 file: ShapeRegArxiv.tex date: November 13, 2019 A. Guntuboyina and B. Sen/Shape-restricted Regression 18 has been termed the statistical dimension of Kby Amelunxen et al. [2]. Therefore, when Z˘ N n(0;I n),inequality (33) bounds the risk R(;^ ) of the LSE via the statist”
Sharp oracle inequalities for Least Squares estimators in shape restricted regression (2015, background): “The survey [1] provides general recipes to bound from above the statistical dimension of cones of several types.”
Optimal rates of statistical seriation (2016, methodology): “, [17]) of Θ defined by IE[supθ∈Θ〈θ, z〉], whose connection to the statistical dimension was studied in [1].”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “Amelunxen et al. (2014, Rem. 2.9) seem to have been the first to recognize that Gordon’s minimax theorem can be reversed in the presence of convexity. A substantial refinement of this observation appeared in Thrampoulidis et al. (2014). There is a long series of follow-up works by Babak Hassibi’s gr”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, background): “Alternatively, the logarithm of the determinant is a nonconvex, but smooth, proxy for rank when X is positive semideﬁnite (and can be applied to general matrices by embedding them in a PSD matrix).”
Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy? (2015, background): “Therefore, the deeper the network the stronger the shrinkage we get.”