Algorithmic threshold for high-dimensional projection pursuit I: general theory
Abstract
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→∞ with M/N→α∈(0,∞). 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 SN=√N𝕊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.
Related
- Search Dimension in Unlabeled Projection Pursuit: A Scaling Law for Subspace Restriction
- Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part I: Glauber Dynamics
- Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics
- Mordukhovich Derivatives and Covering Constant for Set-Valued Metric Projection in General Banach Spaces
- SPARK: A General Goodness-of-Fit Assessment via Residual Projection
BibTeX
@misc{huang2026algorithmic,
title = {{Algorithmic threshold for high-dimensional projection pursuit I: general theory}},
author = {Brice Huang and Mark Sellke and Nike Sun},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29416},
eprint = {2608.29416},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29416},
}
RIS
TY - UNPB
TI - Algorithmic threshold for high-dimensional projection pursuit I: general theory
AU - Brice Huang
AU - Mark Sellke
AU - Nike Sun
PY - 2026
DA - 2026/08/29
PB - arXiv
DO - 10.48550/arxiv.2608.29416
UR - https://arxiv.org/abs/2608.29416
AB - 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→∞ with M/N→α∈(0,∞). 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=√N𝕊^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.
ER -