📊 statistics

From Sublinear to Linear: Local Convergence in Finite-Width Networks via Locally Polyak-Lojasiewicz Regions

This paper establishes that gradient descent on finite-width feedforward networks achieves local linear convergence under squared loss by proving that a positive, Lipschitz-stable Neural Tangent Kernel induces a local Polyak-Łojasiewicz inequality, a mechanism empirically validated through spectral analysis and step-size sensitivity on MNIST and CIFAR-10 datasets.

Original authors: Agnideep Aich, Ashit Baran Aich, Bruce Wade

Published 2026-05-29

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Agnideep Aich, Ashit Baran Aich, Bruce Wade

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Why Do Neural Networks Learn So Fast?

Imagine you are trying to find the lowest point in a massive, foggy mountain range (this is the "loss landscape" of a neural network). You are blindfolded and can only feel the slope under your feet (this is "Gradient Descent").

Classical math tells us that in a foggy, non-convex mountain range, you might get stuck in a small dip or wander around very slowly. It predicts a sublinear rate of progress—meaning you get faster and faster as you go, but the rate of improvement slows down over time.

However, in real life, when we train AI, it often zooms straight to the bottom incredibly fast. This paper asks: Why? Specifically, it looks at "finite-width" networks (standard AI models, not infinitely huge ones) and tries to explain the speed without assuming the network is infinitely wide.

The Core Idea: Finding a "Safe Zone"

The authors propose a new way to look at this speed. They break the problem into two parts:

The Map (The LQCR): First, they use a previous theory (from Aich et al., 2025) that says: "If you start at a specific spot and take small enough steps, you are guaranteed to stay inside a specific, safe neighborhood called a Locally Quasi-Convex Region (LQCR)." Think of this as a fenced-in valley. As long as you stay inside the fence, the terrain is predictable.
- Old finding: Staying in this valley guarantees you will eventually reach the bottom, but it doesn't explain why you get there fast.
- New finding: The authors ask, "What if there is a special property inside this valley that makes you run downhill like a sled?"
The Engine (The PL Inequality): They found that if a specific condition is met inside that valley, the math changes. The condition involves something called the Neural Tangent Kernel (NTK).
- The Analogy: Imagine the NTK is like the "stiffness" of the ground. If the ground is stiff and stable (mathematically, "positive" and "smooth"), then the steeper the slope, the faster you fall.
- The Discovery: The authors proved that if the NTK starts out "stiff" (positive) and doesn't change too wildly as you move (Lipschitz stability), then the loss function satisfies a Polyak-Łojasiewicz (PL) inequality.
- What this means: In plain English, this inequality guarantees that as long as you are in this safe valley, your progress will be linear. You won't just inch forward; you will shrink the error by a fixed percentage every single step. This is the "near-exponential" speed we see in practice.

The Catch: You Must Stay in the Valley

The paper is very careful about what it claims. It says:

If the network starts with a "good" NTK (positive stiffness),
And the NTK stays stable as you move,
And You stay inside the safe valley (the LQCR),
Then you will converge linearly (very fast).

Crucially: The paper does not say this mechanism is the only reason AI learns fast. It just says, "Here is a specific set of conditions where we can mathematically prove it happens." It is a "sufficient condition," not a "necessary" one.

The Experiments: Testing the Theory

The authors didn't just do math; they ran experiments to see if these invisible "latent variables" actually behave as predicted. They treated the training process like a science experiment where they measured the specific ingredients of their theory.

1. The Binary MNIST Test (The Controlled Lab):
They trained a simple network on handwritten digits (3s vs. 8s).

What they measured: They tracked the "stiffness" of the NTK, how far the network wandered from its starting point (drift), and the speed of the loss drop.
The Result: As long as the network stayed close to the start (small drift), the NTK remained stable, and the loss dropped in a perfect straight line on a log scale. The theory held up.

2. The Width Ablation (Pushing the Limits):
They tested what happens if they make the network wider (more neurons) but keep the step size (learning rate) the same.

The Failure: At a width of 1024 with a standard step size, the network wandered too far out of the "safe valley." The NTK lost its stability, and the fast, linear speed broke down. The theory predicted this would happen, and it did.
The Fix: They reduced the step size. Suddenly, the network stayed in the valley again. The NTK stabilized, and the fast linear speed returned.
The Lesson: This proved that the "safe zone" isn't just about how wide the network is; it's about the relationship between width and step size. If you take steps that are too big, you fall out of the zone where the math works.

