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 target projection distributions can be found by efficient, data-dependent directions. It characterizes the algorithmically attainable set via stochastic control, giving exact criteria for spherical and Ising settings.

  • Problem

    The paper asks which target distributions can be approximated by algorithmically found directions, since finding a projection close to a target is not a convex optimization problem.

    Source: §1 · p. 2

  • Method

    The paper characterizes measures attainable by dimension-free Lipschitz algorithms through control-constrained criteria for spherical and Ising directions.

    Source: §1.1 · pp. 3–5

  • Results

    A target measure is approximable by a Lipschitz algorithm if and only if it belongs to the specified attainable set for the spherical or Ising setting.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    The characterization specifies which target measures are algorithmically feasible in spherical and Ising projection pursuit.

    Source: §1.1 · p. 4

    For the three-process analysis, sufficient regularity of the natural matrix square root is difficult to ensure, so the proof instead uses the processes’ coordinate sum.

    Source: §4.1 · p. 49

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 introduction frames high-dimensional projection pursuit as identifying which projection measures dimension-free Lipschitz algorithms can attain, and presents an exact stochastic-control characterization using controlled SDEs. It also describes matching incremental AMP algorithms and relates the characterization to perceptron optimization thresholds.

1.2. Further background and related works.

  • Earlier work [MZ22] showed that high-dimensional Gaussian point clouds admit non-Gaussian projections, but all such projections remain bounded in 2-Wasserstein distance from Gaussian.The paper positions projections outside its algorithmically achievable sets as suggestive of underlying data structure.Source: §1 · p. 2, §1.2.1 · p. 6

1. Introduction

  • For high-dimensional Gaussian data, the paper asks which one-dimensional projection measures can be found by efficient algorithms, rather than merely which measures are feasible.The target-measure search is not convex, and the paper considers directions on either the sphere or the Ising cube.Source: §1 · p. 2, §1.1 · p. 3

1.1. Main results.

  • In the symmetrized setting, Lipschitz algorithms attain exactly the 2-Wasserstein closures of the stochastic-control measure sets, separately for spherical and Ising directions.The control sets are defined by laws of controlled processes, with distinct endpoint conditions for the two settings.Source: §1.1 · p. 4
  • For general projections, attainable measures are exactly the closures of the corresponding spherical and Ising control sets, which also equal their concave-p subclasses.The general control formulation uses a function p to specify admissible controls for each setting.Source: §1.1 · pp. 5–6
  • For bounded continuous activations, the characterization yields algorithmic thresholds for spherical and Ising perceptron optimization from their respective attainable-measure sets.The Ising control set is strictly smaller than the spherical one because it imposes an endpoint condition.Source: §1.1 · p. 6

1.2.2. Satisfiability threshold and free energy. "

  • Prior perceptron research established efficient solvability for the spherical half-space case with nonnegative margin and developed rigorous threshold results in both spherical and Ising settings.The spherical reformulation is convex [Sto13a]; cited Ising threshold results include [DS19] [Hua24].Source: §1.2.2 · p. 7, §1.2.3 · p. 7

1.2.3. Previous algorithms.

  • Work on the symmetric binary perceptron found regimes where solutions exist but stable algorithms cannot find them, while independent spherical AMP work [MZ24] treats a subclass with p=1.The paper relates its results to algorithms finding rare dense clusters and notes that the relationship between the algorithm classes is conjectural.Source: §1.2.3 · p. 8

1.2.4. Hardness of random optimization problems.

  • The hardness analysis extends branching OGP toward exact algorithmic thresholds by analyzing its spin-glass ensembles in the small-step-size limit.Earlier branching OGP work used Guerra–Talagrand interpolation, which applies only to even mixed p-spin models.Source: §1.2.4 · p. 8
  • The hardness framework extends [HS23] by tracking evolving probability measures rather than finitely many norms, enabling sharp thresholds for Ising spins and more general Hamiltonians.The challenge arises from the lack of spherical symmetry; the analysis develops stochastic control within the branching overlap gap property.Source: §1.2.4 · pp. 8–9

1.3. Some proof ideas.

  • The proof extracts limiting SDE controls from Lipschitz algorithms by establishing tightness and passing discretized drift and quadratic-variation budget constraints to the limit.The Ising case requires a second, interacting control problem for the Doob martingale’s coordinate process.Source: §1.3 · pp. 9–10
  • Incremental AMP constructs matching Lipschitz algorithms by simulating controlled SDEs using a family of disorder matrices evolving along a Brownian-bridge revelation.The construction makes the algorithmic and hardness results match; this implementation uses the full family G(t), rather than only the input matrix.Source: §1.3 · p. 10

1.4. Formal definitions and theorem statements.

  • The main results characterize the measures attainable and confined by Lipschitz algorithms in spherical and Ising projection pursuit; concave controls suffice for the full endpoint sets.The spherical theorem gives high-probability achievability and confinement, and the analogous results hold for Ising projection pursuit.Source: §1.4 · p. 12
  • For symmetrized spherical and Ising projection pursuit, the paper likewise identifies the endpoint-measure sets that Lipschitz algorithms can attain and to which they are confined.The theorem states high-probability achievability and confinement for the respective symmetrized sets.Source: §1.4 · p. 13

1.5. Organization of this paper.

  • The paper’s proof first derives hardness and matching IAMP achievability, then establishes endpoint-set equivalence and uses truncation to prove confinement and obtain perceptron thresholds.Truncation addresses the lack of uniform integrability; the final corollary optimizes linear functionals over the characterized measure sets.Source: §1.5 · pp. 13–14

2. Overview of limiting procedure

This overview tracks algorithm outputs as Gaussian disorder is revealed along a Brownian bridge, then preprocesses and spatially rerandomizes the resulting processes to extract semimartingale limits. It develops estimates and high-probability budget constraints governing the limiting coefficients, and gives a free-probability heuristic for the limiting feasible region and cost function.

2. Overview of limiting procedure

  • The procedure starts with a discrete-time process tracking the algorithm’s expected output conditional on the Brownian bridge’s revelation of the Gaussian disorder.The bridge runs from zero to the Gaussian disorder supplied to the algorithm.Source: §2 · p. 16, §2.1 · p. 17

2.1. Processes tracking the algorithm.

  • The process is decomposed into increments expected to yield drift and martingale terms, with spatially rerandomized local averages approximating the limiting SDE coefficients.The paper connects this analysis conceptually to branching OGP, but uses Lipschitzness directly to extract the SDE limit.Source: §2.1 · pp. 19–20

