PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models

Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, Lenka Zdeborová

arXiv:1708.03395v3cs.ITcond-mat.dis-nncs.AIcs.LGmath-ph

TL;DR

The paper studies optimal inference and prediction in random high-dimensional GLMs, where rigorous nonlinear results and their algorithmic attainability remain incomplete. It derives free-entropy formulas and Bayes-optimal errors using adaptive interpolation, then connects them to GAMP and characterizes algorithmic phase transitions. The results validate replica predictions, identify regimes where GAMP is optimal or suboptimal, and expose sharp gaps between information-theoretic and algorithmic thresholds.

  • Problem

    Rigorous information-theoretic results were incomplete for nonlinear GLMs, while GAMP performance was not generally known to be optimal.

  • Method

    The paper rigorously evaluates free entropy and derives Bayes-optimal estimation and generalization errors using adaptive interpolation, then compares them with GAMP state evolution.

  • Results

    The analysis validates replica predictions and identifies parameter regions where GAMP reaches optimal performance, alongside sharp algorithmic phase transitions.

  • Takeaways & Limitations

    Random GLMs provide analytically characterized benchmarks for studying the gap between information-theoretic limits and efficient algorithms.

  • Takeaways & Limitations

    The GAMP estimation-error result is stated as a claim because earlier proofs were incomplete or lacked details.

Abstract

from arXiv · show

Generalized linear models (GLMs) arise in high-dimensional machine learning, statistics, communications and signal processing. In this paper we analyze GLMs when the data matrix is random, as relevant in problems such as compressed sensing, error-correcting codes or benchmark models in neural networks. We evaluate the mutual information (or "free entropy") from which we deduce the Bayes-optimal estimation and generalization errors. Our analysis applies to the high-dimensional limit where both the number of samples and the dimension are large and their ratio is fixed. Non-rigorous predictions for the optimal errors existed for special cases of GLMs, e.g. for the perceptron, in the field of statistical physics based on the so-called replica method. Our present paper rigorously establishes those decades old conjectures and brings forward their algorithmic interpretation in terms of performance of the generalized approximate message-passing algorithm. Furthermore, we tightly characterize, for many learning problems, regions of parameters for which this algorithm achieves the optimal performance, and locate the associated sharp phase transitions separating learnable and non-learnable regions. We believe that this random version of GLMs can serve as a challenging benchmark for multi-purpose algorithms. This paper is divided in two parts that can be read independently: The first part (main part) presents the model and main results, discusses some applications and sketches the main ideas of the proof. The second part (supplementary informations) is much more detailed and provides more examples as well as all the proofs.

1 Introduction

The paper studies random high-dimensional GLMs, which unify estimation and prediction tasks across signal processing, learning, neural networks, and communications. It addresses the gap between rigorous information-theoretic results and non-rigorous predictions for nonlinear models by establishing optimal errors and comparing them with GAMP.

  • Model and applications: Random GLMs generate observations from a hidden signal through a random measurement matrix and a potentially nonlinear or stochastic output function.The matrix entries are independently sampled with zero mean and unit variance, while the signal is randomly generated from a prior distribution.
  • Model and applications: The framework covers estimation of the hidden signal and prediction of new outputs from additional data points.Estimation infers X∗ from Y and Φ, whereas generalization predicts Ynew using a new row of Φ.
  • Model and applications: Applications include compressed sensing, quantized and 1-bit measurements, phase retrieval, statistical learning, neural networks, and random error-correcting codes.These settings differ through the output function ϕ and include both linear and nonlinear observations.
  • Research gap: Prior work separately analyzed GAMP algorithmically and established optimal performance mainly for linear Gaussian models, leaving a gap for nonlinear GLMs.Nonlinear information-theoretic results largely relied on non-rigorous cavity and replica methods.
  • Contribution: The paper rigorously validates replica-method predictions for GLMs and relates the resulting optimal estimation and generalization errors to GAMP performance.It also compares information-theoretic results with GAMP and studies algorithmic behavior across parameter regimes.

2 Main results

