PaperlayerView exact revision on arXiv

Source-linked AI summary

Phase Transitions in Learning Driven by Extremal Data

Ethan Levien, Trevor GrandPre

arXiv:2610.29531v1cs.LGcond-mat.stat-mechphysics.data-an

TL;DR

The paper asks when gradient descent can recover a target in extremal multiple-instance learning, where max pooling creates a fitting obstruction. It derives a low-dimensional gradient-flow description for a minimal model and finds freezing and retrieval transitions, with numerical results supporting the predicted phase diagram and asymptotic gradient field.

  • Problem

    The max is the central obstruction to fitting the regression vector by gradient descent, motivating the question of when jointly learning the direction and softmax temperature can recover the target.

    Source: pp. 1–2

  • Method

    The paper derives limiting low-dimensional dynamics for temperature and regression coefficients using random-energy-model and Hopfield-network results.

    Source: pp. 2, 4

  • Results

    The flow has freezing and retrieval transitions; numerically, its phase diagram predicts finite-size trajectory attributes and the training gradient converges to the asymptotic gradient-flow field.

    Source: p. 1

  • Takeaways & Limitations

    The analysis suggests learning speed can change abruptly with initial misalignment, motivating exploration of alternatives such as coupling gradient descent with EM-based approaches during early learning.

    Source: p. 5

    The analysis is restricted to the identifiable regime α < ρ_true²/2, and its almost-sure-limit approximation breaks down at both phase transitions.

    Source: pp. 2–3

Abstract

from arXiv · show

We study an extremal regression problem, an example of multiple instance learning (MIL), where the predictors are given as multisets, called bags. The bag elements (called instances) possess hidden labels which are pooled to produce an observed bag-level label. Max pooling is common in MIL applications, but gives rise to vanishing gradients. To handle this, modern MIL pipelines approximate the max with a softmax, treating the sharpness as a learnable parameter, denoted $\lambda$. When the max pooling model is the true data generating process, learning will be successful when $\lambda$ is increased during gradient descent, thereby driving the dynamics into regions of parameter space with vanishing gradients. To understand the conditions under which gradient descent breaks down, we study a minimal model and derive a low dimensional projection of the gradient flow in the joint limit of large bags $n$ and high dimension $d$ with $\alpha=\ln n/d$ fixed. The flow has two distinct phase transitions: an intrinsic freezing transition related to the random energy model of disordered systems, and a retrieval transition occurring in modern Hopfield networks. Numerical simulation confirms both the phase diagram and the convergence of the finite-size training gradient to its predicted asymptotic form.

S1. BACKGROUND: REM AND EVT

The background connects extremal statistics and the random energy model (REM) to the learning setup. It describes how maxima and partition-function behavior change with the number of instances and dimension.

A. Extreme value statistics

  • For n iid Normal(0,s²) variables, (Mn−bn)/an converges to a Gumbel random variable; when n=e^(αd) and s²=d, Mn≈d√(2α), with order-one Gumbel fluctuations.Source: A. Extreme value statistics · p. 7

B. The random energy model

  • The REM partition function has a freezing transition: the high-temperature sum is dominated by exponentially many configurations, while the low-temperature sum is dominated by the single lowest-energy configuration.The transition occurs at β_c = √(2 ln 2).Source: B. The random energy model · p. 8
  • The REM replica overlap is the probability that two independent draws from the Gibbs weights select the same configuration.The derivative of the log partition function with respect to inverse temperature is related to this overlap.Source: B. The random energy model · p. 8

C. Weak self-averaging transition

  • Power-law sums can have two transitions: one where the central limit theorem fails while the law of large numbers holds, and another where the law of large numbers fails, corresponding to REM freezing.The second transition is derived by comparing the growth of the second moment with the maximum.Source: C. Weak self-averaging transition · pp. 8–9

A. Setup and normalization

  • The setup samples iid standard-normal bag entries and replaces one row with β_true with probability q to form a positive bag.The learned direction is parameterized relative to the target direction and an orthogonal component.Source: A. Setup and normalization · p. 9

1. True output second moment

The section evaluates the true max-pooled output on positive and negative bags. In the identifiable regime, the planted instance realizes the positive-bag maximum with probability tending to one.

1. True output second moment

  • With probability tending to one, the planted instance is the maximum in positive bags, giving w_k/d ∼ ρ_true²; on negative bags, w_k/d ∼ m_n.The passage identifies E± as expectations over positive and negative bags, respectively.Source: §1 · p. 9

2. Model output

The limiting model output is governed by competition between the off-target partition function and the planted instance’s softmax weight. The resulting output has retrieval and non-retrieval regimes, alongside a separate REM freezing transition.