2.2. Preprocessing and spatial rerandomization.

  • Preprocessing truncates the processes and freezes particles, then spatial buckets are used to rerandomize them by averaging within each particle’s bucket.For the Ising perceptron, the procedure also rerandomizes the Ising-coordinate process using its own buckets.Source: §2.2 · pp. 21, 23
  • Under the prescribed parameter order, spatially rerandomized processes converge along subsequences to continuous semimartingales.The procedure first sends N, η, and δ to their limits to obtain an SDE description, then takes the remaining parameters to improve its approximation of μ_G(A).Source: §2.3 · p. 24, §2.2 · p. 24

2.3. Tightness in continuum limit.

  • The conditional laws of (Y, D, Q) are tight, and every subsequential limit makes Y a semimartingale with drift D and covariation Q.In the limit, Y^I has finite variation, Y^II, Y^III, and Y^Is are martingales, and the stated cross-covariations vanish; analogous statements hold for Y+.Source: §2.3 · p. 24
  • Coarsened-bucket averages of discrete drift and diffusivity coefficients supply the limiting SDE coefficients b_s and σ_s, while w_s comes from averaged w coefficients.The limits are taken after averaging over coarsened spatial buckets; σ_s also uses a transform described in Section 4.5.Source: §2.3 · p. 26

2.4. A priori estimates.

  • A priori estimates provide moment controls for Y and Y+ increments and quenched bounds on their drift and covariation approximations.The section states Kolmogorov-type bounds and second-moment bounds for the processes, as well as bounds for drift and quadratic-variation approximations.Source: §2.4 · pp. 26–27

2.5. Budget constraints.

  • With high probability, budget constraints apply to the spherical and Ising perceptron coefficients, including preliminary constraints for their drift and diffusivity terms.The general budget theorem gives a cost-based constraint with probability at least 1 − e^(−cN) under its stated Lipschitz and partition conditions.Source: §2.5 · pp. 28–29
  • Propositions 2.22–2.23 establish high-probability, uniform-in-time constraints for spherical and Ising budgets, including Ising diffusivity and corresponding c-variants.The propositions apply simultaneously for all 0 ≤ d ≤ d_max − 1.Source: §2.5 · pp. 33–34

2.6. Heuristic derivation of budget constraint.

  • The Wishart illustration recovers the Marchenko–Pastur support, while the spiked example predicts an outlier above the threshold 1/G_W(λ+).For a supercritical spike θ, the outlier is around (G_W)^−1(1/θ).Source: §2.6 · pp. 35–36
  • In a Wishart example, the feasible (v, x) region is v ≥ 0, x ≥ 0, and x + (v^1/2 − 1)^2 ≤ 1.The passage presents this as the full range of feasible pairs.Source: §2.6 · p. 37
  • Free-probability calculations heuristically derive feasible coefficient regions for spherical perceptron examples and explain how the paper’s cost function arises.The examples first simplify by ignoring a coefficient, then consider its interaction with the others.Source: §2.6 · p. 38
  • The limiting constraint is sharp: exposed boundary points arise from top eigenvectors, and convex combinations yield other boundary and interior points.Interior points use an additional convex combination with an independent standard Gaussian vector.Source: §2.6 · p. 38

3. Lipschitz algorithms and a priori estimates

The section establishes basic concentration and projection estimates, then shows how to perturb Lipschitz algorithms to control their correlation functions.

3.1. Basic estimates.

  • A subgaussian vector with variance proxy σ² has pth norm moment at most C_pσ^pN^(p/2), and centered L-Lipschitz Gaussian outputs have variance proxy 2L².The moment bound applies to Lipschitz Gaussian outputs with σ²=2L².Source: §3.1 · pp. 39–40
  • Relaxed-domain outputs can be rounded to the sphere or cube with nearly the same performance, with projection-distribution W2 error bounded by ε+C(α^1/2+1)ι.The bound holds outside the exceptional event in Lemma 3.4.Source: §3.1 · p. 41

3.2. Correlation function bounds.

  • For an L-Lipschitz algorithm, the correlation function satisfies χ′(1)≤L²; its Hermite expansion also makes χ increasing and convex.These properties reduce bounding χ to controlling its derivatives at 0 and 1.Source: §3.2 · p. 41
  • In both spherical and Ising settings, an L-Lipschitz algorithm can be perturbed to have χ(0)=q0 and χ′(0)≥1/L², while remaining L-Lipschitz.The construction applies when q0<1 and L≥1.Source: §3.2 · p. 42
  • The perturbation approximates the original algorithm, with error that becomes small as q0 approaches one.The paper notes that algorithms with q0 tending to one can only attain the Gaussian distribution.Source: §3.2 · p. 42
  • Any attainable target of a randomized L-Lipschitz algorithm can also be attained by a deterministic L-Lipschitz algorithm, with slightly worse parameters.The argument fixes a suitable realization of the auxiliary randomness.Source: §3.2 · p. 43

4. SDE characterization of limits

Section 4 develops SDE descriptions of limits of Lipschitz algorithms by smoothing discrete-time coefficients and occupation measures while carrying domain and budget constraints toward continuous time. It shows that algorithm distributions can be approximated by constrained SDE endpoint distributions, with error vanishing as the Lipschitz constant grows.

4. SDE characterization of limits

  • Theorem 4.2 shows that distributions from Lipschitz algorithms are approximated by constrained SDE endpoint distributions, with error vanishing as the Lipschitz constant grows.The SDE has regular coefficients, satisfies diffusivity and approximate budget constraints, and starts at a time close to q0 with specified initial-measure conditions.Source: §4 · p. 45
  • A more general diffusion can be approximated by Markovian SDE solutions with Lipschitz coefficients under budget constraints; when its Ising marginal is even, the coefficient w can also be even.The approximation is stated for the diffusion pair and its corresponding Markovian SDE solutions.Source: §4 · pp. 45–46

4.1. Ideal smoothing in abstract setting.

  • Under bounded Lipschitz coefficients, ideal smoothing gives an SDE whose marginal law matches the smoothed semimartingale’s law at each fixed time.The argument compares their Fokker–Planck equations and uses uniqueness; a one-dimensional coordinate-sum version is also established.Source: §4.1 · pp. 48–50