The paper derives rigorous information-theoretic formulas for random GLMs, including free entropy, estimation error, and generalization error, and connects them to GAMP through state evolution. It also identifies conditions under which GAMP is optimal and examples where algorithmic and information-theoretic thresholds differ.

  • Bayes-optimal inference: The Bayes-optimal estimator uses the posterior distribution generated from the known prior P0 and likelihood Pout in the random GLM.For squared-error signal estimation, the posterior mean minimizes mean-square error.
  • Information-theoretic results: The free entropy converges in probability in the high-dimensional limit n, m →∞ with m/n →α, extending rigorous results beyond linear Gaussian outputs.The expression matches replica-symmetric formulas and rigorously establishes conjectures from statistical physics.
  • Information-theoretic results: The resulting formulas determine the asymptotic MMSE and Bayes-optimal generalization error from the free entropy and its maximizing parameters.For discrete labels, the optimal predictor instead uses posterior marginals and their argmax.
  • Algorithmic interpretation: GAMP is asymptotically optimal when its state-evolution fixed point matches the extremizer of the free-entropy potential.State evolution tracks the overlap between the true signal and the estimate, while GAMP performance can be compared with the optimal errors.

3 Application to learning and inference

The paper applies its theory to phase transitions in sparse recovery and classification, comparing information-theoretic limits with GAMP performance. These examples reveal hard phases, algorithmic gaps, and benchmark opportunities for general-purpose learning algorithms.

  • Applications: The analysis determines information-theoretic and algorithmic phase transitions for several nonlinear sensing and classification problems.The examples vary output functions, priors, and sample complexity to compare optimal errors with GAMP predictions.
  • Fixed points: The non-informative fixed point makes GAMP perform as badly as random guessing for α < αc, whereas α > αc allows state evolution to grow from infinitesimal positive overlap.For almost exact recovery, the relevant fixed point is q∗ = ρ, and its stability depends on both the output channel and prior.
  • Sparse recovery: αIT = ρ for sign-less sparse recovery, matching canonical compressed sensing, but GAMP requires α > 1/2 even for very sparse signals.For dense signals, GAMP needs αAMP(ρ = 1) ≈1.128; losing measurement signs creates the algorithmic difficulty.
  • Sparse recovery: ReLU measurements retain the information-theoretic cost of twice canonical compressed sensing, while GAMP recovers almost exactly below that doubled algorithmic threshold.Negative outputs are uninformative information-theoretically but improve algorithmic performance.
  • Classification: Binary perceptrons exhibit a discontinuous optimal transition at αIT ≈1.249, while GAMP reaches perfect generalization only above αAMP ≈1.493.For Gauss-Bernoulli perceptrons, optimal generalization instead decreases smoothly with α.
  • Algorithmic benchmarks: These random GLMs provide benchmarks by comparing out-of-the-box algorithms with information-theoretic optima and problem-tuned GAMP.The comparison exposes sample-complexity and performance gaps that are difficult to assess on standard open-access datasets.

4 Methods and proofs

The paper rigorously derives the replica-symmetric free entropy for random GLMs using adaptive interpolation, then obtains mutual information and Bayes-optimal errors. The proof connects state-evolution fixed points with optimization extrema and identifies when GAMP is optimal or sub-optimal.

  • Proof strategy: Adaptive interpolation extends prior interpolation methods by using a two-parameter potential fRS(q, r; ρ) rather than a single-parameter potential.The method requires non-trivial new ingredients because earlier upper-bound arguments do not directly apply to GLMs.
  • Algorithmic interpretation: GAMP is optimal when state evolution converges to the same extremizer as the potential, and sub-optimal otherwise.State-evolution fixed points correspond algebraically to critical points of the two-variable potential.
  • Optimal errors: The mutual information and Bayes-optimal estimation and generalization errors follow from the free-entropy formula, with optimal-error formulas valid under uniqueness and moment conditions.The generalization result holds when the maximizer q∗(α) is unique; overlap and matrix-MMSE formulas additionally require all moments of P0 to be finite.
  • Interpolating estimation problem: The proof interpolates between the original GLM and two scalar inference channels, with t controlling the mixture and signal-to-noise ratios.At t = 0 the model is the original GLM; at t = 1 it becomes the scalar-channel problem.
  • Proof strategy: Choosing an optimal interpolation path establishes equality between the replica formula and the limiting free entropy.The path uses non-trivial t-dependent signal-to-noise ratios and small perturbations to control overlaps.
  • Main theorem: Theorem 1 identifies the limiting free entropy through equivalent sup-inf and inf-sup variational formulas over q and r, under hypotheses on the prior, channel, matrix, and noise.The matching lower and upper bounds yield the variational characterization, while stronger assumptions provide convergence in probability.

1 Setting