2. Model output

  • The off-target partition function is mapped to the REM partition function by matching the number of terms and the exponents’ distributions.Table S1 presents this correspondence; the sign of the exponents is immaterial because their distribution is symmetric.Source: Table S1 · p. 10, §2 · p. 10
  • For λ > λ⋆, the off-target partition function is dominated by a few instances near the maximum, whereas for λ < λ⋆ its softmax average is spread over exponentially many instances.The output fluctuations remain exponentially small for λ < λ⋆ on both sides of the transition at λ⋆/2, which changes fluctuations of the partition function but not of the output.Source: §2 · p. 10
  • In the retrieval phase, the planted-instance softmax weight approaches one; in the non-retrieval phase, that weight is exponentially small.The retrieval boundary compares the planted instance’s exponent with the growth rate of the off-target partition function.Source: §2 · p. 10

3. Cross term

  • On negative bags, the covariance between m_n and the normalized softmax output is O(1/d²).Source: §3 · p. 11

4. Phase table

The phase table combines the high/low-temperature and retrieval/non-retrieval criteria into four regimes. In each regime, the conditional loss is a squared residual based on the corresponding output limit.

4. Phase table

  • The total loss is the positive-bag conditional loss weighted by q plus the negative-bag conditional loss weighted by 1 − q.Source: §4 · p. 11
  • The conditional losses for positive and negative bags converge to squared residuals formed from their respective limiting outputs.Source: §4 · p. 11
  • The four phases combine the H/L criterion λ ≶ λ⋆ with the R/N retrieval criterion.Source: §4 · p. 11
  • In retrieval, the positive-bag output is ρρ_trueu; in non-retrieval it equals the negative-bag output, which is λρ in H and 2αρ in L.Source: §4 · p. 11

B. Gradient flow

The limiting gradient flow evolves λ, ρ, and the overlap u according to phase-specific pooled scores and residuals. Across the four temperature/retrieval regimes, some coordinates freeze while others continue to evolve.

B. Gradient flow

  • The flow is projected onto λ, ρ, and u, with u evolving through the tangent-projected gradient of the loss.The residuals for each phase are taken from its corresponding row of Table I.Source: B. Gradient flow · p. 11
  • In HR, the planted instance dominates positive bags, making their pooled score independent of λ; the negative-bag mismatch drives λ.The positive-bag softmax weight is already concentrated on the planted instance.Source: B. Gradient flow · p. 11
  • In HN, both bag scores equal λρ, so u is frozen and λ² − ρ² is conserved as (λ, ρ) moves toward a zero-residual point.The overlap is frozen because neither bag type selects a single instance.Source: B. Gradient flow · p. 12
  • In LR, λ and u are frozen, while ρ evolves to match the predicted extremal scale 2αρ to the true extremal statistics.This is the low-temperature, retrieval regime.Source: B. Gradient flow · p. 12

S3. ROBUSTNESS TO NOISE IN LABELING AND SELECTION

The noise analysis distinguishes changes to pooled predictions from changes to targets: noise can leave phase boundaries and outputs intact while changing residuals or the loss. The paper also connects MIL pooling to Hopfield retrieval through their shared softmax competition.

S3. ROBUSTNESS TO NOISE IN LABELING AND SELECTION

  • Noise leaves the retrieval and temperature boundaries and pooled outputs unchanged; it can change target residuals instead.The analysis reduces the noisy case to determining the noisy limits of the pooled outputs.Source: S3. ROBUSTNESS TO NOISE IN LABELING… · p. 12
  • Independent mean-zero post-max noise adds a constant to population loss and leaves the gradient flow unchanged.Its cross-term vanishes because the noise is independent of the label and prediction.Source: S3. ROBUSTNESS TO NOISE IN LABELING… · pp. 12–13
  • With noisy targets, the phase boundaries and freezing properties remain unchanged because the pooled prediction’s dependence on λ, u, and ρ is unaffected.The stated frozen coordinates are u in HN/LN and λ in LR/LN.Source: S3. ROBUSTNESS TO NOISE IN LABELING… · p. 13

S4. CONNECTION TO PATTERN RETRIEVAL IN ASSOCIATIVE MEMORY

  • MIL pooling is a projection of the Hopfield attention readout onto the query, with planted-instance weight competing against the REM partition function.The connection is the softmax competition between one distinguished pattern and exponentially many background patterns.Source: S4. CONNECTION TO PATTERN RETRIEVAL IN… · p. 13

S5. EXTENSION TO A CLASSIFICATION LOSS

The asymptotic pooled-score forms do not depend on the loss, so losses built from the same normalized pooled score inherit the same phase structure. The loss changes the residuals driving the flow and can therefore change its fixed points.

