Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks

arXiv:2502.11152 · math.OC, cs.LG · Submitted 2026-08-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks".

Jane: The paper was written by Po Chen, Rujun Jiang and Peng Wang from Fudan University and University of Macau.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the show, everyone. Today we're digging into a fresh arXiv paper that's got the optimization community buzzing. It's called "Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks."

Jane: And Tom, I have to say, when I first saw that title, I thought, okay, another deep learning theory paper. But this one is genuinely different. It's tackling a question that's been nagging at researchers for years.

Tom: Right, and for our listeners who aren't steeped in the math, let's break down what we're actually looking at. A deep linear network is basically a stack of matrix multiplications. No fancy activation functions, just layers of linear transformations.

Jane: Exactly. And the "regularized loss" part means we're adding a penalty term to keep the weights from exploding. The paper is asking a deceptively simple question: when you're training one of these networks, can we actually guarantee that the algorithm will converge nicely to a solution?

Lu: And that's where the "error bound" comes in. It's a mathematical guarantee that tells us the distance to a solution is controlled by the size of the gradient. If the gradient is small, you're close to a critical point.

Tom: So it's like saying, if you're walking downhill and the slope gets gentle, you know you're near the valley floor.

Lu: Precisely. And this paper proves that this property holds for deep linear networks under some mild conditions on the network width and the regularization parameters.

Jane: Which is a big deal because these networks, even though they're linear, have a loss landscape that's full of saddle points and local minima. It's not a convex problem, so you can't just assume nice behavior.

Tom: And the authors, Po Chen, Rujun Jiang, and Peng Wang, they didn't just prove it for the global optimum. They proved it for *every* critical point. That's the part that really caught my attention.

Meng: So the error bound holds even around saddle points? That seems almost too good to be true.

Lu: It does, but that's exactly what the theorem states. And it's important because in practice, gradient descent often gets stuck near saddle points for a long time. Knowing that the error bound holds there tells us something about how the algorithm will behave in those regions.

Jane: And that's the hook for our next segment. We're going to look at what this actually means for the convergence of training algorithms.

Summary: Tom: So we've established that this paper, "Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks," proves a powerful property around critical points. But what does that property actually buy us?

Jane: Right. The summary of the paper is that this error bound is the missing piece for proving that gradient descent converges linearly. That means the error shrinks by a constant factor at every step, which is the gold standard for optimization algorithms.

Lu: And the beauty of their approach is that it's a unified framework. Instead of analyzing a specific initialization scheme or a specific network architecture, they prove a general property of the loss landscape itself.

Meng: So instead of saying, "If you start here, you'll converge," they're saying, "No matter where you start, as long as you're near a critical point, the geometry of the problem guarantees you'll get there fast."

Tom: Exactly. And that's a much more robust result. The paper shows that the error bound holds for the set of all critical points, not just the global minima.

Jane: And that's what makes it so useful. In practice, you don't always converge to the global minimum. You might get stuck at a saddle point or a local minimum. But this paper says that even then, the convergence behavior is predictable and linear.

Lu: It also connects to other well-known conditions in optimization. The paper shows that the error bound implies the Polyak-Lojasiewicz inequality and the quadratic growth condition. These are all different ways of saying the same thing: the loss function is well-behaved around its critical points.

Meng: So it's like they've shown that all these different regularity conditions are actually equivalent in this setting.

Lu: That's right. And that's a significant theoretical contribution because it unifies a lot of prior work.

Tom: And the practical implication is that we can now analyze the convergence of a whole family of first-order methods, not just vanilla gradient descent.

Jane: That's the big picture. But the details of how they actually prove this are fascinating. They had to develop some new mathematical tools to handle the complex structure of the critical point set.

Tom: And that's what we're going to dig into next. How did they actually pull this off?

Improvements: Tom: Welcome back. We're talking about "Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks." We've covered what the error bound is and why it matters. Now, what did the authors actually improve upon?

Jane: Well, Tom, the key improvement is that they moved beyond the two-layer case. A lot of previous work on error bounds for linear networks was limited to just two layers.