The paper formulates random generalized linear estimation and supervised prediction in the high-dimensional regime. A latent signal, random measurement matrix, channel, and noise generate observations, while Bayes-optimal prediction concerns unseen measurements.

  • Generalized linear model: A GLM uses a latent vector X∗, random matrix Φ, output function ϕ, optional randomness A, and additive Gaussian noise to generate m observations.The matrix entries are independent, zero-mean, unit-variance random variables, and signal components are drawn independently from P0.
  • Generalized linear model: The model includes linear estimation, noisy perceptrons, quantized sensing, and nonlinear estimation through different choices of ϕ and the output channel.The channel representation treats each measurement as an output conditioned on the normalized matrix-signal product.
  • High-dimensional regime: The high-dimensional limit takes n and m to infinity while their ratio m/n approaches a positive measurement rate α.The averaged free entropy is the central thermodynamic quantity in this limit.
  • Learning tasks: The estimation task infers X∗ from Y and Φ, whereas the generalization task predicts labels for new matrix rows and corresponding outputs.The teacher-student formulation generates training data and evaluates predictions on a newly sampled pattern.
  • Learning tasks: The optimal generalization error is the minimum prediction error over all estimators using the available training data and measurements.The MMSE is likewise defined through posterior conditional expectations.
  • Scalar channels: The analysis expresses the GLM through two scalar denoising channels: an additive Gaussian channel and a channel linked to Pout.Their free entropies arise from posterior normalization factors and form the basis of the decoupling property.

2 Main results

The paper rigorously derives replica-symmetric formulas for random GLMs under broad technical assumptions, yielding asymptotic free entropy, mutual information, and Bayes-optimal estimation and generalization errors. It also connects these quantities to state evolution and characterizes when GAMP reaches optimal performance.

  • Replica-symmetric formula: Theorem 1 proves a single-letter replica-symmetric formula for the asymptotic free entropy under assumptions covering noisy and discrete noiseless output channels.The formula applies when the prior and measurement matrix satisfy moment conditions, the output function is almost-everywhere continuous, and either Δ>0 or discrete noiseless outputs are used.
  • Mutual information: The resulting free-entropy expression yields a single-letter formula for the mutual information between observations and hidden variables.The mutual-information corollary is obtained from the free-entropy theorem through scalar-channel quantities.
  • State evolution: For almost every α, the replica-symmetric optimization has a unique optimizer q*, and its critical points coincide with fixed points of state evolution.When the output channel is informative, the optimizer and the corresponding fixed-point characterization support the asymptotic inference analysis.
  • Optimal reconstruction: The optimizer q*(α) determines asymptotic signal overlap, while matrix MMSE provides the appropriate reconstruction error when sign ambiguity makes vector MSE unsuitable.For sign-invariant observations such as phase retrieval, estimating X* itself can remain impossible even though X*X*ᵀ is estimable.
  • Optimal generalization: Theorem 3 and Theorem 4 derive Bayes-optimal generalization errors for predicting a new output from a new data-matrix row.The optimal prediction error follows from the I-MMSE theorem applied to the asymptotic free entropy.
  • GAMP performance: GAMP achieves the MMSE and Bayes-optimal generalization error when its state-evolution overlap converges to q*(α), although the stated GAMP error claim is not presented as a fully proved theorem.The paper reports this convergence in many models and emphasizes that the claim underlying the GAMP formulas has missing proof details in prior work.

3 Application to concrete situations

The paper distinguishes information-theoretic recovery from algorithmic recovery, identifying non-informative, hard, and tractable phases across several GLM channels. Examples show that channel structure can preserve optimal recovery thresholds while substantially shifting the thresholds attainable by GAMP.

  • Phase definitions: The non-informative phase is characterized by Bayes-optimal estimation and generalization errors no better than random guessing.For symmetric channels, q = 0 can be a stable fixed point of the state evolution and the global optimizer of the information-theoretic potential.
  • Phase definitions: The hard phase permits perfect reconstruction information-theoretically, but GAMP cannot achieve it, leaving efficient exact recovery as an open question.GAMP can still improve generalization over the non-informative fixed point in this regime.
  • Phase definitions: The hard non-informative phase permits perfect reconstruction information-theoretically, while GAMP remains no better than random guessing.This phase is reported as absent for the linear channel, and the existence of polynomial-time exact recovery algorithms remains open.
  • ReLU channel: For the ReLU channel, perfect generalization is possible exactly when α > 2ρ, while GAMP needs a larger α beyond its spinodal transition.Zero-valued measurements do not improve the information-theoretic threshold but do provide useful algorithmic information to GAMP.
  • Sign-less channel: For sign-less sparse recovery, the information-theoretic threshold is αIT = ρ, but GAMP's algorithmic threshold approaches αs(ρ) → 1/2 as ρ → 0.Thus losing output signs leaves recovery information-theoretically comparable to compressed sensing but algorithmically more difficult.
  • Symmetric door channel: For the symmetric door channel, αIT ≥ 1 is a generic exact-recovery bound and is saturated at K = 0.67449, although GAMP cannot efficiently attain it.At this K, half of the observed measurements are negative and half positive.

