📊 statistics

A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyond

This paper introduces a derandomization framework that proves optimizing specific expected functions drives weight matrices to zero under mild conditions, thereby explaining structure discovery in arbitrarily deep and wide neural networks trained to second-order stationary points and enabling applications in MAXCUT approximation and Johnson-Lindenstrauss embeddings.

Original authors: Nikos Tsikouras, Yorgos Pantis, Ioannis Mitliagkas, Christos Tzamos

Published 2026-05-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Nikos Tsikouras, Yorgos Pantis, Ioannis Mitliagkas, Christos Tzamos

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: Finding Order in the Chaos

Imagine you are trying to teach a student (a Neural Network) to solve a complex puzzle. The student has a massive notebook with millions of pages (parameters) and is allowed to write anything on them. Usually, when you train these students, they end up with messy, chaotic notes that are hard to read and hard to explain.

However, in real life, these students often surprise us. They seem to "figure out" a simple, elegant way to solve the problem, ignoring the messy details. They find a hidden pattern or a "low-rank structure."

The Question: Why do they do this? Is it magic, or is it because of the specific rules we give them (like strong penalties for being messy)?

The Answer: This paper says it's not magic, and you don't need heavy penalties. It's a natural consequence of how the student learns when they reach a state of "stability." The authors prove that if a student stops learning and settles down (reaches a "Second-Order Stationary Point"), they must have organized their notes into a simple, low-rank structure, even if you barely told them to be simple.

The Core Idea: The "Derandomization" Lemma

The paper introduces a mathematical tool called a Derandomization Lemma.

The Analogy: The Foggy Room
Imagine you are in a room filled with fog (randomness). You are trying to find a specific spot on the floor.

The Old Way: Previous research said, "To find the spot, you need to turn on a very bright, blinding light (strong regularization) to cut through the fog."
This Paper's Way: The authors say, "You don't need a blinding light. If you just stand still and wait until you stop shaking (reach a stable point), the fog will naturally clear up around you, revealing the spot."

