PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Brice Huang, Mark Sellke, Nike Sun

arXiv:2608.29416v1math.PRcond-mat.dis-nncs.CCmath-ph

TL;DR

The paper asks which one-dimensional projection measures are feasible for directions produced by efficient algorithms. It characterizes these measures for spherical and Ising settings using Lipschitz algorithms and develops a matching analysis based on information revelation and controlled processes.

  • Problem

    The paper studies which measures can be approximated by directions found from data by a broad class of efficient algorithms, addressing the computational question beyond mere projection feasibility.

  • Method

    The analysis considers algorithms with dimension-free Lipschitz dependence on Gaussian input and tracks a Doob martingale as information is gradually revealed through a Gaussian channel.

  • Results

    Theorem 1.2 characterizes attainable symmetrized projection-pursuit measures: spherical measures lie in ¯ℳsph,sypαq and Ising measures lie in ¯ℳIs,sypαq.

  • Takeaways & Limitations

    The characterized sets coincide with the corresponding continuous-control sets, linking algorithmically attainable measures to the paper’s control-based description.

  • Takeaways & Limitations

    The approach uses the coordinate sum rather than the full three-process object because sufficient regularity for the most obvious matrix square root is difficult to ensure.

Abstract

from arXiv · show

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.

1. Introduction

The paper characterizes which one-dimensional projection measures can be produced by dimension-free Lipschitz algorithms in spherical and Ising settings. It proves matching stochastic-control and algorithmic results, yielding exact perceptron thresholds and a new incremental AMP construction.

  • Problem: Projection pursuit asks whether data-dependent directions can produce specified non-Gaussian empirical projection measures, a computationally difficult task in the high-dimensional regime.The paper studies Gaussian data with directions constrained near either the sphere or the Ising cube.
  • Algorithmic setting: Dimension-free Lipschitz algorithms include widely used gradient-based methods, and the paper precisely characterizes the measures they can approximate.The characterization applies to algorithms whose dependence on the input is Lipschitz with a dimension-independent constant.
  • Main results: In both spherical and Ising settings, achievable measures are exactly the closures of measures generated by the corresponding controlled stochastic differential equations.The spherical and Ising characterizations are stated through the sets defined by admissible stochastic controls.
  • Perceptron consequences: The stochastic-control framework yields exact algorithmic thresholds for optimizing spherical and Ising perceptron Hamiltonians with bounded continuous activation.The spherical threshold is defined using the spherical achievable-measure set, with an analogous Ising result.
  • Technical innovation: The hardness proof develops stochastic control within the branching overlap gap framework, while the matching algorithm uses the full Brownian-bridge family of disorder matrices.The incremental AMP construction simulates controlled diffusions and provides a canonical match between hardness and attainability.
  • Proof strategy: The hardness analysis confines every Lipschitz algorithm to controlled-SDE endpoint measures, while incremental AMP attains every endpoint measure in the matching control family.The proof upgrades the hardness statement to the paper’s stronger confinement formulation.

2. Overview of limiting procedure

The section develops a Brownian-bridge-based discrete process for tracking Lipschitz algorithm outputs and extracting a limiting stochastic description. Tightness, semimartingale structure, and budget constraints then restrict the feasible spherical and Ising projection processes.

  • Process construction: A Brownian bridge reveals the Gaussian disorder over time while the process tracks the algorithm’s conditional expected output.The bridge ends at the Gaussian disorder supplied to the algorithm, and the process observes its evolution at discrete times.
  • Process construction: Spatial rerandomization imposes a natural filtration, enabling tightness analysis and extraction of coefficients for the limiting SDE.The analysis introduces discrete-time coefficient quantities and proves tightness for the rerandomized processes.
  • Limiting structure: Subsequential limits are continuous semimartingales whose coordinate components separate into finite-variation and martingale parts.The limiting process has drift and covariation, with specified components having zero drift and cross-covariation.
  • Coefficient constraints: High-probability budget constraints govern the coefficients associated with both spherical and Ising perceptrons.The constraints are stated for several coefficient systems, including diffusivity terms for the Ising case.
  • Coefficient constraints: The feasible range of a coefficient pair is characterized by v ≥ 0, x ≥ 0, and x + (v^1/2 − 1)^2 ≤ 1.This set is identified as the full range of feasible (v, x) values.