4 Proof of the replica formula by the adaptive interpolation method

The proof uses adaptive interpolation to connect the original GLM to tractable scalar inference problems and establish the replica formula under stated assumptions. Regular interpolation paths, overlap concentration, and matching bounds yield the limiting free entropy characterization.

  • 4 Proof of the replica formula by the adaptive interpolation method: The proof initially assumes bounded prior support, a bounded C2 output function, and an iid Gaussian measurement matrix.The paper states that these assumptions are later relaxed in an appendix.
  • 4.1 Interpolating estimation problem: The adaptive interpolation method evolves the original estimation problem at t=0 into two analytically tractable scalar problems at t=1.Intermediate models mix the original and scalar channels through time-dependent signal-to-noise ratios.
  • 4.1 Interpolating estimation problem: The planted setting may have many state-evolution solutions, so the interpolation must be designed to track the right fixed point.This distinguishes the method from settings where only one solution exists.
  • 4.1 Interpolating estimation problem: The interpolation uses perturbations and regular functions qϵ and rϵ whose signal-to-noise dependencies can be chosen nonlinearly in t.This flexibility permits selection of an optimal interpolation path rather than a purely linear schedule.
  • 4.2 Free entropy variation along the interpolation path: The derivative of the interpolating free entropy is computed along the path, enabling comparison between the original and scalar inference models.The resulting derivative identity is formalized as Proposition 3.
  • 4.3 Overlap concentration and fundamental sum rule: Overlap concentration and the fundamental sum rule control the interpolation when qϵ(t) matches the expected overlap.These results provide the central intermediate identities used to compare endpoint free entropies.
  • 4.4 Lower and upper matching bounds: Matching lower and upper bounds establish the limiting free entropy as both sup_r inf_q fRS(q,r) and sup_q inf_r fRS(q,r).The proof derives the lower and upper bounds separately and then identifies the equivalent variational forms.

5 Proofs of the limits of optimal errors

The paper derives optimal generalization errors by augmenting the teacher-student model with vanishing test-label side information. It then proves matching bounds and related overlap and mutual-information results through interpolation and concavity arguments.

  • 5 Proofs of the limits of optimal errors: The generalized optimal error is obtained from a train-test observation model and the I-MMSE relation.The interpolation method is extended to incorporate the additional side information needed for the derivation.
  • 5 Proofs of the limits of optimal errors: The proof introduces training and test sets, with test patterns revealed but test labels supplied only through vanishing side information.The limit λ, ϵ →0 recovers the setting where test labels are unavailable to the student.
  • 5 Proofs of the limits of optimal errors: The vanishing-side-information calculation yields Ef(q∗(α)) for the asymptotic generalization error.The argument relies on taking the large-n and vanishing-information limits in the appropriate order and relating the scalar expression to the replica optimizer.
  • 5 Proofs of the limits of optimal errors: Concavity and uniqueness arguments establish differentiability of the perturbed variational quantities required by the I-MMSE calculations.The minimizer is unique away from the excluded perturbation set, supporting the derivative-based proof.
  • 5 Proofs of the limits of optimal errors: Lower and upper bounds on the generalization error are proved using auxiliary side-information models, continuity, and properties of the optimizer.The upper-bound result is stated as Corollary 6.
  • 5.3.1 Upper bound on the overlap: A perturbed-model mutual-information formula supplies the variational identity used in the converse upper-bound argument.The converse rewrites the limiting expression using a change of variables and identifies the maximizing overlap.
  • 5.3.1 Upper bound on the overlap: The proof also establishes an upper bound on the overlap, namely |Q| ≤ q∗(α) almost surely.The result is stated separately as Lemma 13.

A.5 Derivative of the interpolating free entropy: Proof of Proposition 3