Lu: Exactly. And they also extended the analysis from just global optimal solutions to *all* critical points. That's a major step forward.

Meng: So the previous work was like only being able to prove you'd reach the bottom of the valley if you started on the right side. Now they're saying, no matter where you are on the mountain, you'll get to a stable point.

Lu: That's a good way to put it. And to do that, they had to develop some new techniques to handle the fact that the critical point set isn't just a single point. It's a union of connected sets, which makes it much harder to analyze.

Jane: Right. The critical points form these complicated manifolds, and computing the distance to them isn't straightforward.

Tom: So what was their trick?

Lu: They first specialized a known characterization of the critical points under a mild assumption on the network width. Then they used a clever decomposition of the weight matrices to show that the singular values and singular vectors are controlled by the gradient norm.

Meng: That sounds like a lot of linear algebra.

Jane: It is. But the result is that they get explicit constants. They don't just say "there exists a bound." They actually give you the formulas for the constants, which is really useful if you want to use this in practice.

Tom: And they also identified the exact conditions under which the error bound holds. They showed that if the regularization parameters hit a specific degenerate value, the error bound fails.

Lu: That's a nice touch. It shows they really understand the problem. They didn't just prove a sufficient condition; they proved a necessary and sufficient condition.

Meng: So they know exactly when their theorem applies and when it doesn't. That's the mark of a complete analysis.

Jane: And this sets up the next part of our discussion: the actual proof and the technical machinery they built.

First Page: Tom: So we're now looking at the first page of "Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks," and it's packed with context.

Jane: It really is. The introduction lays out the problem beautifully. They start by noting that while deep learning has had huge empirical success, our theoretical understanding of even the simplest case—linear networks—is incomplete.

Lu: And they point out a critical gap. Most existing convergence analyses are tailored to specific initialization schemes and only prove convergence to global optima. But in practice, you might converge to a saddle point or a local minimum.

Meng: So the existing theory doesn't cover what actually happens when you run the algorithm.

Jane: Exactly. And that's where the error bound comes in. It's a way to analyze convergence to *any* critical point, not just the global ones.

Tom: And the first page also introduces the problem formulation. They're looking at minimizing the squared Frobenius norm of the difference between the product of the weight matrices and a target matrix, plus a regularization term.

Lu: That's the standard setup for deep linear networks. And they mention that this formulation captures a wide range of problems, including deep matrix factorization and low-rank adaptation.

Meng: So this isn't just a toy problem. It's connected to real applications.

Jane: Right. And they also discuss the limitations of prior work. They mention that the existing analyses are "highly specific" and rely on "carefully designed weight initialization schemes."

Tom: That's a polite way of saying the previous proofs were fragile.

Lu: It is. And their goal is to develop a unified framework that doesn't depend on those fragile assumptions.

Meng: So the first page sets the stage for a much more general and robust theory.

Jane: And it's a theory that has practical implications. The error bound they prove can be used to show linear convergence of gradient descent, which is what we see in practice.

Tom: And that's the perfect segue into our final segment, where we wrap up and talk about what this all means.

Conclusion: Tom: We've spent a lot of time with "Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks," and it's time to wrap up our thoughts.

Jane: It really has been a fascinating paper. To summarize, the authors proved that the error bound holds for the set of all critical points of the regularized squared loss for deep linear networks.

Lu: And they did it under mild conditions on the network width and the regularization parameters. They even identified the exact conditions where the error bound fails, which shows a deep understanding of the problem.

Meng: The practical impact is that this gives us a unified framework to prove linear convergence for a whole class of first-order methods, not just gradient descent.

Tom: And the numerical experiments they ran support their theoretical findings. They showed that gradient descent converges linearly to critical points, whether they're global minima or not.

Jane: That's the kind of result that makes you feel like the theory is actually capturing what's happening in practice.

Lu: And it opens up new directions. The authors suggest extending this analysis to more general data inputs and loss functions. And of course, the big open question is whether similar results can be proven for deep *nonlinear* networks.

Meng: That would be the ultimate goal. But this paper is a solid step in that direction.

Tom: Absolutely. It's a rigorous, complete, and practical piece of work. We're saying goodbye to this paper and getting ready to dive into the next one.