3. Lipschitz algorithms and a priori estimates

This section establishes concentration and stability properties for dimension-free Lipschitz algorithms, then uses perturbations to control their correlation functions. These estimates support later analysis of algorithmic outputs and projection measures.

  • Gaussian estimates: Lipschitz functions of Gaussian inputs exhibit subgaussian concentration, yielding norm and moment bounds for algorithmic outputs.The section derives concentration for scalar projections and applies it to vector norms and moments.
  • Projection stability: Projection measures are stable under perturbing the direction, and relaxed spherical or Ising outputs can be rounded with nearly unchanged performance.The Wasserstein error after rounding is bounded by the relaxation error and a term proportional to the rounding scale.
  • Correlation control: The correlation function is increasing and convex, with endpoint derivative control including χ′(1) ≤ L^2.The derivative bounds are used to justify assumptions required in the limiting analysis.
  • Correlation control: A perturbation of any Lipschitz algorithm can enforce useful lower and upper bounds on the derivative of its correlation function while approximately preserving performance.The perturbed algorithm remains Lipschitz and approximates the original algorithm in the relevant sense.
  • Correlation control: When the initial correlation q_0 approaches one, the resulting algorithmic output can achieve only the Gaussian distribution.This observation explains why errors depending on 1 − q_0 can be regarded as small in the later analysis.

4. SDE characterization of limits

The section converts subsequential semimartingale limits of algorithmic processes into constrained SDEs. Occupation-measure smoothing and Fokker–Planck comparison establish that these SDEs reproduce the relevant marginal laws while respecting the limiting constraints.

  • Smoothing construction: Occupation measures of the semimartingale, drift, and covariation are smoothed to construct Markovian SDE coefficients approximating the original marginal laws.The modified smoothing procedure is used because passing budget constraints through the ideal smoothing is technically difficult.
  • SDE characterization: The proof of hardness relies on this SDE characterization, which the section identifies as its most important step.The result is later used to relate limiting SDE classes and establish the main hardness argument.
  • Limiting SDEs: A subsequential limit of the rerandomized processes is represented by coefficients and initial laws satisfying diffusivity, budget, and moment constraints.The limiting inverse correlation function is increasing and concave, and the resulting processes are described on a time interval beginning near q_0.
  • SDE characterization: The resulting endpoint distributions approximate the original projection distributions, with errors tending to zero as L^−Θ(1).This identifies the constrained SDE endpoints with the limiting distributions of the algorithmic processes.
  • Fokker–Planck comparison: Under bounded Lipschitz coefficients, the constructed SDE and comparison process satisfy the same Fokker–Planck equations and therefore have matching marginal laws at each fixed time.The argument uses uniqueness for the associated Fokker–Planck equation.

Then we have the bound

This section derives limiting SDE descriptions for Lipschitz algorithms and verifies that their coefficients satisfy the required regularity and budget constraints. The argument also identifies equality cases for the relevant bounds.

  • Optimization bound: Stationarity reduces the interior optimization bound to equality, and the boundary case is checked separately when the residual variance parameter is zero.The proof derives σ^2 = ṽ for an interior stationary point before treating ṽ = 0.
  • Approximation estimates: The proof transfers estimates through spatial and temporal smoothing, convergence, and comparison between the rerandomized and limiting processes.The argument uses bounded or dominated convergence together with regularity estimates to pass bounds to the limit.
  • Limiting SDE: Theorem 4.41 associates any suitable sequence of Lipschitz algorithms with a limiting SDE on a terminal time interval.The limiting drift, diffusion, and control functions are bounded and Lipschitz, subject to specified constraints and initialization conditions.
  • Coefficient matching: The constructed coefficients are chosen so that the drift and diffusive terms of the modified and target SDEs coincide exactly.The definitions set w and the diffusion coefficients from the corresponding quadratic-variation quantities.
  • Constraint verification: The coefficient regularity follows from earlier corollaries, while the budget constraint follows from concentration estimates for the quadratic-variation term.The proof separately verifies boundedness and Lipschitz control for drift and diffusivity, then establishes the constraint in the limit.