3. The CNN Robustness Check (The Real World):
They tried this on a more complex Convolutional Neural Network (CNN) used for image recognition, using standard training tricks like mini-batches and changing learning rates.

The Result: Even though they couldn't measure the NTK directly (it was too big), the other signs were there: the error dropped linearly, and the network didn't wander off into chaos. This suggests the "safe zone" idea might apply to more complex, real-world AI models, even if the math is harder to prove there.

Summary of the Takeaway

The Problem: We know AI learns fast, but standard math says it should be slow.
The Solution: The authors found a specific "local neighborhood" around the starting point where, if the network's internal geometry (NTK) is stable, the learning speed becomes linear (very fast).
The Condition: You must stay inside this neighborhood. If your learning rate is too high or the network is too wide for that step size, you leave the neighborhood, and the fast speed guarantee disappears.
The Proof: They didn't just guess; they measured the specific "ingredients" (NTK stability, parameter drift) during training and showed that when the ingredients are right, the fast speed happens. When they broke the ingredients, the speed broke.

In short: The paper identifies a "sweet spot" in the training process where the math guarantees a fast, straight-line descent to the solution, provided you don't take steps that are too big and wander out of that spot.

Technical Summary: From Sublinear to Linear: Local Convergence in Finite-Width Networks via Locally Polyak-Łojasiewicz Regions

1. Problem Statement

Gradient descent (GD) on deep neural network loss landscapes is non-convex, yet it often converges significantly faster in practice than classical worst-case sublinear guarantees suggest. Prior theoretical work, specifically the Locally Quasi-Convex Region (LQCR) framework (Aich et al., 2025), established that for finite-width feedforward networks, GD remains confined to a local region around initialization and converges to a stationary point at a sublinear rate. However, this framework does not explain the near-exponential (linear) decay observed empirically.

The central question addressed by this paper is: Is there a natural additional local condition under which the convergence rate within the same LQCR improves from sublinear to linear? The authors seek a condition that applies explicitly to the local region characterized by the LQCR, rather than assuming global properties or requiring extreme overparameterization.

2. Methodology and Theoretical Framework

The paper proposes a decomposition of the convergence mechanism into two distinct components: localization and error bounding.

Localization (The LQCR): The authors utilize the LQCR framework (Aich et al., 2025) to define a geometrically characterized region $R$ around the initialization $\theta_0$ with an explicit radius $r(R)$ . In the original LQCR work, this region guarantees that iterates remain confined under a specific decaying step-size schedule. In this paper, the LQCR serves strictly as a containment and localization device.
The Local Polyak-Łojasiewicz (LPL) Condition: The authors derive a local Polyak-Łojasiewicz (PL) inequality specifically for the squared empirical loss within this region.
- Mechanism: The derivation relies on a one-line identity for squared loss: $\|\nabla L(\theta)\|^2 = \frac{1}{n}(f_\theta - y)^\top \Theta_\theta (f_\theta - y)$ , where $\Theta_\theta$ is the empirical Neural Tangent Kernel (NTK).
- Assumptions: The authors assume:
  1. Pointwise Positivity: The empirical NTK is positive definite at initialization ( $\lambda_{\min}(\Theta_{\theta_0}) \ge \lambda_0 > 0$ ).
  2. Lipschitz Stability: The NTK is Lipschitz continuous on the region $R$ with constant $L_\Theta$ .
  3. Compatibility: The region radius and Lipschitz constant satisfy $L_\Theta r(R) < \lambda_0$ .
- Derivation: Using Weyl's inequality, they propagate the initial spectral gap across the region. This yields a uniform lower bound on the NTK eigenvalues: $\lambda_{\min}(\Theta_\theta) \ge \lambda_0 - L_\Theta r(R) = \lambda_R > 0$ .
- Resulting PL Constant: This spectral lower bound translates directly into a PL constant $\mu = \lambda_R$ . Consequently, the squared loss satisfies the local PL inequality: $\frac{1}{2}\|\nabla L(\theta)\|^2 \ge \mu (L(\theta) - L^*_R)$ for all $\theta \in R$ .
Linear Convergence Theorem: By combining the derived PL inequality with the hypothesis that GD iterates remain within $R$ (imposed as a condition for the fixed-step theorem), the authors prove that GD converges linearly to the local minimum $L^*_R$ with a rate determined by $\mu$ and the step size $\eta \le 1/L$ .