Jane: Thanks for joining us, everyone. We'll see you next time on the arXiv review.

Po Chen, Rujun Jiang, Peng Wang

Fudan University · University of Macau

math.OC, cs.LG

Submitted: 2026-08-08

Comments: 44 pages, 2 figures, 2 tables; This paper is accepted for publication in Mathematics of Operations Research

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 60/100

The gist: This paper studies the regularized squared loss of deep linear neural networks: [W F(W):= W L W 1 - Y F squared + sum l=1 L lambda l W l F squared,] where L at least 2 denotes the number of layers, Y

Key concepts

Deep Linear Network: A deep linear network is essentially a stack of matrix multiplications without any fancy activation functions. It consists only of layers of linear transformations applied sequentially to the data.
Regularized Loss: This refers to adding a penalty term to the loss function during training. This penalty term is used to keep the weights in the network from becoming too large, which helps prevent weight explosion.
Error Bound: An error bound is a mathematical guarantee that controls how close an algorithm's current state is to a solution. If the gradient is small, this bound tells us you are near a critical point or solution.
Critical Point: A critical point in the loss landscape is any location where the gradient of the loss function is zero. The paper proves that convergence behavior can be analyzed around all such points, including saddle points.

Terminology

Regularization — 20× in this paper · explained in 3 episodes
Activation Function — 6× in this paper · explained in 1 episode
Loss Function — 6× in this paper · explained in 2 episodes
Unified Framework — 6× in this paper · explained in 5 episodes
Adaptation — 5× in this paper · explained in 1 episode
Objective Function — 4× in this paper · explained in 2 episodes
Alternating Minimization — 2× in this paper · explained in 1 episode
Convergence Guarantees — 2× in this paper · explained in 3 episodes
Generalization — 2× in this paper · explained in 13 episodes
Adam — 1× in this paper · explained in 2 episodes
Ambient Dimension — 1× in this paper · explained in 1 episode
Gradient Flow — 1× in this paper · explained in 2 episodes
Spectral Gap — 1× in this paper · explained in 5 episodes

Summary

This paper studies the regularized squared loss of deep linear neural networks:

[

W F(W):= W L W 1 - Y F squared + sum l=1 L lambda l W l F squared,

]

where L at least 2 denotes the number of layers, Y in R d L times d 0 denotes the target matrix, W l in R d l times d l-1 denotes the l-th weight matrix, and lambda l > 0 for all l are regularization parameters. The paper notes that this problem captures a wide range of deep learning problems, including deep matrix factorization, neural collapse, and low-rank adaptation of learning models.

The authors identify a key gap in the literature: "the existing analyses only apply to analyze the convergence to global optimal solutions. However, Problem (1) and its unregularized counterpart may have other local solutions, to which first-order methods, such as GD, are likely to converge. To the best of our knowledge, the convergence behavior of first-order methods when they approach a critical point—whether a global minimum, a local minimum, or even a saddle point—remains an open question in the literature."

The paper first establishes a closed-form characterization of the critical point set under Assumption 1, which requires that the network widths satisfy d 1,, d L-1 at least d 0, d L. This assumption ensures that the width of each hidden layer is no less than that of the input or output layer and aligns with common practices in deep learning, where hidden layers are typically designed to be wide.

Theorem 1 provides the characterization: W in W F if and only if the weight matrices take specific forms involving orthogonal matrices Q l in O d l-1, block orthogonal matrices O i in O h i, and diagonal matrices l = BlkD(diag(sigma)/sqrt lambda l, 0) where sigma in R r Y satisfies the polynomial equation:

[

sigma i 2L-1 - sqrt lambda y i sigma i L-1 + lambda sigma i = 0, sigma i at least 0, i in [r Y],

]

with lambda:= product l=1 L lambda l.

The main result is Theorem 2, which establishes that under Assumptions 1 and 2, "there exist constants epsilon 1, kappa 1 > 0 such that for all W satisfying dist(W, W F) at most epsilon 1, we have dist(W, W F) at most kappa 1 grad F(W) F."

