CS Paper Radar

Search Dimension in Unlabeled Projection Pursuit: A Scaling Law for Subspace Restriction

Rares Dimitrie Grozavescu, Mark Girolami

cs.LG math.STstat.ML ·submitted 2026-09-29 16:11 UTC · v1

Abstract

Projection pursuit searches for a direction along which the data look least Gaussian. When the observation space contains a large Gaussian complement, the empirical objective can be minimized by a direction that carries no signal, with empirical kurtosis as low as at the truth. Sample splitting exposes rather than repairs this failure. Appending coordinates independent of the latent regime degrades the search while leaving Bayes recoverability unchanged. Restricting the search to the column space of a known forward operator removes the failure exactly on the negative-kurtosis branch. Estimating a principal subspace from the data is the alternative. In a controlled two-component model, the leading sufficient scalings differ in the gain with which the operator transmits the discriminant: $ς^{-4}$ for covariance-spike estimation and $ς^{-8}$ for fourth-moment search. At fixed search dimension, the measured threshold ratio collapses onto $n/p^2$ with exponent $0.156$, close to the predicted $1/8$. This is an empirically supported scaling motivated by sufficient bounds, not a proved asymptotically tight law. When the search dimension is varied, the measured exponent is $0.325$, substantially larger than $1/8$, and the tested range does not identify its functional form. The crossing location also depends on calibration and model configuration. Under a downstream excess-error criterion, the scaling largely disappears.

Closest papers

Nearest neighbours by meaning across the whole index.

Algorithmic threshold for high-dimensional projection pursuit I: general theory

cs.CC math.PRcond-mat.dis-nnmath-ph ·2026-08-29 ·Brice Huang, Mark Sellke, Nike Sun
highly cited similarity 0.62
Abstract · 295 pages. All ideas in this paper are human-generated, and all the writing was done by the human authors. AI was used in the writing of thi…

We study a null model of high-dimensional projection pursuit: we are given $M$ points sampled i.i.d. from a standard gaussian in $N$ dimensions, where $M,N\to\infty$ with $M/N\toα\in(0,\infty)$. Our goal is to characterize the possible empirical distributions of these points' projections along a data-dependent direction $x$, which ranges over either the sphere $S_N=\sqrt{N}\mathbb{S}^{N-1}$ or cube $Σ_N=\{-1,+1\}^N$. We consider this problem in an algorithmic setting, where $x$ must be the output of an algorithm with dimension-free Lipschitz dependence on the input; this class of algorithms includes general gradient-based methods such as Langevin dynamics and approximate message passing (AMP). Our main result exactly characterizes the set of empirical distributions attainable by this class in terms of a one-dimensional stochastic control problem. As a consequence of our main result, we obtain exact algorithmic thresholds for optimizing the Hamiltonian of a spherical or Ising perceptron model with general bounded continuous activation. For the spherical problem, independent work of Montanari and Zhou (2024) characterized the empirical distributions attainable by a related two-stage AMP algorithm, also in terms of stochastic control. Our proof of hardness builds on the branching overlap gap property introduced in earlier work by the first two authors. Our main innovation is to develop stochastic control theory within the branching OGP framework, significantly expanding the settings in which it locates an exact algorithmic threshold. Notably, our methods apply even though the non-algorithmic problem of characterizing all feasible projections remains a major outstanding challenge. For the matching algorithmic result, we construct a new incremental AMP algorithm that acts on a Brownian-bridge revelation of the gaussian disorder and simulates the same family of controlled SDEs.

0.59

Inference and Uncertainty Quantification for Streaming $r$-PCA

cs.LG stat.ML ·2026-08-18 ·Haoshu Xu, Hongzhe Li
theory similarity 0.58
Abstract

We address two open questions in streaming PCA via Oja's algorithm: sharp operator-norm convergence for general rank under sub-Gaussian data, and distributional inference for the resulting subspace estimator. Existing convergence analyses, even in the rank-one case, either assume bounded data or leave non-vanishing remainder terms that prevent adaptation to a polynomially vanishing tail spectrum, while existing distributional results are confined to the rank-one case. Our convergence theory removes these remainder terms and yields a sharp rate. In the dense-tail spiked covariance regime, this rate matches the minimax rate up to logarithmic factors. More generally, we prove a matching lower bound, up to logarithmic factors, across both dense-tail and sparse-tail regimes under a mild nondegeneracy condition. The analysis yields a linearization of Oja's iterates, which in turn enables a high-dimensional Gaussian approximation for the general-rank subspace estimation error with an explicit limiting covariance. We also establish a row-wise Gaussian approximation over convex sets for the aligned difference, recovering prior rank-one results as special cases. For practical inference, we develop an online multiplier bootstrap algorithm and prove its consistency. Beyond streaming PCA, our techniques contribute to Gaussian approximation and bootstrap inference for nonconvex stochastic approximation.

