An official website of the United States government
Given independent standard Gaussian points v1, . . . , vn in dimension d, for what values of (n, d) does there exist with high probability an origin-symmetric ellipsoid that simultaneously passes through all of the points? This basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. Based on strong numerical evidence, Saunderson, Parrilo, and Willsky (Saunderson, 2011; Saunderson et al., 2013) conjectured that the ellipsoid fitting problem transitions from feasible to infeasible as the number of points n increases, with a sharp threshold at n ∼ d^2/4. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some n = d^2/polylog(d). Our proof demonstrates feasibility of the least squares construction of (Saunderson, 2011; Saunderson et al., 2013) using a convenient decomposition of a certain non-standard random matrix and a careful analysis of its Neumann expansion via the theory of graph matrices.
more »
« less
This content will become publicly available on February 18, 2026
Youden's demon is Sylvester's problem
Abstract If four people with Gaussian‐distributed heights stand at Gaussian positions on the plane, the probability that there are exactly two people whose height is above the average of the four is exactly the same as the probability that they stand in convex position; both probabilities are . We show that this is a special case of a more general phenomenon: The problem of determining the position of the mean among the order statistics of Gaussian random points on the real line (Youden's demon problem) is the same as a natural generalization of Sylvester's four point problem to Gaussian points in . Our main tool is the observation that the Gale dual of independent samples in itself can be taken to be a set of independent points (translated to have barycenter at the origin) when the distribution of the points is Gaussian.
more »
« less
- Award ID(s):
- 2042428
- PAR ID:
- 10573119
- Publisher / Repository:
- Oxford University Press (OUP)
- Date Published:
- Journal Name:
- Mathematika
- Volume:
- 71
- Issue:
- 2
- ISSN:
- 0025-5793
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
A set of high dimensional points X ={x1,x2,…,xn}⊆Rd in isotropic position is said to be δ -anti concentrated if for every direction v, the fraction of points in X satisfying |⟨xi,v⟩|⩽δ is at most O(δ). Motivated by applications to list-decodable learning and clustering, three recent works [7], [44], [71] considered the problem of constructing efficient certificates of anti-concentration in the average case, when the set of points X corresponds to samples from a Gaussian distribution. Their certificates played a crucial role in several subsequent works in algorithmic robust statistics on list-decodable learning and settling the robust learnability of arbitrary Gaussian mixtures. Unlike related efficient certificates of concentration properties that are known for wide class of distri-butions [52], the aforementioned approach has been limited only to rotationally invariant distributions (and their affine transformations) with the only prominent example being Gaussian distributions. This work presents a new (and arguably the most natural) formulation for anti- concentration. Using this formulation, we give quasi-polynomial time verifiable sum-of-squares certificates of anti-concentration that hold for a wide class of non-Gaussian distributions including anti-concentrated bounded product distributions and uniform distributions over Lp balls (and their affine transformations). Consequently, our method upgrades and extends results in algorithmic robust statistics e.g., list-decodable learning and clustering, to such distributions. As in the case of previous works, our certificates are also obtained via relaxations in the sum-of-squares hierarchy. However, the nature of our argument differs significantly from prior works that formulate anti-concentration as the non-negativity of an explicit polynomial. Our argument constructs a canonical integer program for anti-concentration and analysis a SoS relaxation of it, independent of the intended application. The explicit polynomials appearing in prior works can be seen as specific dual certificates to this program. From a technical standpoint, unlike existing works that explicitly construct sum-of-squares certificates, our argument relies on duality and analyzes a pseudo-expectation on large subsets of the input points that take a small value in some direction. Our analysis uses the method of polynomial reweightings to reduce the problem to analyzing only analytically dense or sparse directions.more » « less
-
Abstract We classify the extreme points of a polytope of probability distributions in the (2,2,2) CHSH-Bell setting that is induced by a single Tsirelson bound. We do the same for a class of polytopes obtained from a parametrized family of multiple Tsirelson bounds interacting non-trivially. Such constructions can be applied to device-independent random number generation using the method of probability estimation factors (2018 Phys. Rev. A98040304(R)). We demonstrate a meaningful improvement in certified randomness applying the new polytopes characterized here.more » « less
-
Abstract We prove that among all 1-periodic configurations $$\Gamma $$ of points on the real line $$\mathbb{R}$$ the quantities $$\min _{x \in \mathbb{R}} \sum _{\gamma \in \Gamma } e^{- \pi \alpha (x - \gamma )^{2}}$$ and $$\max _{x \in \mathbb{R}} \sum _{\gamma \in \Gamma } e^{- \pi \alpha (x - \gamma )^{2}}$$ are maximized and minimized, respectively, if and only if the points are equispaced and whenever the number of points $$n$$ per period is sufficiently large (depending on $$\alpha $$). This solves the polarization problem for periodic configurations with a Gaussian weight on $$\mathbb{R}$$ for large $$n$$. The first result is shown using Fourier series. The second result follows from the work of Cohn and Kumar on universal optimality and holds for all $$n$$ (independent of $$\alpha $$).more » « less
-
ABSTRACT There are a number of hypotheses underlying the existence of adversarial examples for classification problems. These include the high‐dimensionality of the data, the high codimension in the ambient space of the data manifolds of interest, and that the structure of machine learning models may encourage classifiers to develop decision boundaries close to data points. This article proposes a new framework for studying adversarial examples that does not depend directly on the distance to the decision boundary. Similarly to the smoothed classifier literature, we define a (natural or adversarial) data point to be (γ, σ)‐stable if the probability of the same classification is at least for points sampled in a Gaussian neighborhood of the point with a given standard deviation . We focus on studying the differences between persistence metrics along interpolants of natural and adversarial points. We show that adversarial examples have significantly lower persistence than natural examples for large neural networks in the context of the MNIST and ImageNet datasets. We connect this lack of persistence with decision boundary geometry by measuring angles of interpolants with respect to decision boundaries. Finally, we connect this approach with robustness by developing a manifold alignment gradient metric and demonstrating the increase in robustness that can be achieved when training with the addition of this metric.more » « less