Assumption 2 imposes conditions on the regularization parameters relative to the singular values of Y. For L = 2, it requires lambda:= lambda 1 lambda 2 not equal to y i squared for all i in [r Y]. For L at least 3, it requires:

[

lambda:= lambda 1 lambda L not equal to y i 2(L-1) (L-2 over L) L over 2(L-1) [(L over L-2) L-2 over 2(L-1) + (L over L-2)-L-2 over 2(L-1)]-2(L-1), i in [r Y].

]

The paper shows this assumption is necessary and sufficient: if Assumption 2 does not hold, the error bound fails to hold (see Appendix A). Conversely, if Assumption 2 holds, the error bound holds.

Corollary 1 derives two additional regularity conditions from the error bound:

(i) PL inequality: "There exists a constant mu 1 > 0 such that grad F(W) F squared at least mu 1 F(W) - F(W*) " in a neighborhood of any critical point W*.
(ii) Quadratic growth: "If, in addition, W* is a local minimizer, there exists a constant mu 2 > 0 such that dist 2(W, W F) at most mu 2 (F(W) - F(W*))."

The paper notes that these regularity conditions (the error bound, the PL inequality, and the quadratic growth condition) are shown to be equivalent in [41] under the additional assumption that the point is a local minimizer.

Proposition 6 (in Appendix C) shows that if a sequence W k satisfies two conditions—(i) sufficient decrease: F(W k+1) - F(W k) at most-kappa 1 W k+1 - W k F squared, and (ii) relative error: grad F(W k+1) F at most kappa 2 W k+1 - W k F —then "there exists k 1 > 0 such that for all k at least k 1, W k k at least k 1 converges R-linearly to W* for some W* in W F, and F(W k) k at least k 1 converges Q-linearly to F(W*)."

The paper emphasizes that "in contrast to algorithm-specific convergence rate analyses in [6, 12, 25, 37, 48], the error-bound-based framework provides a unified analytical approach. In particular, it applies not only to GD but also to a broad class of first-order methods capable of optimizing Problem (1)."

The proof strategy involves several key steps:

Reduction to a simpler problem: The paper shows (Lemma 1) that it suffices to study the problem W G(W):= W L W 1 - sqrt lambda Y F squared + lambda sum l=1 L W l F squared, where lambda:= product l=1 L lambda l.
Structural analysis of critical points: Proposition 1 shows that for any pair (sigma,) in B and (sigma', ') in B, if sigma not equal to sigma', W(sigma,) is well separated from W(sigma', '), and otherwise they are identical. This allows the critical point set to be expressed as a finite union of well-separated sets.
Handling the zero critical point: Proposition 2 establishes the error bound for the case sigma* = 0 with explicit constants.
Bounding singular values and vectors: Proposition 4 bounds the smallest singular values of weight matrices, while Proposition 5 bounds the top r sigma singular values and the singular vectors using the Davis-Kahan theorem.
Construction of an intermediate point: In the proof of Theorem 3, the authors construct a point using left and right singular matrices of W and show that both dist(, W G) and W - F are bounded by grad G(W) F.

The paper highlights that "unlike prior works [35, 26, 27, 47], where the critical point set W F has a relatively simple structure that allows for closed-form computation of the distance dist(W, W F), the presence of orthogonal permutations and hierarchical structures in W F (see Theorem 1) prevents such computation. To address this challenge, we develop a suite of new techniques (see Section 3.2.2), which offer a new framework for establishing error bounds of non-convex problems with complex solution sets."

The paper conducts numerical experiments using gradient descent with the PyTorch library, terminating when grad F(W k) F squared at most 10-6 and F(W k) - F(W k-1) at most 10-7.

The paper sets d L = 20, d 0 = 10, d l = 32 for each l = 1,, L-1, samples Y from the standard Gaussian distribution, sets lambda l = 10-4 for all l, and uses learning rate 4.5 times 10-4. The weights are initialized near both optimal and non-optimal critical points constructed using Theorem 1.