0.42

Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails

cs.LG ·2026-09-03 ·Shi Fu, Huibo Xu, Qixin Zhang, Dacheng Tao
benchmark similarity 0.58
Abstract

Restricted eigenvalue (RE) bounds govern stable recovery by norm-regularized estimators. For isotropic sub-Gaussian measurements, the benchmark sample size is $1+w(A)^2$, where $w(A)$ is the Gaussian width of the normalized descent cone. The COLT 2015 open-problem note (Banerjee et al., 2015) asked whether the same law follows for heavy-tailed designs from a uniform small-ball condition alone. We give an explicit and systematic negative answer to the general question as formulated there: the proposed law fails in its full dimension-free, arbitrary-set form, and the missing obstruction is simultaneous threshold occupancy. A constant-width polyhedral descent cone with fixed small-ball constants has zero empirical RE on every sample path up to half the ambient dimension. More generally, every finite range space admits exact threshold encoding in an arbitrarily narrow spherical cap and a lift to a full polyhedral descent-cone section. For every fixed threshold VC dimension $d$, as $β\downarrow0$, the sharp worst-case sample complexity is $Θ(β^{-1}[d\log(1/β)+\log(1/δ)])$. The separation persists under exact isotropy and all finite moments: on the same constant-width cone, Gaussian measurements succeed with $O(1+\log(1/δ))$ samples, whereas an isotropic heavy-tailed design fails pathwise for $n\lesssim\sqrt{p/\log p}$. Gaussian smoothing yields an everywhere-positive $C^\infty$ density while retaining arbitrarily poor RE. Under isotropy, a distribution-free fallback governed by affine dimension times squared enclosing radius is sharp on this family.

0.27

Robust Latent Variable Graphical Models: Exact Recovery and Fundamental Limits

cs.IT stat.MLcs.LG ·2026-10-19 ·Chuansen Peng, Xiaojing Shen
theory similarity 0.57
Abstract

We study robust estimation of a Gaussian precision matrix that decomposes as a sparse matrix minus a symmetric, possibly indefinite, low-rank matrix, a structure that arises when latent-variable marginalization is combined with conditioning on linear measurements. The proposed convex estimator replaces the sample covariance by the centered Gaussian measure-transformed (MT) covariance, which preserves the signed graph of the sparse component under the nominal model, and penalizes the low-rank component by the nuclear norm of a congruence transform, an atomic norm that encodes structural side information. Our main result is a primal--dual witness theorem: under restricted invertibility and irrepresentability conditions on the Fisher information, the raw convex optimizer is unique, has no false edges, recovers the signs of all sufficiently strong edges, and has exactly the true rank and inertia. These conditions reduce to the graphical-lasso conditions when the low-rank part is absent, and we verify them from primitive incoherence and near-isotropy assumptions. Over a class on which they hold uniformly, we prove information-theoretic limits for Frobenius estimation, signed graph recovery, and inertia recovery. In particular, inertia recovery requires $N\gtrsim p/ν_{\min}^2$ samples, where $ν_{\min}$ is the smallest nonzero eigenvalue modulus of the low-rank part; the spectral beta-min condition of the witness theorem is necessary up to a $\sqrt{\log p}$ factor; and the Frobenius risk attains the minimax rate up to a factor $\sqrt{μ(1+\min\{d,r\})\log p}$, where $μ$ is the incoherence parameter, $d$ the maximal degree, and $r$ the rank. We further quantify robustness under Huber contamination, with a bias bound that is sharp for the MT functional and vanishes for remote outliers, and give a globally convergent linearized ADMM with closed-form updates.

0.23

Low-Rank Denoising for Predict-then-Optimize

cs.LG econ.EMmath.OCmath.SP ·2026-09-14 ·Henry Aldridge-Krawciw, Irene Aldridge
similarity 0.57
Abstract · 15 pages

A shortest-path decision is often made from edge costs that are only observed through noisy samples, such as the average of $m$ simulation replications. When the mean cost vectors of different instances lie near a $k$-dimensional subspace, projecting the averaged sample onto that subspace should remove noise. We make this precise. The mean squared error of any projection estimator splits exactly into a variance term and a bias term. The best projector is the positive eigenspace of $Σ_c - D/m$, where $Σ_c$ is the covariance of the true costs and $D$ is the noise covariance. For a rank-$k$ signal, the projection has the error of a sample mean with a factor $d/(μk)$ more replications, where $d$ is the number of edges and $μ$ is an incoherence constant. For a signal that is only approximately low-rank, every rank-$k$ projection has an error floor, and the plain average wins beyond an explicit replication count. A margin bound shows that the chance of choosing a suboptimal path falls at the same improved rate. A projector learned from $n$ noisy instances loses at most an $O(d/n)$ term.