3. Key Contributions

The paper makes five specific contributions:

Local PL Inequality from NTK Conditioning: They prove that pointwise positivity of the empirical NTK at initialization, combined with Lipschitz continuity, yields a PL inequality on the LQCR with an explicit constant $\mu = \lambda_0 - L_\Theta r(R)$ .
Explicit Decomposition of Roles: The authors clarify that the LQCR provides the region and containment, while the NTK conditioning provides the PL inequality. They explicitly avoid claiming that local quasi-convexity alone generates fast rates.
Sufficient, Not Necessary: The result is framed as a sufficient local condition for linear convergence on the squared loss. The authors do not claim this mechanism is necessary or the unique explanation for fast convergence in deep networks.
Latent Variable Empirical Methodology: Instead of merely fitting log-log slopes to loss curves, the authors propose an empirical strategy that directly tracks the "latent variables" of the theory: the NTK spectral gap, parameter drift, the empirical PL ratio, and suboptimality decay.
Boundary and Recovery Demonstration: Through width ablation, the paper demonstrates a specific failure mode where the local regime breaks (due to excessive parameter drift eroding the NTK gap) and shows that reducing the step size restores the local regime and the theoretical diagnostics.

4. Experimental Results

The authors validate their theory using three experimental setups:

Controlled Binary MNIST (MLP):
- On a fully connected network with width 512, the subset empirical NTK eigenvalue remains positive and stabilizes after an initial drift.
- Parameter drift remains small ( $\approx 0.17$ ), consistent with the lazy regime.
- The empirical PL ratio exhibits a positive lower envelope ( $\approx 6.87$ ) on the stable middle regime.
- Suboptimality decay follows a geometric pattern on a semi-log scale, consistent with linear convergence.
Width Ablation (Boundary Analysis):
- At widths $m \in \{128, 256, 512\}$ , the system behaves as predicted: NTK drift is small, and the PL ratio is positive.
- At width $m=1024$ with step size $\eta=10^{-3}$ , the system breaks the local regime: parameter drift jumps to $1.87$, the NTK eigenvalue drops by 83%, and the PL ratio degrades.
- Recovery: Reducing the step size to $\eta=5 \times 10^{-4}$ for the $m=1024$ case restores the lazy regime (drift drops to $0.158$), recovers the NTK conditioning, and yields the highest empirical PL ratio ($14.39$) observed in the study. This confirms the step-size sensitivity of the containment hypothesis.
CNN Robustness Check (CIFAR-10):
- Using a ResNet-style CNN trained with mini-batch SGD and cosine annealing (settings outside the strict fixed-step, full-batch theoretical scope), the authors observed that the signatures of the LPLR mechanism persist: a positive lower envelope on the PL ratio, bounded parameter drift, and linear-rate suboptimality decay across three seeds.
- The authors note this is a robustness check; NTK conditioning was not directly verified at this scale, and the theoretical assumptions (fixed step size, smooth activations) were relaxed.

5. Significance and Claims

The paper positions its contribution as a local, finite-width sufficient condition for linear convergence, distinct from global overparameterization results.

What it claims: The authors demonstrate that if a finite-width network stays within an LQCR and the empirical NTK satisfies specific spectral and stability conditions, the squared loss satisfies a local PL inequality, guaranteeing linear convergence. They provide empirical evidence that these conditions hold in specific regimes and that violating the containment condition (via step size or width) breaks the linear rate.
What it does not claim:
- It does not claim the LPLR mechanism is necessary for fast convergence.
- It does not claim this is the only route to linear rates (e.g., feature learning or mean-field dynamics may apply elsewhere).
- It does not claim the mechanism applies universally to all loss functions (the proof is specific to squared loss) or all architectures (current proofs assume smooth fully-connected networks).
- It does not claim to explain fast convergence in all practical deep learning scenarios, but rather identifies a specific local regime where it provably suffices.

The authors emphasize that their empirical methodology—probing latent variables rather than just loss curves—allows for a more rigorous validation of the theoretical assumptions, capable of disconfirming the framework if the latent variables behave contrary to predictions.