The results show that GD converges to an optimal solution at a linear rate for solving Problem (1) with different network depths, and similarly, it converges to a non-optimal critical point at a linear rate for L = 4, 6. The paper notes that "Problem (1) only has global optima and strict saddle points when L = 2, as shown in [11]. Therefore, even if initialized in the vicinity of a non-optimal critical point, i.e., strict saddle point, the algorithm will ultimately converge to a global optimal point almost surely."

The paper investigates three more general setups with L = 4, d L = 16, d 0 = 10, d l = 32 for l = 2,, L-1, lambda l = 5 times 10-5, and learning rate 10-3:

General data input: Using non-orthogonal data matrices X 1, X 2, X 3 with condition numbers 43.43, 36.04, and 16.36, respectively.
Linear networks with bias: Adding bias terms to the network.
Deep nonlinear networks: Using ReLU, Leaky ReLU, and tanh activation functions.

The paper observes that GD converges to a solution at a linear rate across these settings. This consistent behavior leads us to conjecture that the error-bound condition may hold for deep networks in more general scenarios. Additionally, the number of iterations required to meet the stopping criterion generally increases as the condition number of the input data becomes larger.

The paper identifies two future research directions: One future direction is to extend our analysis to deep linear networks with more general data input X and loss functions. Another interesting direction is to investigate the regularized loss of deep nonlinear networks.

Improvements for AI systems

Based on the paper, here are specific improvements for AI systems:

Add error-bound-based convergence monitoring: Implement a runtime check that estimates dist(W, W F) using the gradient norm ∥∇F(W)∥ F during training. When this distance stops decreasing proportionally to the gradient norm, the system can detect convergence to a critical point (local minimum, saddle point, or global minimum) and terminate early, saving computational resources.
Guarantee linear convergence for deep linear networks: Modify existing gradient descent implementations for deep linear networks to include the regularization terms λ l ∥W l∥2 F as specified in Problem (1). Under Assumptions 1 and 2 (width conditions and regularization parameter constraints), the system can now provably achieve linear convergence to critical points, not just global optima. This is a significant improvement over existing methods that only guarantee convergence to global solutions under specific initialization schemes.
Implement adaptive regularization parameter selection: Use the necessary and sufficient conditions in Assumption 2 (Equations 7 and 8) to automatically select regularization parameters λ l that ensure the error bound holds. The system can check whether λ = ∏λ l avoids the critical values specified in these equations, guaranteeing the theoretical convergence guarantees apply.
Width-aware architecture design: Before training, verify that min d1,..., d L-1 ≥ min d0, d L (Assumption 1). If violated, the system can automatically adjust hidden layer widths to satisfy this condition, ensuring the closed-form critical point characterization (Theorem 1) applies and the error bound holds.
Critical point classification: Using Theorem 1's characterization, the system can classify any critical point by computing the singular values σ from Equation (6). This allows the AI system to distinguish between global optima, local minima, and saddle points during training, enabling informed decisions about whether to continue training or restart with different initialization.
Early stopping with theoretical guarantees: Implement a stopping criterion based on the error bound: stop when dist(W, W F) ≤ κ1∥∇F(W)∥ F with the explicit constants from Equation (123). This provides a rigorous stopping condition that guarantees the current iterate is within a known distance of a critical point, unlike heuristic stopping rules.
Initialization strategy for guaranteed convergence: Use the critical point structure from Theorem 1 to design initialization schemes. Initialize weight matrices near known critical points (constructed from the SVD of Y and solutions to Equation 6) to ensure the error bound holds from the start, guaranteeing linear convergence from the first iteration.
Saddle point escape detection: For L=2 networks, the system can detect when it's approaching a strict saddle point (which are the only non-global critical points) and automatically perturb the weights to escape, since the paper shows these are the only problematic points in this case.
Regularization-aware loss landscape analysis: The system can use the explicit critical point characterization to predict which local minima the optimization will converge to based on initialization, allowing for better model selection and ensemble strategies that explore different critical points.
Transfer learning with convergence guarantees: When fine-tuning pre-trained deep linear networks, the system can verify that the new regularization parameters satisfy Assumption 2 for the target data's singular values, ensuring the fine-tuning process converges linearly to a critical point of the new objective.