5. Matching IAMP algorithms

This section constructs incremental AMP algorithms that simulate the controlled SDEs arising in the hardness analysis. The construction extends prior IAMP schemes to correlated matrix processes and yields Lipschitz algorithms with additional symmetry and endpoint properties.

  • Main construction: Theorem 5.1 constructs a Lipschitz algorithm that approximates the output of controlled SDEs under regularity, moment, and budget assumptions.The theorem applies to bounded Lipschitz controls and suitable initial measures, with an approximation parameter ε and constants depending on L and ε.
  • Symmetry: Under additional symmetry assumptions, the algorithm can be centered, with output mean zero in R^N.The symmetry is enforced exactly at the finite-dimensional algorithmic level, not only in the state evolution limit.
  • Algorithmic novelty: The new IAMP algorithm multiplies iterates by a correlated family of Brownian matrix processes, enabling simulation of general semimartingale diffusions.Earlier IAMP algorithms were restricted to martingale SDEs because they used first-order iterations with the fixed input matrix.
  • Chaotic IAMP: Chaotic IAMP achieves feasible symmetrized endpoint measures and can construct large approximately ultrametric solution trees.The correlation function can be made small near the endpoint while preserving the target symmetrized behavior.
  • State evolution: The IAMP state evolution is coupled to the target SDE so that its coordinate profile and final output approximate the desired endpoint law.The key relation is A_ℓu_ℓ ≈ x_ℓ, leading to Gu_ℓmax ≈ x_ℓmax and the law of X_1.

(We note that the order of parameters is consistent with (5.68).)

This section proves the chaotic IAMP estimates through an induction controlling correlations and moments across paired state-evolution processes. The resulting estimates establish the desired approximation in the limiting parameter regime.

  • Inductive structure: The proof proceeds by induction through four implications linking recursive moment, covariance, and correlation estimates.The induction cycle is (5.97) ⇒ (5.98) ⇒ (5.99) ⇒ (5.100) ⇒ (5.97) at the next iteration.
  • Moment bounds: Uniform second-moment bounds keep the iterates and their increments controlled throughout the induction.The bound includes the paired Y variables and the increments of the auxiliary M processes.
  • Covariance control: Conditional symmetry allows the covariance lemma to control paired Gaussian variables generated by the chaotic recursion.The relevant process variables have symmetric conditional distributions, satisfying the zero-mean condition required by the covariance estimate.
  • Correlation decay: The paired U-process increments become asymptotically uncorrelated while retaining variance bounded away from zero.The proof combines a vanishing cross-covariance with a positive lower bound on the corresponding second moment.
  • Induction closure: The analogous V-process estimates close the induction and imply that the relevant correlation discrepancy is o_η(1).The argument establishes a positive variance lower bound for V increments before concluding the next-step discrepancy estimate.

6. Eqivalence and continuity of stochastic control problems