4.2. Discrete coefficients and smoothing.

  • Discrete-time occupation measures are spatially smoothed and projected to a coordinate sum; modified temporal smoothing then helps preserve budget constraints.The modified procedure differs from ideal smoothing, and the section later addresses the discrepancy between the resulting coefficients.Source: §4 · p. 44, §4.2 · p. 51
  • With high probability, spatial smoothing preserves the domain constraint for the discrete-time coefficients.The constraint holds for all times t and spatial coordinates y in the stated domain.Source: §4.2 · p. 54
  • With high probability, the budget constraint also holds for the spatially smoothed quantities at every time.Source: §4.2 · p. 55
  • Spatially smoothed coefficients are continuously differentiable in space and satisfy bounds; the added density of frozen particles is essential for boundedness.These properties are established for the “+” processes.Source: §4.2 · p. 56
  • For t ≥ q0, the square roots of the smoothed quantities F and w have spatial regularity bounds used in passing to the limit.The text identifies these bounds as a precursor to the limit result in Corollary 4.29.Source: §4.2 · p. 58
  • With high probability, the spatially smoothed occupation densities satisfy continuity-in-time bounds for q0 ≤ t ≤ 1.The bounds apply across all 0 ≤ s ≤ t ≤ 1.Source: §4.2 · p. 60
  • The temporally smoothed coefficients are continuously differentiable in space and time and satisfy regularity bounds analogous to those for spatial smoothing.The stated bounds also extend to the ideal-smoothed coefficients.Source: §4.2 · p. 62
  • Temporal smoothing carries the domain and budget constraints with high probability, with sharper constraint comparisons holding outside exceptional bad-time sets.The results compare different smoothing rules and establish the budget constraint for temporally smoothed quantities outside the bad-time set.Source: §4.2 · pp. 63–65

4.3. Limiting coefficients and constraints.

  • Under a Skorohod coupling, the occupation measures converge weakly whenever the disorder measures converge.The convergence covers the path occupation measure and those associated with the coefficients.Source: §4.3 · pp. 67–69
  • The smoothed coefficients converge pointwise, remain nonnegative where specified, and preserve the domain condition v(t,y) ≥ u(t,y)^2 for all t and y.The nonnegativity claim applies to the listed limiting coefficients and functions; the domain condition is stated for the directly smoothed coefficients.Source: §4.3 · p. 69
  • The coefficients for the limiting process converge pointwise, and the limiting regularity and bad-time estimates support passing coefficient bounds to the limit.The convergence proof uses weak convergence and the fact that the derivative p1 has measure-zero discontinuities under the limiting measure; the bad-time lemma transfers containment for sufficiently large N.Source: §4.3 · pp. 70–71
  • The limiting coefficients inherit regularity bounds, while the limiting budget constraints hold almost surely.The coefficient bounds also control discrepancies outside a set of bad times; the excerpt does not expose the formulas for these estimates.Source: §4.3 · pp. 70–72

4.4. Limiting SDE.

  • For each fixed time, the ideal-coefficient SDE and the limiting process have matching marginal laws, and the smoothed-coefficient SDE approximates the limiting process in L2-Wasserstein distance.The marginal-law match follows from their shared Fokker–Planck equations; the Wasserstein approximation is also stated for the Is component.Source: §4.4 · pp. 73, 75

4.5. Final budget constraints for limiting SDE.

  • The final budget step addresses the discrepancy between r̄(t,y) and t p1(t), and introduces a reduction of the u,v constraint to one parameter σ.The stated inequality setup assumes v ≥ u^2 − λ̄ and positive P1, P2; the excerpt does not include the proposition’s conclusion.Source: §4.5 · p. 76

Then we have the bound

This section develops SDE descriptions and approximation arguments for Lipschitz algorithms, proving the main theorem and extending the analysis to a continuous-process setting. It also shows that smoothing preserves the required coefficient constraints and regularity, with a time-uniform budget bound.

Theorem 4.41

  • Theorem 4.41 represents a subsequential limit of an L-Lipschitz algorithm by an SDE on [q*, 1], with errors tending to zero as L grows.The theorem assumes convergence of the algorithms’ control functions and specifies regularity, budget, and initialization conditions for the SDE.Source: Then we have the bound · p. 79
  • Theorem 4.41’s errors can be made to vanish at least polynomially in L, with the largest error arising from the initialization bound.The final W2 error bounds follow from Proposition 4.38.Source: Then we have the bound · p. 83

Proofs of Theorems 4.2 and 4.3

  • The proof of Theorem 4.2 applies Theorem 4.41 to obtain its conclusions, then combines approximation and error bounds to establish the result.The proof bounds the component errors by ε_apx, O(ε_apx) + o_K(1), and o(1), respectively.Source: Then we have the bound · p. 83
  • For Theorem 4.3, the adaptation assumes p(q0) ≥ 1/L and regularity of p, allowing any suitable q* near q0 and J = ∅.It starts from continuous-time processes, avoiding the division-by-zero issue that required choosing q* in the preceding argument.Source: Then we have the bound · pp. 83–84

Then we have the bound

  • Spatial smoothing and comparison preserve the domain constraint and give the coefficients an approximate budget constraint, up to o_K(1).The argument checks the budget through successive comparisons of the original, truncated, and smoothed coefficients.Source: Then we have the bound · pp. 85–86
  • The approximate budget yields a priori bounds that support regularity estimates for the smoothed coefficients and occupation densities.The stochastic integral representation supplies additional estimates for the coordinates of Z+.Source: Then we have the bound · pp. 86–87
  • The regularity assumption on p permits J = ∅, giving uniformly close smoothed coefficients; independence from N also makes several auxiliary estimates redundant or trivial.The assumption p(q0) ≥ 1/L means no further restriction on q* is needed for the cited bound.Source: Then we have the bound · p. 87
  • The ideal-coefficient SDE approximations have matching marginals with the corresponding ideal processes, and the actual SDE solutions are close to those approximations.The argument combines coefficient-discrepancy bounds, Grönwall’s inequality, and closeness of the smoothed and original processes.Source: Then we have the bound · pp. 87–88
  • These estimates yield all five conclusions of Theorem 4.3, with the third bound holding uniformly over t in [q*, 1].Because J = ∅, the budget constraint holds at each time, enabling SDE approximations to the stated processes.Source: Then we have the bound · p. 88
  • The W2 approximation estimates follow from Theorem 4.41, and symmetry permits w_t to be even when L(Z_Is(t)) is even at each time.The spatial mollifier can be chosen even.Source: Then we have the bound · p. 88

5. Matching IAMP algorithms

This section develops matching incremental AMP algorithms that simulate controlled SDEs, using a Brownian-bridge revelation of the Gaussian matrix and establishing corresponding state-evolution limits and high-probability feasibility. It also presents centered and chaotic variants, analyzed through symmetry at η = 0 and continuity of state evolution as η decreases to zero.

5. Matching IAMP algorithms

  • Chaotic IAMP can achieve any feasible symmetrized endpoint measure with χ(1 − ι) ≤ ι, and in the symmetrized setting can construct large approximately ultrametric solution trees.The chaotic algorithm’s output agrees with an efficient IAMP iteration with probability 1 − e^(-cN).Source: §5 · pp. 89–90
  • Under Theorem 5.1’s control and initial-condition assumptions, a Lipschitz algorithm can mimic the specified SDE; added symmetry assumptions also permit mean-zero output.The theorem assumes Lipschitz controls and approximate constraints with tolerance ε; the spherical case is covered by setting w_t = 1 and ignoring condition (v).Source: §5 · pp. 89–90
  • When w(t,x)=w(t,−x) and the initial distribution ζ_Is is symmetric, there exists a C(L, ε)-Lipschitz algorithm satisfying part (a)’s conclusions and with expected output E_A_N(G,g_aux)=0.Source: §5 · p. 90