0.32

Compact and Infinite-Order Error Analysis for Null-Space SVD Estimation

cs.LG math.ST ·2026-08-31 ·Xin Li, Jonathan Cohen, Rami Puzis
theory similarity 0.56
Abstract · 31 pages

We study null-space estimation from a noisy matrix. For a simple left null space, we first derive an exact compact expression for the error of the smallest left singular vector. We then give an all-order series for the SVD vector and projector, followed by compact and consistently truncated series forms for the fixed-realization empirical risk and conditional population generalization risk. The recursion extends to a multiple-dimensional null space by following the complete invariant subspace. The convergence radius is not inferred from an error plot: it is computed independently from the nearest complex exceptional point that joins a retained eigenvalue branch to its complement. A reduced-nullity experiment shows that moving this spectral boundary can increase the radius, although the improvement is not monotone in the retained nullity. For individually ordered null directions under Gaussian training with \(τ\geq m\), we prove that the Wishart splitting matrix \(W\) gives a strict second-order empirical ranking. Gaussian averaging equalizes the leading generalization risks at both small and very large noise, while a column-swap theorem proves strict expected generalization ranking for an isotropic signal subspace. For unequal spikes, an exact population-overlap criterion and a simultaneous \(99\%\) Monte Carlo confidence certificate explain the observed intermediate ranking. A sixth-order risk correction improves the lower-crossover estimate in the reported experiment. This equal--ranked--equal phenomenon is a finite-sample diagnostic related to spectral mixing, but its tolerance crossings, the exceptional-point radius, and the asymptotic BBP threshold are three distinct quantities.

0.38

Nuclear Norm-Regularized Bayesian Matrix Completion

cs.LG stat.ML ·2026-09-24 ·Calvin Tolbert
similarity 0.55
Abstract · 40 pages, 7 figures

Nuclear-norm-regularized least squares is a standard approach to matrix completion, but it yields only a point estimate. Its Bayesian counterpart, a prior combining the nuclear norm with a Frobenius-norm term, gives a strongly log-concave though nonsmooth posterior when the noise precision is known. In practice the precision is unknown, and placing a truncated Jeffreys prior on it makes the joint posterior neither log-concave nor smooth. To our knowledge, we give the first sampler for this model with an explicit non-asymptotic guarantee: its output is within a prescribed total-variation or Wasserstein distance of the posterior on the matrix after a number of steps polynomial in the matrix dimensions and the reciprocal of the target accuracy. The sampler never targets a continuous distribution that is not strongly log-concave. It discretizes the precision onto a grid, estimates its posterior by thermodynamic integration along the tilted conditional posteriors of the matrix, and bounds the error this propagates to the posterior on the matrix. The approach applies whenever non-log-concavity is confined to a bounded scalar hyperparameter and the conditional distributions are strongly log-concave with smooth-plus-Lipschitz potentials. Our result establishes feasibility; the polynomial complexity is not intended as a practical algorithm at current problem scales.

0.26

Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models

cs.LG cs.ITmath.NAmath.PR+1 ·2026-09-02 ·Piyush Sao
code/data similarity 0.55
Abstract · 41 pages, 6 figures, 4 tables. Reproducibility code: https://github.com/piyush314/random-projection-geometry (pinned as a submodule). Compan…

The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of $n$ points to $m=O(\varepsilon^{-2}\log n)$ dimensions preserves pairwise squared distances within relative error $\varepsilon$ with high probability, and this dimension order is asymptotically optimal. In high dimensions, however, distances concentrate around a baseline while key geometric information lies in much smaller fluctuations. We show that the JL bound can therefore be uninformative about retained geometry: an independent Gaussian replacement map can satisfy it even though the replacement cloud is independent of the original data. We then ask how well any decoder can recover a feature $f(D)$ of a squared distance $D$ from a linear sketch. Under squared-error loss, the optimal decoder is conditional expectation, so recovery defines a linear operator whose singular values quantify feature recovery. For isotropic Gaussian data ($Σ=σ^2 I_d$), we diagonalize this operator in closed form. For fixed $k$ with $m,d-m\to\infty$, its $k$th singular value satisfies $\ell_k\approx(m/ d)^{k/2}$. This yields three sharp consequences. A rank-$m$ sketch retains at most an $m/d$ fraction of the variance of any feature of one squared distance. If $m\to\infty$ and $m/d\to0$, the expected Kendall correlation is $\frac{2}π\sqrt{m/d}(1+o(1))$; for fixed $q$, nearest- neighbor agreement tends to $1/q$. Yet one projection can satisfy the JL bound while mean Kendall correlation vanishes when $\log n\ll m\ll d$. After removing scale, Haar-averaged retained covariance-shape information is $(m/d)^2$. Thus JL distance preservation does not quantify the geometry available for comparison or inference.

0.38