The proof differentiates the free entropy of the interpolating model with respect to the interpolation parameter. Gaussian integration by parts, the Nishimori identity, and control of a remainder term yield Proposition 3.

  • A.5 Derivative of the interpolating free entropy: Proof of Proposition 3: The derivative calculation begins by expressing the interpolating free entropy through the Hamiltonian and its t-derivative.The output-channel log-likelihood derivatives and overlap Q enter the resulting terms.
  • A.5 Derivative of the interpolating free entropy: Proof of Proposition 3: The remaining quantity A_n,ϵ is shown to vanish uniformly in t as n→∞, completing the proof of Proposition 3.The uniform convergence is established under hypotheses (H1)–(H3).
  • A.5 Derivative of the interpolating free entropy: Proof of Proposition 3: Gaussian integration by parts with respect to the measurement matrix and auxiliary Gaussian variables evaluates the principal derivative terms.The calculation applies successively to Φ, V, and W∗.
  • A.5 Derivative of the interpolating free entropy: Proof of Proposition 3: The Nishimori identity removes the term T2 from the derivative decomposition.This identity is invoked directly to show that T2=0.

A.5.2 Proof that An,ϵ vanishes as n →∞

This section proves that the remainder A_n,ϵ vanishes uniformly along the interpolation path. Concentration, conditional independence, boundedness, and Cauchy–Schwarz control its constituent terms.

  • A.5.2 Proof that An,ϵ vanishes as n →∞: The proof reduces uniform vanishing of A_n,ϵ to concentration of the normalized log-partition function around the interpolating free entropy.The required concentration holds uniformly in t.
  • A.5.2 Proof that An,ϵ vanishes as n →∞: Conditional expectation identities and the tower property simplify the expectations appearing in A_n,ϵ.These steps exploit the conditional structure of the interpolating variables.
  • A.5.2 Proof that An,ϵ vanishes as n →∞: Cauchy–Schwarz bounds the remaining terms after the relevant conditional identities are applied.The proof combines successive estimates to control the residual expression.
  • A.5.2 Proof that An,ϵ vanishes as n →∞: Boundedness assumptions on the output function and its derivative provide finite constants controlling the residual moments.The argument uses bounds involving the noisy observations and the measurement ratio m/n.
  • A.5.2 Proof that An,ϵ vanishes as n →∞: The overlap fluctuation is bounded uniformly in t under hypothesis (H2), completing the control needed for A_n,ϵ.The final bound depends on the output function and α.

A.7 Proof of Proposition 6

The proof establishes monotonicity properties of the MMSE by analyzing how the two auxiliary Gaussian channels depend on R1 and R2, then connects scalar-channel free entropy to convexity and regularity.

  • Bounds: E⟨Q⟩n,t,ϵ lies in [0, ρ].This follows because the relevant quantity is bounded by the signal second moment ρ.
  • Monotonicity of the MMSE: MMSE(X∗|Yt, Y′t, V, Φ) is non-increasing in R1 because R1 controls an additional Gaussian observation of X∗.The auxiliary channel is Y′t = √R1 X∗ + Z′, with Z′ standard Gaussian.
  • Monotonicity of the MMSE: MMSE(X∗|Yt, Y′t, V, Φ) is also non-increasing in R2, which enters the observation channel Yt.The proof compares two values of R2 using an independent Gaussian vector V′.
  • Monotonicity of the MMSE: MMSE(X∗|Yt, Y′t, V, Φ) is a non-increasing function of R2.This monotonicity is stated as the resulting property after the comparison argument.
  • Scalar-channel properties: The scalar-channel free entropy is convex, differentiable, non-decreasing, and 1/2 E[X0^2]-Lipschitz on R+.It is strictly convex when the prior P0 is not a point mass.

B.2 The non-linear scalar channel

This section analyzes the nonlinear scalar output channel through mutual information and free entropy, proving continuity, convexity, monotonicity, and differentiability properties under progressively broader hypotheses.

  • Channel representation: For the scalar channel, IPout(q) = I(W∗; Y(q)|V) = ΨPout(ρ) − ΨPout(q).Thus properties of the free entropy ΨPout translate directly into properties of the conditional mutual information.
  • Regularity of ΨPout: For additive-noise channels with bounded C2 ϕ, ΨPout is C2 on [0, ρ].The result relies on boundedness of ϕ and its first two derivatives.
  • Regularity of ΨPout: Under the stated channel hypotheses, ΨPout is continuous, convex, and non-decreasing on [0, ρ].The bounded C2 case provides the same conclusion directly, while the general case is obtained through approximation arguments.
  • Regularity of IPout: IPout is continuous, concave, and non-increasing on [0, ρ].The proof uses uniform approximation by continuous, concave, non-increasing functions and a separate limiting argument for discrete outputs.
  • Differentiability: ΨPout is differentiable on [0, ρ), with its derivative obtained by differentiating under the expectation and using the scalar posterior.The derivative extends continuously to q = 0.
  • Strict monotonicity: If Pout is informative, ΨPout is strictly increasing on [0, ρ].Otherwise the posterior mean would vanish almost surely, forcing Pout(y|·) to be almost everywhere constant and contradicting informativeness.