5.2. General form IAMP iterations.

  • A Brownian-bridge revelation of the Gaussian matrix lets IAMP multiply iterates by correlated matrices, enabling simulation of general semimartingale diffusions beyond the martingale SDEs of earlier IAMP algorithms.At each iteration, the algorithm uses the matrix Brownian motion at a chosen increasing sequence of times.Source: §5 · p. 91

5.1. AMP state evolution for multiple correlated matrices.

  • AMP with multiple correlated matrices has a state-evolution limit: pseudo-Lipschitz observables converge in probability to the corresponding limiting random variables.The section also extends the framework to long-term memory and exogenous randomness.Source: §5.1 · pp. 92–93

5.2. General form IAMP iterations.

  • The explicit IAMP iteration approximates the SDE coordinate marginals as the time step shrinks, while its two-stage construction controls errors from the approximate assumptions.The iterates approach the SDE solutions as δ → 0, with normalized approximation errors of order O(ε^(1/2)).Source: §5.2 · pp. 94–95
  • The IAMP iterates track the SDE coordinate profiles while maintaining A_l u_l ≈ x_l, so the final Gaussian projection approximates the target law.The construction uses a Brownian-bridge revelation of the Gaussian disorder.Source: §5.2 · p. 98
  • Proxy processes x_l and y_l approximate the SDE solutions with errors vanishing as δ→0 independently of ε; the rescaled process ȳ_l may instead have ε-dependent error.The coefficient functions are evaluated on the proxies so the overall error vanishes in the stated regime.Source: §5.2 · pp. 98–99
  • The state-evolution limits admit representations driven by standard Brownian motions, and their comparison with the SDE solutions uses shared driving motions.The comparison concerns the piecewise-constant state-evolution processes and the solutions of the corresponding SDEs.Source: §5.2 · pp. 99–100

5.3. Proof of IAMP diffusion limit.

  • The diffusion-limit proof establishes zero conditional means for successive Y and M increments given their respective prior filtrations.These orthogonal-increment identities are proved by induction in Lemma 5.15.Source: §5.3 · p. 100
  • Under Theorem 5.1a conditions, the IAMP iterates converge to the specified state-evolution limits, with the scaling factors Γ_l and γ_l verified to be strictly positive.The proof applies the stated convergence result after establishing positivity of these factors.Source: §5.2 · p. 97, §5.3 · p. 106
  • The IAMP output lies in the relaxed spherical or Ising domain with high probability.The construction uses a Lipschitz algorithm agreeing with the IAMP iteration with exponentially high probability.Source: §5.3 · pp. 108–109

5.4. Centering of general IAMP algorithms.

  • Under the stated symmetry conditions, centered IAMP has exact finite-dimensional symmetry and conditional mean zero, while retaining the original algorithm’s guarantees.The construction uses an odd Lipschitz initialization map and even w; its guarantees follow from the original IAMP result.Source: §5.4 · pp. 111–112

5.5. Chaotic IAMP.

  • For inputs with correlation p ≤ 1 − ε, chaotic IAMP is designed to make outputs nearly uncorrelated by generating decorrelated noise and using it in a modified IAMP iteration.Its two phases first generate noise vectors that are only o_η(1)-correlated, then incorporate them alongside the respective input matrices.Source: §5.5 · pp. 112–113
  • For fixed ℓ_init, the chaotic initialization iterates converge as N grows to independent standard Gaussian state-evolution variables.The stated limit is (Y_−ℓ_init, …, Y_−1) distributed as N(0, I_ℓ_init).Source: §5.5 · p. 113
  • At η = 0, the chaotic state-evolution variables symmetrize the earlier IAMP limits using independent symmetric random signs.The argument uses sign symmetry of the centered Gaussian processes and induction through the modified nonlinearities.Source: §5.5 · p. 118
  • State-evolution limits are stochastically continuous as η decreases to zero, enabling small positive η to approximate the symmetrized η = 0 behavior.At η = 0, the sign nonlinearity is not Lipschitz, so the standard state-evolution result does not directly apply there.Source: §5.5 · p. 118
  • A preliminary chaotic-IAMP-based algorithm is extended to a globally Lipschitz map, and sufficiently small δ and η yield the required Lipschitz algorithm.The construction first meets the requirements of Theorem 5.1c except those involving the correlation function χ.Source: §5.5 · pp. 119–120
  • The constructed algorithm’s correlation function is shown to approximate zero, with χ(1 − ι) ≤ χ(p) ≤ ι in the stated limiting regime.The section announces Theorem 5.32 under the assumptions of Theorem 5.1c.Source: §5.5 · pp. 120–121

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