The paper shows that several stochastic-control formulations yield the same limiting endpoint measures for Lipschitz algorithms, including the cleaner ideal control problem. These achievable-measure sets also vary continuously with the aspect ratio α.

  • The IAMP, BOGP, and ideal control formulations coincide in the limiting regime through a cycle of inclusions and approximation arguments.
  • Theorem 6.1 identifies the asymptotically achievable Ising endpoint measures with the ideal control sets ℳ̄_Is(α) and ℳ̄_Is,c(α).
  • Theorem 6.4 gives the analogous characterization for symmetrized Ising endpoint measures, with ideal controls restricted to p = 1.
  • The maps α ↦ ℳ̄_Is(α) and α ↦ ℳ̄_Is,sy(α) are continuous in the Hausdorff metric induced by W_2.
  • At starting time q_0 = 1, the Lipschitz-achievable set reduces to the singleton containing the standard Gaussian measure.

7. Confinement of Lipschitz achievable measures to ideal set

This section addresses the lack of guaranteed W_2 subsequential convergence for Lipschitz-achievable measures by proving confinement in the weaker W_q metric, q ∈ [1,2). The result connects general Lipschitz algorithms to the ideal control sets.

  • Lipschitz-achievable projection measures need not have W_2-convergent subsequences, as shown by the spherical algorithm selecting the first data row.
  • For q ∈ [1,2), the measures generated by Lipschitz algorithms are asymptotically confined to the ideal set in W_q.
  • Moment and concentration estimates show that truncation changes the empirical projection measure negligibly in W_q, although not necessarily in W_2.
  • The proof truncates algorithms by replacing rows with large conditional projection means by independent Gaussian rows, preserving Lipschitzness.

We then have the bounds

The section proves the quantitative bounds needed for achievability and hardness, then applies them to show that ideal measures can be attained while measures separated from the ideal set remain algorithmically inaccessible.

  • Truncation and concentration estimates provide uniform control of projection moments and Wasserstein distances for Lipschitz algorithms.
  • Every measure in the ideal Ising control set can be approximated by an efficiently implementable IAMP algorithm with exponentially high probability.
  • The same achievability conclusion holds for symmetrized measures in the Ising setting.
  • For any positive separation from the ideal set, sufficiently accurate Lipschitz algorithms cannot attain the separated target measures.
  • The hardness proof relies on the controlled-SDE characterization of Lipschitz outputs and the matching IAMP construction, whose endpoint-measure sets coincide.

Then the function

This section establishes continuity and Lipschitz-based concentration properties for the processes and functionals used in the projection-pursuit analysis.

  • The function f_ϕ is continuous on the compact set of achievable measures under the W1 metric.Compactness follows from closure and compactness of the relevant measure space.
  • The analysis tracks inner-product processes across discrete times of order δ, treating the Ising case as the more difficult setting.The spherical case is described as similar but easier.
  • The limiting processes Y and Y+ are shown to exist with semimartingale decompositions.This provides the stochastic-process structure used later in the proof.
  • The processes are organized into components whose limiting behavior is analyzed through drift, quadratic variation, and covariation.These quantities support the derivation of continuous stochastic-process scaling limits.
  • Lipschitz algorithms produce outputs whose associated random vectors are subgaussian with dimension-independent variance proxies.The argument uses Lipschitz dependence on Gaussian inputs and standard concentration estimates.

A.2. Estimates on preprocessing errors.

This section bounds preprocessing errors by combining martingale, subgaussian, stopping-time, and coupling arguments.

  • A.2. Estimates on preprocessing errors.: Preprocessing transformations preserve endpoint distributions up to negligible W2 error under the stated assumptions.The processes X, Xtr˚, X+˚, Xtr, and X+ can be coupled with uniformly small endpoint discrepancies.
  • A.2. Estimates on preprocessing errors.: The stopping-time estimates imply negligible discrepancies between original and truncated processes uniformly in N.The estimates rely on coupling the initial process with a random variable having law μ.
  • A.2. Estimates on preprocessing errors.: Centered process increments form martingales with subgaussian tails, enabling uniform moment bounds through Doob’s inequality.The argument is applied to multiple process components and their recentered versions.
  • A.2. Estimates on preprocessing errors.: Truncation agrees with the original process until a stopping time, so error control reduces to bounding the probability of early stopping.The stopping time is expressed through componentwise stopping times.
  • A.2. Estimates on preprocessing errors.: Adding a small density of frozen particles also incurs negligible W2 error in the endpoint distribution.The proof uses martingale structure and high-probability agreement events.

