Escape dynamics and implicit bias of one-pass SGD in overparameterized quadratic networks

This paper analyzes one-pass SGD dynamics in overparameterized quadratic networks, revealing that while overparameterization only modestly accelerates escape from poor generalization plateaus, the algorithm's implicit bias—driven by unconstrained weight norms and conserved quantities—selects the zero-loss solution closest to the random initialization within a continuous manifold of solutions.

The Gist

The Big Picture: A Game of "Copycat"

Imagine you are trying to teach a robot (the Student) to mimic a master chef (the Teacher). The master chef has a secret recipe (the Teacher's weights) that turns ingredients (input data) into a perfect dish (the output). Your robot has its own set of knobs and dials (the Student's weights) that it can turn to try and recreate that dish.

The goal is simple: Turn the robot's knobs until the dish it makes tastes exactly like the master chef's.

This paper studies what happens when:

1. The robot is overparameterized: It has more knobs than the master chef does.
2. The robot learns one-pass: It gets to taste the ingredients and adjust its knobs only once per sample, never seeing the same ingredient twice.
3. The "flavor" math is quadratic: The taste depends on the square of the knob settings, which creates a very specific, bumpy landscape of possibilities.

---

1. The "Flat Plateau" Problem

When the robot starts learning, it usually begins with its knobs set to zero or random values. In this specific type of math (quadratic), the robot hits a Plateau.

• The Analogy: Imagine the robot is standing on a giant, perfectly flat, foggy meadow. No matter which way it takes a step, the ground feels exactly the same. There is no "downhill" slope to guide it toward the solution.
• The Result: The robot wanders around aimlessly for a long time, unable to figure out how to get better. This is called the "uninformative plateau."

Does having more knobs help?
You might think, "If the robot has more knobs (overparameterization), it should find the way out faster."

• The Finding: Surprisingly, no. Having more knobs doesn't change the shape of the foggy meadow. It just means there are more legs trying to walk at the same time. The robot still gets stuck for roughly the same amount of time. The only difference is that having more knobs makes the robot slightly louder in its attempts to escape, but the time it takes to finally break free is determined by how complex the Master Chef's recipe is, not how many knobs the robot has.

2. The "Lake of Solutions"

Once the robot finally escapes the foggy plateau, it reaches the "Zero Error" zone. This is where the robot finally makes the perfect dish.

• The Analogy: In simple problems, there is usually just one perfect spot on the map where the robot can stand to make the dish. But in this complex, overparameterized world, the "perfect spot" isn't a single dot. It's a giant, continuous lake.
• Why? Because the robot has extra knobs. You can rotate the knobs in many different ways, and as long as the overall shape of the settings remains the same, the dish tastes perfect. It's like having a team of 10 people carrying a table; you can swap who stands where, and the table stays level. There are infinite ways to arrange the team to get the same result.

3. The "Lazy Traveler" (Implicit Bias)

Here is the most fascinating part. Since there is a whole "lake" of perfect solutions, which one does the robot pick? Does it pick the one closest to the center? The one with the most symmetrical knobs?

• The Finding: The robot is incredibly lazy. It picks the solution that is closest to where it started.
• The Analogy: Imagine you are dropped in the middle of a giant, flat lake of perfect solutions. You have a compass that points to "Home" (your starting random position). You don't swim to the far side of the lake just because it looks nicer. You simply walk the shortest distance to the nearest point on the shore that satisfies the "perfect dish" rule.
• The Science: The paper proves that the learning process (SGD) has a "conserved quantity." It's like a physical law that says, "You cannot change your distance from your starting point in a specific way." The robot is mathematically forced to stop at the solution closest to its random initialization.

4. The "Hill and Valley" Map

The researchers also looked at the "terrain" of the problem using a tool called the Hessian (which measures the steepness and curvature of the ground).

• The Plateau: They found that the "foggy meadow" the robot gets stuck in isn't just flat; it's a saddle. It's flat in some directions (where the robot wanders) but has a hidden "downhill" slope in other directions that eventually lets the robot escape.
• The Lake: The "lake" of perfect solutions isn't a deep pit. It's a marginal minimum. It's flat along the surface of the lake (because you can rotate the knobs without changing the taste), but if you try to step off the lake, you immediately go uphill.