The section completes a covariance-control argument for Theorem 5.32 and develops how chaotic IAMP can yield large approximately ultrametric solution trees, noting when explicitly branching IAMP applies. For even activations, the construction uses approximately orthogonal future trajectory increments and Lipschitz concentration to produce a branching tree with controlled pairwise overlaps.

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

  • The proof of Theorem 5.32 inductively propagates orthogonality relations, using the recursion and joint Gaussianity to establish each step.It then uses covariance bounds and second-moment control to show that the coupled V-increment correlation and D_V(j+1) vanish as η tends to zero.Source: (We note that the order of parameters… · pp. 121, 122, 125

5.6. Constructing solution trees for even activations.

  • For small enough δ and ε, with probability 1 − e^(−cN), any good parameter choice admits K = e^(cN) outputs forming a large approximately ultrametric tree.The outputs lie in Σ_N(ι) or S_N(ι); they can be generated by applying the chaotic IAMP algorithm to suitably correlated Gaussian inputs.Source: §5.6 · pp. 126–127
  • Explicit branching IAMP can apply when the optimal function p equals one on a nontrivial interval, a case associated with a tree root having self-overlap strictly between zero and one.Branching IAMP was proposed for mean-field spin glasses in [AM20] and analyzed in [Sel24, Sec. 4] and [HS24, Sec. 3.3].Source: §5.6 · p. 127
  • A depth-k, width-e^{cN} tree has pairwise overlaps within ε of q̃_j when the pair’s least common ancestor is at depth j.The construction relies on approximately orthogonal future increments and Lipschitz concentration; the outputs have asymptotic overlap q_j under the stated condition.Source: §5.6 · p. 128

6. Eqivalence and continuity of stochastic control problems

This section relates stochastic-control classes that describe attainable endpoint measures, establishing equivalences and inclusions and simplifying their descriptions through control adjustments. It also proves continuity and approximation results for these classes under changes in the budget, control function, and endpoint conditions.

6. Eqivalence and continuity of stochastic control problems

  • For the Ising setting, Lipschitz-algorithm limits coincide with endpoint laws of the clean control problem, and concave p with p(0)=0 suffices to attain them.The clean formulation starts at q0=0, removes the o_L(1) terms, and allows progressively measurable controls subject to budget constraints; the spherical setting has analogous results.Source: §6 · p. 129
  • The proof equates the IAMP, BOGP, and ideal control-law classes through inclusions, using both approximation of feasible controls and the algorithms’ control interpretation.The inclusion cycle also shows that endpoint laws allowed from arbitrary starting times q0 are attainable with q0=0; the argument uses algorithmic results rather than stochastic control alone.Source: §6 · pp. 129–131
  • For symmetrized endpoint laws, the attainable set is characterized by the simpler control problem with p=1, leaving only σ and w as controls.The result follows through a similar inclusion argument, with the symmetric setting allowing general controls to be simulated by algorithms whose correlation functions approach the required condition.Source: §6 · pp. 130–131
  • Both the Ising attainable-law set and its symmetrized counterpart vary continuously with α in the Hausdorff metric induced by W2.The two set-valued maps are α ↦ ℳ̄_Is(α) and α ↦ ℳ̄_Is,sy(α).Source: §6 · p. 130

6.1. Definitions of measure classes.

  • The measure classes organize controlled processes under differing regularity, budget, initialization, and endpoint conditions, and their achievable X(1) laws become equivalent in the stated limit.The classes interpolate between IAMP, BOGP, and ideal formulations.Source: §6.1 · pp. 132–134
  • At q0=0, the measure classes coincide, including the xii, ideal, and ideal* classes; for q0∈[0,1), M_Lip(alpha,q0)=M_Lip(alpha,0)=M_ideal(alpha,0)=M_ideal*(alpha,0).Source: §6.1 · pp. 136–137

6.2. Approximations of Lipschitz algorithms.

6.3. Consequences of earlier results.

  • For every q0∈[0,1), M_IAMP(alpha,q0)⊆M_Lip(alpha,0), M_Lip(alpha,q0)⊆M_BOGP(alpha,q0), and M_xi(alpha,q0)⊆M_IAMP(alpha,q0).Source: §6.3 · pp. 141–143
  • For any target law in the stated class, the construction achieves W2 error at most ε; taking a union over L and an intersection over ε completes the argument.The construction applies to any μ in the class specified in the proof.Source: §6.3 · p. 144

6.4. Simple adjustments.

  • Simple control adjustments establish the inclusions M^i ⊆ M^ii ⊆ M^iii ⊆ M^iv ⊆ M^v and M^x ⊆ M^xi for all q0 ∈ [0,1).The adjustments modify controls to meet the next class’s conditions while preserving or approximating the resulting processes.Source: §6.4 · p. 145
  • Simple adjustments construct controls satisfying Adm_x(α,q0; L, ε) while preserving the required conditions.Source: §6.4 · p. 152

6.5. Continuity in the budget.

  • The budget-to-endpoint-measure-set map is uniformly continuous, and this yields the inclusion M^v(α,q0) ⊆ M^vi(α,q0).Source: §6.5 · p. 152

6.6. Continuity in the function 𝑝.

  • The section proves M^x(α,q0) ⊆ M^xii(α,q0), M^ix(α,q0) ⊆ M^ideal*(α,q0), M^vi(α,q0) ⊆ M^vii(α,q0), M^xii(α,q0) ⊆ M^x(α,q0), and M^ideal(α,0) ⊆ M^xii(α,0).Source: §6.6 · p. 154
  • For fixed q0 and budget f, the endpoint-measure set map p ↦ M(q0; p, f) is uniformly continuous under the stated metrics.The function p is metrized by the L1 distance between its derivatives, and the endpoint-measure sets by Hausdorff distance.Source: §6.6 · p. 154
  • When p and p-tilde agree on [ε,1], endpoint measures can be approximated with squared W2 distance at most 9(1 + 1/α)ε.At q0 = 0, this yields inclusion of the ideal endpoint-measure class in the xiip class.Source: §6.6 · pp. 158, 160

6.7. Ising endpoint condition.

  • For every q0 in [0,1), the cited lemma establishes the inclusion from the relaxed to the exact Ising endpoint class; its proof approximates the exact endpoint condition by the relaxed condition.Source: §6.7 · pp. 160, 164

6.8. Simplification to p = 1 for symmetrized endpoint measures.

  • Symmetrization is a contraction in W2, supporting the passage from attainable measures to symmetrized classes.The paper also establishes compactness of the inverse image of a measure under symmetrization in the W2 metric.Source: §6.8 · pp. 170–171
  • The symmetrized measure classes from Lip through IAMP coincide, and M_Lip,sy(α) equals M_ideal,sy(α, 0) and the closure of the symmetric Ising class.The proof establishes a cycle of inclusions among the intermediate classes, then identifies their common set with the ideal class and the closure of the symmetric Ising class.Source: §6.8 · p. 171
  • The inclusion from symmetrized IAMP measures to symmetrized Lipschitz measures uses an additional algorithmic property that yields a stronger BOGP control condition.The stronger condition requires p(ε) ≥ 1 − ε.Source: §6.8 · p. 173

6.8. Simplification to p≡1 for symmetrized endpoint measures

  • M Lip,syp(α, 0) ⊆ M BOGP,syp(α, 0), as established by Lemma 6.50.The proof uses Lipschitz algorithms and perturbation estimates to place their symmetrized endpoint measures in the BOGP class.Source: §6.8 · p. 174
  • Lemma 6.51 reduces the vi-class condition p(ε) ≥ 1−ε to p≡1 while approximating symmetrized endpoint measures.For a vi-class measure, the proof constructs a vii-class measure whose symmetrization satisfies the approximation bound (6.61).Source: §6.8 · p. 175
  • The lemma also treats the ideal and x classes by replacing p with a smooth proxy that agrees with it on [ε, 1].The proxy has value ε/2 at 0 and a C2 norm bounded by 4/ε²; the argument applies when L ≥ 4/ε².Source: §6.8 · p. 176

7. Confinement of Lipschitz achievable measures to ideal set

Section 7 establishes that Lipschitz-algorithm projection measures approach the ideal sets in W_q for q<2, a weaker metric that handles sequences lacking W_2-convergent subsequences. It proves this confinement by truncating influential rows and also introduces a concentration estimate for the main achievability and hardness proofs.

7. Confinement of Lipschitz achievable measures to ideal set

  • For every q in [1,2), projection measures from approximate Lipschitz algorithms are asymptotically confined to the ideal Ising sets in W_q; the spherical result omits the approximate-algorithm hypothesis.The same confinement applies to symmetrized measures and their corresponding ideal set.Source: §7 · p. 177

7.1. Confinement of averaged inner product distributions

  • Truncating an algorithm by replacing rows with large expected inner products by independent Gaussian rows yields a measure close to the original in W_q for q<2.The truncation supports the confinement proof by controlling the effect of influential rows before applying compactness.Source: §7.1 · pp. 178, 182, 184

7.2. Proofs of main achievability results

  • The achievability proofs introduce a concentration estimate that is also used in the section’s hardness proofs.The estimate is stated for fixed measures and Lipschitz algorithms, for q in [1,2].Source: §7.2 · p. 184

We then have the bounds

The section proves that Lipschitz algorithms attain the characterized general and symmetric projection distributions, then develops the corresponding hardness proofs and opens the perceptron-threshold corollary proof.

We then have the bounds

  • For both general and symmetric settings, Lipschitz algorithms attain every distribution in the corresponding characterized feasible set to arbitrary accuracy.The proofs use the equality between each feasible set and its IAMP characterization, then construct an algorithm that attains the target with probability approaching one.Source: We then have the bounds · pp. 186–187

7.3. Proofs of main hardness results.

  • For general and symmetric settings, sufficiently accurate algorithmic projections remain close to the corresponding feasible set; the hardness proofs apply this separation to exact and approximate Lipschitz algorithms.The separation parameter determines an approximation tolerance, and the theorem proofs split between algorithms already close to the cube and those that are approximate Lipschitz algorithms.Source: §7.3 · pp. 189–190

7.4. Algorithmic threshold for perceptron model.

  • The perceptron-threshold subsection opens the proof of Corollary 1.14 with a simple lemma.The supplied passage introduces the proof but does not state the lemma or the corollary’s result.Source: §7.4 · p. 191

Then the function · Appendix A. Moment estimates and tightness · A.1. Preliminary estimates.

The section establishes continuity tools for transferring projection-measure approximations, then develops moment and Lipschitz estimates used to prove scaling limits and concentration for the tree-revelation processes.

Then the function

  • Uniform continuity of f_phi on the W1-compact closure lets W1 approximations control bounded-continuous observables.The proof uses compactness and sequential continuity of f_phi.Source: Then the function · pp. 191–192

Appendix A. Moment estimates and tightness

  • The appendix studies tree-revelation processes at discrete times with steps of order delta, focusing on the more difficult Ising case.It defines truncated, smoothed, spatially bucketed, and rerandomized variants of the processes.Source: Appendix A · p. 193
  • The processes Y and Y+ have scaling limits with semimartingale decompositions, and their drift and covariation limits match those of the limiting processes.Under Assumption 2.12, Y, Y+, D, D+, Q, and Q+ have subsequential continuous scaling limits.Source: Appendix A · p. 193

A.1. Preliminary estimates.

  • The preliminary estimates show that x-bar is Lipschitz in the Gaussian disorder and its centered vector is subgaussian with variance proxy LO(1).The proof derives the Lipschitz bound through the algorithm’s Lipschitz property and then applies Gaussian concentration.Source: §A.1 · p. 194
  • Conditioned on the revealed disorder, y has mean zero and is subgaussian with variance proxy LO(1).Its Lipschitz dependence on the disorder yields the subgaussian estimate.Source: §A.1 · p. 194
  • The process increments are approximately Lipschitz on U_M, yielding empirical averages with Lipschitz scale LO(1)/(delta sqrt(N)).For the Ising increments, the Lipschitz bound holds on the full space; the other listed increments require restriction to U_M.Source: §A.1 · pp. 194–196

A.2. Estimates on preprocessing errors. … A.5. Moment estimates for quadratic variation.

These sections establish error and moment estimates for preprocessing, spatially rerandomized processes and their drifts, and quadratic-variation processes and their approximations. They identify asymptotically relevant processes and combine estimates toward tightness of the Y, D, and Q processes.

A.2. Estimates on preprocessing errors.

  • Each preprocessing step can be coupled to incur negligible W2 error in the endpoint distribution.The result covers X, Xtr*, X+*, Xtr, and X+.Source: §A.2 · p. 196

A.3. Moment estimates for process.

  • Spatial rerandomization has a controlled increment error relative to Xtr, with the same estimate applying to Y+ and X+.Source: §A.3 · p. 204
  • Quenched second-moment bounds hold for X and also for Xtr and X+, uniformly across the stated time range.The proposition takes expectations over sampled indices independently of the Gaussian disorder.Source: §A.3 · p. 205
  • Quenched second-moment bounds also hold for YI and YI,+, with the same bound applying to Y+.Source: §A.3 · p. 206
  • Lemma A.15 gives moment bounds for sampled process increments, including corresponding bounds for the modified and plus processes.The estimates cover the stated time range and several process variants; the supplied passages omit the bound formulas.Source: §A.3 · p. 206

A.4. Moment estimates for drift.

  • The approximate drift processes for component I are identified as the only asymptotically nontrivial ones, and Proposition A.18 gives estimates for them and their plus versions.The supplied passages state that the original and approximate drifts are close, but do not show the estimate formulas.Source: §A.4 · p. 209

A.5. Moment estimates for quadratic variation.

  • After subtracting the associated drift, the Z processes are martingales, and the section defines piecewise linear quadratic-variation and covariation processes Q for them.The definition makes Q symmetric in its process indices and sets Qσ to Qσ,σ.Source: §A.5 · p. 214
  • Only Q^II, Q^II,III, Q^III, and Q^Is survive asymptotically; the Q^I,σ and Q^σ,Is processes are negligible.The same asymptotic statement is asserted for the Q+ processes.Source: §A.5 · p. 215
  • Proposition A.29 gives large-N estimates for quadratic-variation processes, including the Ising and Q+ variants.The supplied passages do not show the estimates’ formulas.Source: §A.5 · pp. 215–216
  • Lemma A.30 bounds the difference between Q and its approximation Q̃, with the same bound for the Q+ processes.The bound applies to all listed σ, τ process pairs.Source: §A.5 · p. 216
  • The appendix provides first-moment bounds for Q processes and for E^σ,τ terms, with corresponding bounds for Q+ and E+ variants.These include quenched bounds on Q^σ and annealed bounds on E^σ,τ for σ, τ in {II, III, Is}.Source: §A.5 · pp. 218–219
  • Lemma A.34 gives an annealed second-moment bound for Ẽ^III, also valid for Ẽ+^III.The bound is stated for each interval indexed by d from 0 to d_max − 1.Source: §A.5 · p. 219
  • Combining estimates from subsections A.3–A.5 proves tightness of the Y, D, and Q processes as N grows and η and δ vanish under Assumption 2.12’s scaling.The proof is given for the Ising case; the spherical case is stated to be simpler.Source: §A.6 · p. 220

A.6. Tightness.

This section establishes tightness and identifies the structure of subsequential limits, including for the “+” variant. These results provide the ingredients used to prove Theorem 2.13.

A.6. Tightness.

  • The random measures ℚ_N are tight, and every subsequential limit has error process ℰ identically zero; the “+” variant satisfies the same conclusions.Along a suitable coupling, the error processes converge uniformly to zero.Source: §A.6 · pp. 221–222
  • The result bounds p_σ(Ξ) by ō_K(1) for every σ ∈ {I, II, III, Is}, holding with probability at least 1 − exp(−N^(1/2)).Source: §A.6 · p. 223
  • Piecewise constant process laws converge along the same subsequences as the continuous-process laws, and this also holds for the “+” variant.This transfers the subsequential convergence result to the piecewise constant versions of the processes.Source: §A.6 · p. 225
  • In any subsequential limit, Γ has finite variation and Υ is a martingale, with covariations of Z_σ and Z_τ given by Q_σ,τ and Q_σ,Is = 0 for σ ∈ {II, III}.The “+” variant has the same limiting-process properties.Source: §A.6 · p. 226

Appendix B. Derivation of budget constraint

Appendix B proves the budget constraints of Theorem 2.19: under the stated Gaussian, Lipschitz, and partition assumptions, the random vector satisfies constraints (B.9) with high probability. The proof reduces the probabilistic bound to a deterministic optimization and then controls that optimization through concentration and Gaussian comparison.

Proposition B.1

  • With probability at least 1 − e^(−cN), the random vector satisfies the budget constraints (B.9) for all sufficiently large N under Proposition B.1’s assumptions.The positive constant c depends on α, L, ι, and ϵ.Source: Appendix B · p. 229

B.1

  • For fixed partition proportions and projection direction, Proposition B.2 upper-bounds the random projection by a deterministic constrained maximum, then uses a polytope approximation and union bound to establish Proposition B.1.The approximation controls the number of facets uniformly in key parameters; the deterministic maximum is also reduced to a simplified optimization problem.Source: Appendix B · p. 229

B.3–B.4

  • To handle partitions depending on the Gaussian data, the proof uses uniform concentration to reduce to deterministic partitions and then bounds an associated random-matrix top eigenvalue.It first controls an optimization over k orthogonal sphere points; concentration for each fixed partition supports a union bound over partitions when k is sufficiently large.Source: Appendix B · p. 230

B.5–B.7

  • Slepian and Gordon Gaussian comparison replace the deformed Wishart term with Gaussian linear terms, after which Lagrange multipliers and a non-variational formula complete the bound.The comparison yields a minimax problem that is bounded by the simplified optimization; the latter is evaluated in §B.6 and used to bound the minimax problem in §B.7.Source: Appendix B · p. 230

B.1. Linear projections of statistics. · B.2. Upper bound on number of facets in polytope approximation.

This section develops a finite-polytope framework for feasible sets, beginning with normalized one-dimensional projections of statistics. It establishes continuity of the sets as parameters vary and a uniformly bounded facet count for closed D_mu-polytopes approximating them across parameter pairs in Λ.

B.1. Linear projections of statistics.

  • A normalized projection direction turns the statistics vector into a linear objective, which is maximized over the ideal feasible set.The appendix introduces this projection framework as an input to the proof of Proposition B.1.Source: §B.1 · p. 231
  • For each parameter pair, an epsilon-neighborhood of the ideal feasible set lies in a polytope with at most C_pol facets and a stated cost-and-budget bound.The constants epsilon_1 and C_pol depend only on alpha, iota, and epsilon; the exact cost-and-budget inequality is not visible in the supplied passage.Source: §B.1 · p. 232

B.2. Upper bound on number of facets in polytope approximation.

  • The facet-count proof starts with a crude bound on the set in (B.42), using Cauchy–Schwarz and the constraint (mu, w) = 1.The displayed bound involves iota and min{1, alpha}, but its full expression is not visible in the supplied passages.Source: §B.1 · p. 232, §B.2 · pp. 238–239
  • The map from (λ, μ) to S*(λ, μ; ε1, ε2), and the map to its ε-neighborhood, are continuous in Hausdorff distance.These continuity results apply for parameters in Λ and nonnegative ε1, ε2, and ε.Source: §B.2 · pp. 239, 241
  • A positive margin ε1 can be chosen uniformly over Λ because its parameter-dependent value is positive and continuous there.The proof establishes pointwise positivity, proves continuity, and then takes the infimum over Λ.Source: §B.2 · pp. 242–243
  • For each (λ, μ) in Λ, a closed D_μ-polytope can contain the ε1-neighborhood of S*(λ, μ) while remaining inside K2, with both bounding sets convex bodies.The proof constructs the polytope by separating the boundary of K2 from the ε1-neighborhood of S*(λ, μ).Source: §B.2 · pp. 243–244

B.2. Upper bound on number of facets in polytope approximation

  • The proof thickens the constructed half-spaces by a common positive amount, using lower semicontinuity and compactness to obtain a uniform choice over a parameter neighborhood.For each nearby parameter pair, the allowable thickening is positive; its lower semicontinuity on the compact neighborhood yields a positive infimum.Source: §B.2 · pp. 247–248
  • The construction also establishes the needed set inclusions for nearby parameter pairs by controlling perturbations of the sets involved.The proof uses the separation of the relevant sets and a perturbation bound to obtain the left-most inclusion in (B.52).Source: §B.2 · p. 248
  • For every (lambda, mu) in Λ, a closed D_mu-polytope exists with at most Cpol facets, where Cpol depends only on alpha, iota, and epsilon.The supplied passage truncates the further condition the polytope satisfies, so it is not specified here.Source: §B.2 · pp. 248–249

B.3. Reduction to optimization over many orthogonal replicas. · B.4. Application of uniform concentration.

This section reduces the original quantity to optimization over orthogonal replicas and uses uniform concentration to bound that optimization across partitions. It also uses Gaussian rotational invariance and uniform concentration to show that, for sufficiently large N, Fv approximately stochastically dominates Fiv.

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

  • F is approximately stochastically dominated by Fii(k), defined by maximizing an average over k orthogonal replicas.The replicas have norm √N and are mutually orthogonal (and orthogonal to x̄ in the initial construction).Source: §B.3 · pp. 249–250
  • Fiii(k) approximately stochastically dominates Fii(k), simplifying the expression by removing dependence on x̄ and allowing an arbitrary partition.This prepares the reduction to a deterministic partition in the next subsection.Source: §B.3 · pp. 253–254

B.4. Application of uniform concentration.

  • For a fixed partition independent of G, Fiv approximately stochastically dominates Fiii(k) for the random partition, using uniform concentration over all partitions.For each fixed partition, the k-replica average concentrates with failure probability e^-ckN; sufficiently large k permits a union bound over partitions.Source: §B.4 · pp. 255, 257, 258
  • Uniform concentration and a union bound extend the bound across the partition family, whose size is at most e^O(N), yielding the stated high-probability conclusion.The proof takes k sufficiently large, depending only on the parameters in Remark B.19.Source: §B.4 · p. 258
  • For sufficiently large N, Fv approximately stochastically dominates Fiv.The stated comparison holds for all real t.Source: §B.4 · p. 258
  • Gaussian rotational invariance identifies the distribution of the process defining Fiv with a transformed process that is dominated by a comparison process.The proof then bounds the difference between the comparison process and its transformed version uniformly over vectors of norm √N.Source: §B.4 · p. 259

B.5. Application of gaussian comparison inequalities. · B.6. Non-variational description of 𝐹˛.

This section uses Gaussian comparison inequalities to reduce bounds on F through Fv and Fvi to F˛, and gives an equivalent non-variational description of F˛ using V evaluated at z‹. It establishes properties of the scalar functions involved and concludes that Fvi is, with very high probability, approximately upper bounded by F˛.

B.5. Application of gaussian comparison inequalities.

  • The comparison reduces the proof of Proposition B.2 to bounding Fvi in terms of F˛, and the resulting final bound is at most e⁻ᶜᴺ.The reduction uses Propositions B.20, B.23, B.24, B.27, B.28, and B.7.Source: §B.5 · pp. 260–262
  • Slepian’s and Gordon’s inequalities yield stochastic domination of Fv by Fvi.The comparisons are applied to the respective processes defining the positive and negative components.Source: §B.5 · p. 261

B.6. Non-variational description of 𝐹˛.

  • V is strictly convex and tends to infinity, so it has a unique minimizer zmin on [z0, ∞).When the condition (B.88) fails, zmin is the unique solution to V′(z) = 0 for z > z0.Source: §B.6 · pp. 263–264
  • F˛ equals V(z‹), giving an equivalent non-variational formula for the quantity defined variationally in (B.40).The result is established for each of the three cases describing z‹.Source: §B.6 · pp. 264, 268
  • When (B.88) holds and x̂ ≤ 0, z‹ = zmin = z0; otherwise z‹ is either zmin or m⁻¹(α/x̂), according to the stated conditions.In the latter cases, zmin is the unique root of V′(z) = 0 when (B.88) fails, and m⁻¹(α/x̂) applies when x̂ > α/m(zmin).Source: §B.6 · p. 264
  • Outside case (1) of Remark B.35, every local maximizer of F˛ has an entrywise positive vector w.This property supports the Lagrange-multiplier calculation for the non-variational formula.Source: §B.6 · p. 265
  • The function defining βmin is strictly convex and diverges at both interval endpoints, giving a unique minimizer that is strictly increasing in γ.Source: §B.6 · p. 268
  • For γ > 0, g is differentiable with g′(γ) = m(β*(γ)), β* is nondecreasing, and g(γ) = Θ(γ^1/2) as γ → ∞.At γ = 0, g has a finite right derivative if x̂ > 0, but no finite right derivative if x̂ ≤ 0.Source: §B.6 · p. 268
  • At γ‹ = γ(z‹), the parameter functions satisfy β*(γ‹) = z‹.This identity holds in both cases used to define z‹.Source: §B.6 · pp. 269–270
  • The functions m^-1(1/z), g(γ²), and β*(γ²) are Lipschitz, with common bound C6 = 2/ι.Source: §B.6 · p. 271
  • With very high probability, Fvi is approximately upper bounded by F˛, as asserted in Proposition B.29.The argument uses the characterization F˛ = V(z‹) from Proposition B.34.Source: §B.7 · p. 272

B.7. Conclusion of proof.

The proof completes Proposition B.29 in cases (2) and (3) by deriving the optimizer through a scalar fixed-point equation and bounding an auxiliary constrained optimization value. It supports the upper bound with high-probability and structural estimates, control of the optimizer’s parameter near its target, and an approximate stochastic-domination comparison.

Heuristic derivation

  • The heuristic optimization selects beta*(gamma): beta_min when x_hat is below the threshold, and m^-1(alpha/x_hat) otherwise.The argument seeks the largest feasible beta, using the threshold alpha/m(beta_min) to distinguish the two cases.Source: §B.7 · p. 274
  • The fixed-point equation has at most one solution, and gamma* satisfies it, making gamma* its unique solution.The proof shows the left-hand side increases while the right-hand side is nonincreasing; it then verifies that gamma* satisfies the equation.Source: §B.7 · pp. 275–276

Rigorous proof

  • With probability at least 1 − e^(-cN), the supremum over theta+ is attained at a point with norm at most C8 sqrt(N).The bound applies for any y with norm sqrt(N), with C8 depending on alpha and iota.Source: §B.7 · p. 276
  • With exponentially high probability, F_vi is approximately stochastically dominated by F_vii for all real t.Proposition B.44 establishes the comparison using a restricted supremum domain and a choice of the infimum parameter guided by the heuristic calculation.Source: §B.7 · p. 277
  • Uniform Gaussian concentration bounds hold with exponentially high probability over beta and bounded coefficient vectors.Lemma B.46 gives the bounds simultaneously for beta in the stated range and coefficient vectors with bounded infinity norm.Source: §B.7 · pp. 278–279
  • Every local maximizer of V_gamma on the sphere has the stated resolvent form, with its parameter beta at least w_hat1.The result follows from the Lagrange-multiplier characterization and the necessary Hessian condition for a local maximum.Source: §B.7 · p. 280

B.7. Conclusion of proof.

  • Proposition B.49 shows that Fvii is approximately stochastically dominated by Fviii for all t in R.The proof uses Proposition B.45 to upper-bound the supremum over vectors of norm N^1/2, up to a small additive error, by a g-term; the comparison holds with probability at least 1 - e^-cN.Source: §B.7 · p. 284
  • The proof of Proposition B.50 handles vhat_1 <= delta_2 separately, where the optimization over theta+ is trivial when vhat_1 < 0 or can be bounded crudely when vhat_1 is small and positive.This is the complementary case to the optimizer-control argument for vhat_1 > delta_2.Source: §B.7 · pp. 285–286
  • For vhat_1 > delta_2, the proof of Proposition B.50 establishes Fviii ≤ V(z*) + O(delta^1/2), and choosing delta sufficiently small, depending only on Remark B.30 parameters, concludes the proof.Source: §B.7 · pp. 288–289
  • Under cases (2) and (3) of Remark B.35, Proposition B.29 follows from Propositions B.34, B.44, B.49, and B.50; case (1) was proved earlier.This closes the proof of Proposition B.29 for the cases handled here.Source: §B.7 · p. 290
Loading 2608.29416v1…