How it works:
The paper looks at a specific type of math problem where the input is random (like rolling dice). They show that if you optimize this problem until you hit a "stable point" (where the math says you can't improve much more), the random part of the solution naturally shrinks to zero.

Think of it like a spinning top. If you spin it wildly, it's chaotic. But as it slows down and reaches a stable, upright position, it stops wobbling. The "wobble" (randomness) disappears, leaving only the "spin" (the useful structure).

Key Ingredients for Success

The authors found that to make this "fog clearing" happen naturally, you need a few specific conditions, which are much more relaxed than what previous studies required:

Don't Freeze the Bias: In the past, researchers sometimes "froze" the bias (a constant number added to the calculation) to make the math easier. The authors show that you must let the bias move.
- Analogy: Imagine trying to balance a broom on your hand. If you lock your wrist (freeze the bias), you have to use a huge amount of force (strong regularization) to keep it upright. If you let your wrist move freely (train the bias), you can balance it with almost no effort. The bias adjusts itself to make the solution simple.
Tiny Regularization: You don't need to punish the student for being complex. A tiny, almost invisible nudge is enough.
- Analogy: You don't need a bouncer to stop a party from getting wild; sometimes just a gentle reminder that "we need to leave soon" is enough for everyone to pack up and leave in an orderly fashion.
Any Smooth Loss: It works with almost any standard way of measuring mistakes, as long as the math is "smooth" (no sharp, jagged edges).

Real-World Applications (What the Paper Actually Claims)

The authors didn't just prove this for neural networks; they showed this "fog clearing" trick works in three specific areas:

1. Neural Networks (The Main Event)

The Claim: If you train a neural network (of any size or depth) until it stabilizes, the first layer of the network will naturally align itself with the most important directions in the data.
The Result: The network automatically discovers a "low-rank" structure. This means it effectively ignores the noise and focuses on the signal, which helps it generalize better to new data.
The Experiment: They trained a network to learn a simple pattern (a "teacher" model). Even though the network started with random weights, it naturally converged to a simple structure that matched the teacher, proving the theory.

2. The MAXCUT Problem (Cutting a Graph)

The Problem: Imagine a graph of cities connected by roads. You want to split the cities into two groups so that the number of roads connecting the two groups is as high as possible. This is a classic hard math problem.
The Old Way: The famous solution (Goemans & Williamson) uses a "randomized" method. It solves a math problem and then flips a coin to decide which group each city goes into.
The New Way: The authors show you can use their "fog clearing" method to remove the coin flip. Instead of guessing randomly, you can use a simple optimization process to find a specific, deterministic solution that is just as good as the random one.
The Result: A "derandomized" algorithm that finds a great cut without needing to rely on luck.

3. Johnson-Lindenstrauss (JL) Embeddings (Shrinking Data)

The Problem: You have a huge dataset with thousands of dimensions (like a photo with millions of pixels). You want to shrink it to a smaller size (like a thumbnail) without losing the relationships between the points.
The Old Way: Usually, you do this by creating a "random" matrix (a grid of random numbers) to shrink the data. It works, but it's random.
The New Way: The authors show you can learn the best shrinking matrix. Instead of picking random numbers, you optimize the matrix until it becomes "deterministic" (no randomness left).
The Result: They found a specific, non-random matrix that shrinks the data perfectly, proving that you don't need randomness to get the best compression.

Summary in One Sentence

This paper proves that if you let a learning algorithm settle down into a stable state (and let its "bias" adjust freely), it will naturally strip away all the randomness and complexity, revealing a simple, elegant structure—whether it's a neural network learning a pattern, a graph being cut, or data being compressed.

Technical Summary: A Derandomization Framework for Structure Discovery

Problem Statement

Understanding the dynamics of feature learning in neural networks (NNs) remains a significant theoretical challenge. While empirical evidence suggests that NNs trained via gradient-based methods often converge to low-complexity structures that aid generalization, theoretical guarantees have historically been limited. Previous work, such as Mousavi-Hosseini et al. (2023), demonstrated that in a specific teacher-student setting, a two-layer student network trained with Stochastic Gradient Descent (SGD) and a strong regularizer attains a low-rank structure in its first-layer weights. However, these results relied on restrictive assumptions: frozen biases, specific network architectures, and the necessity of strong regularization to force structural collapse.

This paper addresses the question: Can low-rank structure be discovered in neural networks under more natural and minimal assumptions? Specifically, the authors aim to establish structure discovery guarantees for:

NNs of arbitrary size and depth.
Networks where all parameters, including biases, are trainable.
Any smooth loss function.
Arbitrarily small (tiny) regularization.
Optimization methods that converge to a second-order stationary point (SOSP), such as Perturbed Gradient Descent (PGD).

Methodology

The Core Derandomization Lemma

The theoretical foundation of the paper is a Key Derandomization Lemma (Lemma 3.1). The authors analyze an objective function of the form:
$f(W, b; \theta) = \mathbb{E}_x [g_\theta(Wx + b)] + \lambda \|W\|_F^2$
where $x \sim \mathcal{N}(0, I_d)$ , $W$ and $b$ are parameters, $g_\theta$ is a smooth nonlinear function, and $\lambda > 0$ is a regularization parameter.

The lemma states that for any $\rho$ -approximate second-order stationary point ( $\rho$ -SOSP) of this function, the Frobenius norm of $W$ is bounded by:
$\|W\|_F \leq \frac{\rho}{2\lambda - \sqrt{K\rho}}$
where $K$ is the Hessian Lipschitz constant of the objective. Crucially, as $\rho \to 0$ (approaching an exact SOSP), $W$ converges to 0.

Mechanism: The proof relies on Stein's Lemma, which relates the second derivative of the bias term $b$ to the first derivative of the weight matrix $W$ . By analyzing the first-order optimality conditions for $W$ and the second-order conditions (Hessian) for $b$ , the authors show that the curvature constraints at a $\rho$ -SOSP force the weight matrix to vanish (or become low-rank in the decomposed setting) unless the regularization is artificially large.

Application to Neural Networks

The authors apply this lemma to the teacher-student setting where labels are generated by a multiple-index teacher model $y = h(Ux; \epsilon)$ .

Decomposition: The first-layer weights $W$ are decomposed into components parallel ( $W_\parallel$ ) and perpendicular ( $W_\perp$ ) to the teacher's subspace.
Reformulation: The regularized risk is reformulated to isolate the perpendicular component $W_\perp$ . The objective function for $W_\perp$ takes the form required by the Derandomization Lemma.
Result: At any $\rho$ -SOSP, $\|W_\perp\|_F$ is arbitrarily small. This implies that the learned weights align with the principal subspace of the input data defined by the teacher, effectively discovering the low-dimensional structure.

Role of Biases: The paper emphasizes that training biases is essential for this result. If biases are frozen (as in some prior work), the model requires an artificially large regularization to force $W=0$ . By allowing biases to be trained, the model can adjust $b$ to fit the data, allowing the structural discovery (vanishing $W_\perp$ ) to occur even with tiny regularization.

Handling Non-Smooth Activations: For ReLU networks, the authors employ a smooth approximation (e.g., $ReLU_\iota(x) = \frac{1}{\iota}\log(1+e^{\iota x})$ ) to satisfy the smoothness and Hessian Lipschitz assumptions required for the $\rho$ -SOSP definition.

Key Contributions

General Derandomization Lemma: A theoretical result showing that optimizing functions of the form $\mathbb{E}[g(Wx+b)] + \lambda\|W\|^2$ leads to $W \to 0$ at SOSPs, effectively "derandomizing" the input dependence.
Relaxed Assumptions for Structure Discovery: The paper extends previous findings to:
- Arbitrary network depth and width.
- Fully trainable parameters (including biases).
- Any smooth loss function.
- Arbitrarily small regularization ( $\lambda$ ), provided the optimization reaches a sufficiently precise $\rho$ -SOSP.
Theoretical Guarantees for PGD: The authors demonstrate that Perturbed Gradient Descent (PGD) can efficiently find $\rho$ -SOSPs in polynomial time, thereby guaranteeing the discovery of low-rank structures in practice.
Cross-Domain Applications: The framework is applied to two other domains:
- MAXCUT: A deterministic approximation algorithm for MAXCUT that matches the randomized Goemans-Williamson guarantee, achieved via gradient-based optimization without explicit combinatorial constructions.
- Johnson-Lindenstrauss (JL) Embeddings: A deterministic construction for learning JL embeddings by optimizing the distribution of projection matrices to minimize worst-case distortion.

Results

Neural Networks

Theoretical: Theorem 4.1 and 4.2 establish that for any NN satisfying smoothness assumptions, minimizing the regularized risk leads to a weight matrix where the perpendicular component $W_\perp$ is bounded by $\mathcal{O}(\rho/\lambda)$ .
Empirical: Experiments on a two-layer ReLU network trained to recover a single-index teacher model show that the first-layer weights converge to the principal subspace spanned by the teacher direction. The training utilizes PGD with isotropic noise injection to escape saddle points.

MAXCUT

The authors present a deterministic algorithm that approximates the MAXCUT value. By optimizing a smoothed objective function derived from the Goemans-Williamson SDP relaxation, they achieve a cut value of at least $\alpha \cdot \text{OPT} - \mathcal{O}(\epsilon)$ , where $\alpha \approx 0.878$ . This is achieved without relying on the method of conditional expectations or pseudorandom generators.

Johnson-Lindenstrauss Embeddings

The paper demonstrates that optimizing the parameters of a Gaussian distribution over projection matrices (mean and variance) can yield a deterministic matrix that satisfies the JL guarantee with distortion $\mathcal{O}(\epsilon)$ . Experiments show that this learned projection achieves near-zero distortion, outperforming standard random Gaussian projections.

Significance and Claims

The paper claims that structure discovery is an inherent characteristic of the optimization landscape for problems involving expectations over Gaussian inputs, provided the solution is a second-order stationary point.

Implicit Regularization: The work provides a new explanation for parsimony (low-rank solutions) in NNs. It suggests that the "implicit regularization" effect of gradient descent is not solely due to the algorithm's trajectory but is a property of the stationary points themselves, which naturally suppress randomness (i.e., drive $W_\perp \to 0$ ) even with minimal explicit regularization.
Necessity of Biases: The authors highlight that training biases is not just a practical heuristic but a theoretical necessity for achieving these structural guarantees under mild conditions.
Unified Framework: The significance lies in the unification of structure discovery in NNs with derandomization in combinatorial optimization. The same mathematical lemma explains why NNs learn low-dimensional representations and how to deterministically construct optimal cuts and embeddings.

The authors remain modest regarding generalization guarantees, noting that their results focus strictly on structure discovery (the geometry of the solution) rather than the statistical performance (generalization error) on unseen data, which would require additional assumptions on the data distribution or hypothesis class. They also acknowledge the current limitation of assuming Gaussian input distributions, suggesting this as a direction for future research.