A.6. Tightness.

This section proves tightness and subsequential convergence for the random laws of the continuous process trajectories, with the error process vanishing in the limit.

  • A.6. Tightness.: The laws Q_N are tight, and every subsequential limit assigns probability one to paths with zero error process E.The same assertion holds for the “+” variant.
  • A.6. Tightness.: Moment and Hölder estimates control the process paths and establish compactness through Arzelà–Ascoli and Prohorov’s theorems.The resulting compact sets carry arbitrarily high probability uniformly for sufficiently large N.
  • A.6. Tightness.: The error process converges in probability to the zero path, and a subsequence can be chosen for almost-sure convergence.This convergence is then transferred to the process approximations.
  • A.6. Tightness.: The truncation indicators are small with probability at least 1 − exp(−N^1/2).This bound holds for all tracked process components under the stated assumptions.
  • A.6. Tightness.: Piecewise constant versions of the processes converge along the same subsequences as the original laws.The statement also applies to the “+” variant.

Appendix B. Derivation of budget constraint

This appendix derives budget constraints for Lipschitz Gaussian-process constructions by reducing random projections to deterministic convex and optimization problems.

  • Appendix B. Derivation of budget constraint: The budget-constraint result considers Lipschitz vector-valued functions of Gaussian matrices and random partitions satisfying prescribed proportion constraints.The auxiliary Gaussian matrix is independent of the original disorder and auxiliary randomness.
  • Appendix B. Derivation of budget constraint: The resulting proposition holds with probability at least 1 − e^(−cN), where c depends on α, L, ι, and ε.The probability statement applies for all sufficiently large N.
  • Appendix B. Derivation of budget constraint: The proof compares a random linear projection F with its maximum F̃ over vectors satisfying the budget constraint.This comparison is used to show that the random vector lies in or near the associated convex body.
  • Appendix B. Derivation of budget constraint: A polytope approximation allows concentration bounds to be combined with a union bound over sufficiently many directions.The approximation is chosen uniformly in the key problem parameters.
  • Appendix B. Derivation of budget constraint: The stochastic upper-bound argument successively reduces the original projection quantity to tractable optimization problems.The reductions include orthogonal-point optimization, Gaussian comparison, and minimax formulations.
  • Appendix B. Derivation of budget constraint: Gaussian comparison inequalities replace a deformed Wishart matrix with linear Gaussian terms, leading to a minimax problem and a non-variational formula V(z̃).The formula is obtained using Lagrange multipliers and then bounds the preceding minimax quantity.

B.1. Linear projections of statistics.

This section defines the feasible set for linear projections through cost and budget constraints, then reduces its analysis to a finite-dimensional optimization problem with high-probability approximation guarantees.

  • Feasible sets: The random vector Y lies in an ambient domain D_, while D_μ imposes the target measure constraint w ∈ W_μ and coordinatewise v ≥ U.The paper also uses the affine closure F_μ and weighted inner products to formulate projection bounds.
  • Projection objective: The linear projection F_{λ,μ}(Ŷ;Y) is defined by weighted inner products between the direction Ŷ and the components of Y.The direction Ŷ satisfies a normalization condition without loss of generality.
  • Ideal optimization: The ideal value F̃_{λ,μ} maximizes this linear projection over the ideal feasible set S̃(λ,μ).This replaces the random vector construction by optimization over all admissible feasible vectors.
  • Probabilistic control: Proposition B.2 provides the main high-probability comparison controlling the random projection objective by its ideal counterpart.The proof combines concentration, continuity of cost and budget, and the polytope approximation.
  • Polytope approximation: Proposition B.3 places an ε_1-neighborhood of S̃(λ,μ) inside a closed D_μ-polytope with at most C_pol facets.The constants depend only on α, ι, and ε.