Summary of Key Takeaways

1. More isn't always faster: Giving the student network more capacity (more neurons) doesn't magically solve the "stuck in the fog" problem. It only helps a tiny bit by changing the speed of the escape, not the time it takes.
2. Infinite Solutions: When the student is bigger than the teacher, there isn't just one right answer. There is a whole continuous family of perfect answers (a manifold).
3. Initialization is Destiny: The specific random way the robot starts determines exactly which perfect solution it will find. The learning algorithm acts like a magnet, pulling the robot to the closest possible solution to its starting point.
4. Symmetry Rules: The reason there are so many solutions is due to a hidden symmetry (rotational invariance). The math allows the robot to spin its internal gears in different ways without changing the final output.

In a nutshell: This paper explains that in complex learning scenarios, the path you take is less about the destination and more about where you started. The learning algorithm doesn't search for the "best" solution in a global sense; it simply finds the "closest" solution to your starting point, and it gets stuck in a flat fog for a while before it finally finds the exit.

Technical Summary

1. Problem Statement

The paper investigates the learning dynamics of a two-layer neural network with quadratic activation functions trained via one-pass Stochastic Gradient Descent (SGD) (online learning). The study is framed within a teacher-student setting:

• Teacher: A network with $p^*$ hidden neurons generating labels $y(\vec{x})$.
• Student: A network with $p$ hidden neurons attempting to approximate the teacher.
• Data: Input vectors $\vec{x}$ are drawn from a high-dimensional Gaussian distribution ($N \to \infty$), with the number of samples $M = \alpha N$.
• Key Variables: The study focuses on the overparameterized regime ($p > p^*$) and the case where the teacher has multiple hidden units ($p^* > 1$).

The core questions addressed are:

1. How does overparameterization ($p > p^*$) affect the time required to escape the initial "uninformative" plateau where generalization is poor?
2. What is the geometry of the loss landscape, specifically regarding the existence of zero-loss solutions?
3. How does the optimization dynamics select a specific solution among the many equivalent zero-loss configurations (implicit bias)?

2. Methodology

The authors employ a rigorous theoretical framework combining statistical physics and dynamical systems:

• High-Dimensional Limit: They analyze the limit where input dimension $N$ and sample size $M$ diverge while keeping the ratio $\alpha = M/N$ finite. The hidden widths $p$ and $p^*$ remain finite ($O(1)$).
• Order Parameters: The dynamics are reduced to low-dimensional Ordinary Differential Equations (ODEs) governing the evolution of:
  • Teacher-Student Overlap Matrix ($\rho$): $\rho_{kl} = \frac{\vec{w}_k \cdot \vec{w}^*_l}{N}$.
  • Student-Student Overlap Matrix ($Q$): $Q_{kk'} = \frac{\vec{w}_k \cdot \vec{w}_{k'}}{N}$.
• Dynamical Equations: Using the framework of online learning in high dimensions (referencing seminal works like Saad & Solla, Goldt et al.), they derive deterministic ODEs for $\rho$ and $Q$ under the assumption of small learning rates ($\eta \ll 1$), effectively modeling gradient flow on the population risk.
• Landscape Analysis: They perform a Hessian analysis of the population risk landscape to characterize critical points (saddles, minima) and their eigenvalue spectra.
• Initialization: To avoid trivial fixed points (where weights remain zero), the student is initialized with small random overlaps with the teacher and orthogonal student weights.

3. Key Contributions and Results

A. Dynamics of Learning: The "Plateau" and Escape

The learning process exhibits distinct phases:

1. Norm Learning: Initially, the norms of student weights ($Q_{kk}$) evolve rapidly to a fixed point $\bar{Q} = p/(p+2)$, while overlaps remain near zero.
2. The Plateau: The system enters a region of slow learning where the population risk is high. The student weights are orthogonal to the teacher ($\rho \approx 0$).
   • Escape Dynamics: The escape from this plateau is governed by the exponential growth of overlaps: $\frac{d\rho}{dt} \propto \rho$.
   • Role of Overparameterization: The authors find that increasing the student width $p$ only modestly accelerates the escape. The characteristic timescale is determined by the teacher complexity $p^*$ (specifically $\tau \sim p^*/16$). Overparameterization affects the prefactor of the exponential decay (making the initial "kick" slightly larger due to more independent nodes trying to align) but does not change the fundamental timescale.
   • Conclusion: Overparameterization does not fundamentally alter the difficulty of escaping the uninformative region in this specific quadratic setting; it remains a "hard" problem for small sample sizes.

B. Geometry of the Loss Landscape

The paper reveals a fundamental difference between the $p^*=1$ (Phase Retrieval) and $p^*>1$ cases:

• Continuous Manifold of Solutions: Unlike the discrete set of solutions in Phase Retrieval, for $p^* > 1$, the zero-loss solutions form a continuous manifold. This arises from the rotational symmetry of the student weight matrix $W$. Any rotation $W' = RW$ (where $R$ is orthogonal) that preserves the output structure yields the same loss.
• Critical Points:
  • Tabula Rasa ($W=0$): A local maximum (all eigenvalues of Hessian are negative).
  • Plateau ($W \perp W^*$): A saddle point with a mix of negative, positive, and null eigenvalues. The ratio of negative to null eigenvalues dictates the difficulty of escape.
  • Zero-Error Solutions: These are marginal minima. The Hessian has only non-negative eigenvalues.
    • Null Eigenvalues: Correspond to two types of flat directions:
      1. Symmetry-induced: Tangent to the manifold of equivalent solutions (rotations).
      2. Overparameterization-induced: Directions existing only when $p > p^*$, representing "wider" minima.

C. Implicit Bias and Solution Selection

Despite the existence of a continuous manifold of zero-loss solutions, the dynamics do not converge to an arbitrary point.

• The Claim: The SGD dynamics consistently select the zero-error solution closest to the random initialization in Euclidean distance.
• Mechanism: This selection is enforced by a conserved quantity in the ODEs. The matrix $S(t) = \rho(t)[\rho(t)^T \rho(t)]^{-1/2}$ remains constant throughout the training trajectory.
• Implication: The final learned weights are determined entirely by the initial random overlaps. This provides a concrete example of implicit bias in gradient-based optimization, where the algorithm favors geometrically proximate solutions without explicit regularization.

4. Significance and Implications

1. Limits of Overparameterization: The study challenges the notion that overparameterization always drastically simplifies learning. In the specific context of quadratic networks with $p^* > 1$, overparameterization does not remove the "hard" plateau phase; it only slightly improves the escape rate via a prefactor. The difficulty is intrinsic to the teacher's complexity ($p^*$).
2. Symmetry and Degeneracy: The paper highlights that continuous symmetries in the model architecture (rotational invariance) create continuous manifolds of global minima even in the absence of extreme overparameterization ($p=p^* > 1$). This contrasts with standard deep learning intuition where degeneracy is often associated with massive overparameterization.
3. Implicit Bias as a Conservation Law: The identification of a conserved quantity ($S(t)$) linking the initial conditions to the final solution offers a rigorous mathematical explanation for implicit bias. It connects to Noether's theorem, suggesting that continuous symmetries in the loss landscape lead to conserved charges that constrain the optimization trajectory.
4. Generalization and Double Descent: The authors suggest that the variance in the final solution (due to dependence on initialization) contributes to the overfitting peak in the bias-variance trade-off. Overparameterization creates a broad manifold of solutions, and as $p$ increases, the system may exhibit "self-averaging," potentially leading to the double-descent phenomenon observed in modern machine learning.

Summary

This paper provides a precise analytical characterization of online learning in overparameterized quadratic networks. It demonstrates that while overparameterization creates a rich geometry of solutions (a continuous manifold), it does not fundamentally solve the "hard" learning problem of escaping the initial plateau. Instead, the learning dynamics are governed by a conservation law that biases the system toward the solution closest to the initialization, offering deep insights into the interplay between symmetry, geometry, and optimization in neural networks.