S5. EXTENSION TO A CLASSIFICATION LOSS

  • The chain rule separates loss-dependent residuals from the architecture-determined derivatives of the pooled scores.The derivatives of the pooled scores are read from Table I.Source: S5. EXTENSION TO A CLASSIFICATION LOSS · p. 13
  • Any loss built from the normalized pooled score inherits the same four phases, with u frozen in HN/LN and λ frozen in LR/LN.The phase boundaries and parameter dependence follow from the same three asymptotic pooled-score forms.Source: S5. EXTENSION TO A CLASSIFICATION LOSS · p. 13
  • The choice of loss affects the residuals and thus the fixed points within each phase, even though the phase structure is inherited.The pooled-score limits, rather than the loss function, determine the phase boundaries.Source: S5. EXTENSION TO A CLASSIFICATION LOSS · p. 13

A. The logistic (cross-entropy) case

Under cross-entropy, the four phases and their freezing properties persist, but the regression flow’s tuning of λ is lost. In particular, λ decreases in HR, closing the regression route through retrieval to λ⋆.

A. The logistic (cross-entropy) case

  • The classification objective uses a logistic prediction from the normalized pooled score minus threshold τ, with cross-entropy residuals replacing the regression residuals.The resulting residuals are R+ = 1 − p̄+ and R− = −p̄−.Source: A. The logistic (cross-entropy) case · p. 14
  • In HN, the fixed point satisfies λρ = τ + ln(q/(1−q)); in LN, ρ⋆ = (τ + ln(q/(1−q)))/√(2α), provided τ + ln(q/(1−q)) > 0.Otherwise, the flow runs to the λρ = 0 boundary; the HN conserved hyperbola is unchanged.Source: A. The logistic (cross-entropy) case · p. 14
  • In LR, u increases throughout the phase and runs to the boundary u = 1 rather than an interior overlap.The stationarity condition for ρ is transcendental because the residuals are sigmoidal in the score.Source: A. The logistic (cross-entropy) case · p. 14
  • In HR, λ decreases, and the trajectory cannot remain in retrieval as λ approaches zero because ϕα(λ) diverges while retrieval requires ρtrueu > ϕα(λ).The trajectory consequently crosses the retrieval boundary.Source: A. The logistic (cross-entropy) case · p. 14
  • Under cross-entropy, the four phases and freezing of u outside retrieval and λ in low-temperature phases remain, but tuning λ to λ⋆ is lost.The binary label lacks the extremal scale in the regression target that drives λ upward through HR.Source: A. The logistic (cross-entropy) case · p. 14

S6. NUMERICAL TESTS OF THE GRADIENT-FLOW LIMIT

The numerical tests compare finite-size empirical gradients with the asymptotic field at selected parameter settings. Figure S1 reports retrieval thresholds across its sweeps, while the gradient comparison is pointwise and does not capture accumulated parameter bias.

  • The empirical-gradient comparison evaluates a point in (λ, u, ρ), so it excludes accumulated learned-parameter bias that could yield higher-dimensional limiting dynamics.The figures compare finite-size gradients against the asymptotic field of Eq. (S29).Source: S6. NUMERICAL TESTS OF THE… · p. 14
  • 0.854, 0.292, and 0.264 are the retrieval thresholds reported for Figure S1’s three initial-temperature settings.The figure also compares empirical gradients with asymptotic predictions across overlap values.Source: S6. NUMERICAL TESTS OF THE… · p. 14
  • The λ0 sweep plots asymptotic ˙λ for fixed overlaps u = 0.7 and u = 0.1; across λ0 ∈ [0.1, 0.4], R persists only for u > 0.458, N only for u < 0.264.Source: S6. NUMERICAL TESTS OF THE… · p. 14

S7. LLM DISCLOSURE

The disclosure describes Claude-model assistance with coding, mathematical derivations, and writing, with substantial text edits and large code sections tracked through reviewed GitHub pull requests. The accompanying supplementary figures specify gradient and error comparisons across selected parameter sweeps.

  • Claude models assisted with coding, mathematical derivations, and writing; substantial text edits and large code sections were managed through reviewed GitHub pull requests.The authors say this workflow let them track and review substantial LLM-generated material.Source: S7. LLM DISCLOSURE · p. 14
  • Figure S1 compares empirical and asymptotic (˙λ, ˙u, ˙ρ) against overlap, varying α or initial temperature across its panels.Its caption specifies ρ0 = 1.7, ρtrue = 1.2, q = 0.2, ℓ = 100, and n = 1808.Source: Figure S1 · p. 15
  • Figure S2 compares ˙λ against λ0 at fixed overlaps u = 0.1 and 0.7, in N and R throughout, respectively.It shows increasing d with n = e^αd and marks λ⋆ = 0.316.Source: Figure S2 · p. 15
  • Figure S3 plots initial ˙λ error against ln d/d for u = 0.1 and 0.7, with individual datasets and means with standard errors.It uses eight datasets per d through d = 225 and four above.Source: Figure S3 · p. 16
Loading 2610.29531v1…