B.3. Reduction to optimization over many orthogonal replicas.

This section replaces a data-dependent optimization over one Lipschitz output by an optimization over many orthogonal replicas, enabling stochastic domination arguments through simplified Gaussian processes.

  • Orthogonal replicas: For k orthogonal replicas, F_ii(k) averages the corresponding objective over vectors of norm N^1/2 that are orthogonal to one another and to the reference direction.This removes the direct dependence on the single data-dependent output from the optimization domain.
  • Initial decomposition: The original quantity F is rewritten as a sum of component functions involving the random partition and the projection direction.The decomposition separates contributions associated with blocks B_j, K_j, and orthogonal projections.
  • First comparison: Proposition B.20 shows that F_ii(k) approximately stochastically dominates F.The comparison is obtained after Gram–Schmidt orthogonalization and Gaussian concentration for Lipschitz extensions.
  • Simplification: A simplified objective F_iii(k) removes dependence on the empirical mean direction and replaces the random partition by an arbitrary partition.This prepares a uniform concentration argument reducing the analysis to deterministic partitions.
  • Replica reduction: Proposition B.23 shows that F_iii(k) approximately stochastically dominates F_ii(k), completing the reduction to the simplified replica problem.The argument uses distributional invariance of Gaussian processes under the relevant orthogonality constraints.

B.5. Application of gaussian comparison inequalities.

Gaussian comparison inequalities reduce the simplified replica optimization to a scalar variational problem whose value is represented by a strictly convex function with a unique minimizer.

  • Gaussian comparison: The simplified objective F_v is compared with auxiliary Gaussian processes using Slepian’s and Gordon’s inequalities.The covariance comparison yields stochastic domination between the relevant positive and negative components.
  • Reduction chain: The comparison chain transfers stochastic domination from the replica objective through successive auxiliary objectives to the scalar variational bound.Propositions B.20, B.23, B.24, and B.27 establish the successive reductions used before the final Gaussian comparison.
  • Convexity: The function V is strictly convex and diverges to infinity, so it has a unique minimizer z_min on its admissible interval.This convexity controls the subsequent case analysis and stationarity arguments.
  • Optimizer characterization: When the boundary condition fails, z_min is characterized as the unique solution of V′(z)=0 in the interior.The boundary case is determined by the sign condition involving α and μ_1.
  • Scalar reduction: The resulting variational objective F̃ is expressed through a scalar function V evaluated at an optimizer z*.Proposition B.34 identifies the exact value as F̃ = V(z*).

B.7. Conclusion of proof.

The proof concludes by analyzing the scalar optimizer, establishing uniqueness and concentration bounds, and combining the comparison steps to obtain the final domination estimate.

  • Uniqueness: The scalar fixed-point equation has at most one solution because its two sides have strictly ordered monotonicity.The argument covers both s ≥ 2 and the separate s = 1 scenarios.
  • Identification: The distinguished value γ* = γ(z*) satisfies the fixed-point equation and is therefore its unique solution.This identifies the scalar optimizer with the variational minimizer from the preceding section.
  • Concentration: Uniform Gaussian concentration supplies exponentially high-probability bounds simultaneously over the relevant parameter ranges.The bounds cover γ, β, and auxiliary Gaussian quadratic forms under the stated parameter restrictions.
  • Stationary-point analysis: The optimization over the sphere is reduced through Lagrange multipliers to vectors determined by a scalar parameter β and diagonal resolvents.Local maximizers have the stated resolvent form and satisfy β ≥ ŵ_1.
  • Conclusion: Combining the stochastic comparisons yields the final bound, with the remaining approximation error controlled by choosing δ sufficiently small.The concluding estimate follows from the preceding propositions and is exponentially small in N.
Loading 2608.29416v1…