C.2 Relaxing the hypotheses on ϕ

The proof extends the main free-entropy theorem from smooth bounded output functions to broader hypotheses by approximation, uniform mutual-information control, and a zero-noise limiting argument.

  • Relaxing ϕ: Theorem 1 is first extended to output channels satisfying (h1)-(h2)-(h3)-(h4) and (h5.a).This is the stated conclusion of Proposition 25 after relaxing the smoothness assumptions.
  • Approximation: A measurable output function ϕ is approximated by a C∞ function bϕ with compact support.The approximation is constructed in L2 under the Gaussian-prior measure.
  • Approximation error: |IPout(q) − I bPout(q)| ≤ C′√ϵ uniformly for q ∈ [0, ρ].This uniform control transfers the theorem from the approximating channel to the original channel.
  • Discrete outputs: The proof then handles discrete outputs by letting ∆ → 0 while controlling the approximation uniformly in n.The n → ∞ and ∆ → 0 limits can therefore be interchanged.
  • Variational formulas: Convex-analytic lemmas justify the sup-inf representations by restricting one optimization variable to [0, ρ].The argument uses conjugate functions, monotonicity, and convexity to show the restricted and unrestricted extrema coincide.

E.1.4 Proof of Theorem 6

Theorem 6 is proved by establishing concentration of the free entropy and then controlling overlap fluctuations through posterior and quenched-disorder concentration, convexity, and interpolation regularity.

  • Free-entropy concentration: Var(ln Ẑt,ϵ/n) ≤ C(ϕ, S, α)/n.This variance bound yields the free-entropy concentration theorem.
  • Overlap concentration: The overlap L concentrates around its posterior expectation ⟨L⟩ under regular interpolation functions.This is Proposition 29, derived using derivative formulas for the interpolated free entropy.
  • Overlap concentration: The posterior average ⟨L⟩ concentrates around its expectation E⟨L⟩ through thermal-fluctuation bounds and free-entropy concentration.The two-stage decomposition separates posterior fluctuations from quenched-disorder fluctuations.
  • Interpolation regularity: The interpolation map Rt is a regular diffeomorphism with Jacobian at least 1, enabling integration over the perturbation region.Its image remains inside a bounded rectangle determined by sn, rmax, and ρ.
  • Convexity argument: Convexity of the free entropy controls differences of derivatives with respect to R1.The argument uses finite-difference bounds and chooses δ = sn n^-1/4.

F.1 General purpose algorithms

The paper compares general-purpose optimization and neural-network methods with optimal errors across regression and classification problems, while numerically evaluating replica predictions through state evolution. The experiments also show that symmetry can prevent unmodified GAMP from moving away from an uninformative fixed point, motivating a slight solver-side perturbation.

  • General-purpose algorithms: General-purpose experiments use scikit-learn, Keras with TensorFlow, CVXPY, and PhaseMax across classification, regression, and phase-retrieval tasks.The reported implementations include logistic regression, neural networks, LASSO, sparse ReLU recovery, and phase-retrieval experiments.
  • General-purpose algorithms: The neural-network setup uses a 2500-dimensional input, two hidden layers with ReLU and sigmoid activations, dropout, and a softmax output.The first layer has dimension 2500×64, the second 64×64, and dropout fraction is 0.2.
  • General-purpose algorithms: Dropout substantially improves generalization error, while increasing training epochs helps the network escape an initially near-random prediction regime.The authors report that fit quality improves drastically as the number of epochs increases.
  • Numerical evaluation: Replica-formula evaluation proceeds by iterating state evolution from two initial conditions, computing the resulting free entropies, and selecting between fixed points.The two initializations are q^t=0=0 and q^t=0=ρ.
  • Breaking the symmetry in GAMP: For symmetric channels and zero-mean priors, GAMP can remain at the q=0 fixed point, so the experiments slightly break solver symmetry while keeping the data-generating model symmetric.The perturbation is described as making GAMP only slightly and unnoticeably suboptimal.
Loading 1708.03395v3…