Blessing of Depth in Linear Regression: Deeper Models Have Flatter Landscape Around the True Solution
Authors: Jianhao Ma
Salar Fattahi
Venue: NeurIPS 2022 Accept (2022)
Keywords: deep linear network
trajectory analysis

Abstract: This work characterizes the effect of depth on the optimization landscape of linear regression, showing that, despite their nonconvexity, deeper models have more desirable optimization landscape. We consider a robust and over-parameterized setting, where a subset of measurements are grossly corrupted with noise, and the true linear model is captured via an $N$-layer diagonal linear neural network. On the negative side, we show that this problem does not have a benign landscape: given any $N\geq 1$, with constant probability, there exists a solution corresponding to the ground truth that is neither local nor global minimum. However, on the positive side, we prove that, for any $N$-layer model with $N\geq 2$, a simple sub-gradient method becomes oblivious to such “problematic” solutions; instead, it converges to a balanced solution that is not only close to the ground truth but also enjoys a flat local landscape, thereby eschewing the need for “early stopping”. Lastly, we empirically verify that the desirable optimization landscape of deeper models extends to other robust learning tasks, including deep matrix recovery and deep ReLU networks with $\ell_1$-loss.

Blessing of Depth in Linear Regression: Deeper Models Have Flatter Landscape Around the True Solution
Jianhao Ma
Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109 j rianhao@umi ch. edu
Salar Fattahi
Department Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109 fattahi @umich ch, edu
Abstract
This work characterizes the effect of depth on the optimization landscape of linear regression, showing that, despite their nonconvexity, deeper models have more desirable optimization landscape. We consider robust and over-vveane wver-parameterized setting, where subset of measurements are grossly corrupted with noise, and the true linear model is captured via an N-layer diagonal linear neural network. On the negative side, we show that this problem does not have a benign landscape: given any N 2 1, with constant probability, there exists solution corresponding to the ground truth that is neither local nor global minimum. However, on the positive side, we prove that, for any N N-layer model with N 2, a simple sub-gradient method becomes oblivious to such "problematic" solutions; instead, it converges balanced solution that is not only close to the ground truth but also enjoys a flat local landscape, thereby eschewing the need for "early stopping". Lastly, empirically verify that the desirable optimization landscape of deeper models extends to other robust learning tasks, including deep matrix recovery and deep ReL.U networks with -osss.
Introduction
Supported by the empirical success of deep models in contemporary learning tasks, by now conventional wisdom that "deeper models generalize better" [21 31 7. Indeed, the fluryy of recent attempts towards demystifying this phenomenon is a testament to the amount of research it has spawned: from simple linear regression more complex and nonlinear models, it is shown that deeper models benefit from range of desirable statistical properties, such as depth separation [K few.
15
35
implicit bias T9
10], and hierarchical learning (1. to
Despite the great promise of deeper models-bon both theoretically and empirically- the effect of depth on their optimization landscape has remained elusive to this day. A recent body of work attempts to characterize the effect depth on the loss function through the notion benign landscape. Roughly speaking, an optimization problem has benign landscape if it is devoid of spurious local minima, and its true solutions ie., solutions corresponding to the ground coincide with global minima.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(a) I-layer
(b) 2-layer
(c) 3-layer
generall istionn
107
generalizaton ertor emprrcc rical loss
50
generelization error
10"4
Itrra on
Deration?
Itratlor T
layer
(c) 2-layr
(f) 3-layer
Figure 1: First row. Local landscape around the balanced solution w' = V0 V0* for 1-, 2-, and 3-layer models. x and y axis correspond to the points of the form w of a and 3, where c and h are respectively the most descent sub-gradient direction and the most negatively curved direction of the Hessian after smoothing. Second row. Generalization error and the empirical loss of the solutions found by SubGM for 1-, 2-, and 3-layer models.
Sh. different values
It has been shown that 2-layer [3] and multi-layer linear neural networks with nearly-noiseless data have benign landscape. However, the notion of benign landscape is significantly stronger than what needed in practice. For instance, the existence of spurious local minima may not pose any issue if an optimization algorithm can avoid them efficiently. Another line of research focuses on characterizing the solution trajectory of different local-search algorithms, showing that they enjoy an implicit bias that steers them away from undesirable solutions [25] 38 10 [9
24
[8]. However, such guarantees only apply to specific trajectories of algorithm, thereby falling short of any meaningful characterization of the optimization landscape around those trajectories.
1.1 Our Contributions
To shed light the effect of depth the optimization landscape of deep models, we consider prototypical problem in machine learning, namely robust linear regression, where the goal is to recover linear model from limited number of grossly corrupted measurements. Given samples of the form = (0", . + ε., we study the optimization landscape of flloss under an N-layer model defined as y fw (x) (w) W2
O WN 2². Our results are summarized follows:
We prove that, for any N 2 1, there exists at least one true solution that neither local nor global minimum of fo-loss, provided that at least fraction corrupted with noise.
of the measurements
Despite the ubiquity of such "hidden" true solutions, we show that, for any N N-layer model with N 2 2, simple sub-gradient method (SubGM) with small initialization converges small neighborhood of balanced true solution. The radius of this neighborhood shrinks with the depth of the model, resulting in more accurate solutions. Moreover, the balancedness of the solution implies that each layer the model inherits a similar sparsity pattern to the ground truth.
We prove that deeper models take longer to train, but once trained, the algorithm will stay close the ground truth for longer time. This implies that early stopping of the algorithm becomes less crucial for deeper models.
Finally, we prove that depth flattens the optimization landscape around the solution obtained by SubGM. In particular, we show that, within 7-neighborhood of the true solution, the steepest descent direction can reduce the loss by most O (2^), which decreases exponentially with N.

---

Motivating Example. To showcase our results, we consider an instance of robust linear regression in the ver-parameterized setting, where the dimension of 6* is 500 and the number of available samples is 300. Moreover, we assume that 10% of the measurements are corrupted with large noise. The first row of Figure shows the landscape around the balanced ground truth wi VØ*, w = Vo-..... w V In particular, and y axis show the most descent sub- aub-gradient direction and the most negatively curved direction of the Hessian after smoothing Evidently, there is a sharp transition in the landscape of N --layer models: for the 1-layer model, the true solution has strictly negative directions along both sub- uub-gradient and negative curvature. However, these descent directions almost disappear in 2- and 3-layer models. The second row of Figure [ the performance of SubGM on these models. It can be observed that I-layer model easily overfits to noise, leading to vacuous generalization error. On the contrary, a 3-layer model can find a solution that generalizes progressively better than 1- and 2-layer models, demonstrating the algorithmic benefit of the depth.
Notations: For two vectors x, y E IRd, their inner product is defined as (æ, y) = x' y. and their Hadamard product is defined as x O = [1181 rayall T For simplicity of notation, we use II, wy to denote the Hadamard product of W1, W2,..., WN E _.. For a vector || || 2o and ||=||o refer to 2-norm, oc-norm, and the number of nonzero elements, respectively. The symbols a; S bc and = (bb) are used to denote a, I Cbb,, for a universal constant C. The notation a, = O(b,) used to denote a₂ Obb) and b, 12(a)). The Sign(-) function is defined as Sign(x) = z/|ai
if x A 0, and (ign(0) = [-1, We denote [m] == 21, .n.. For vector x E Rd, define x² = [nf x: ... x;] for any a > O. In all of our probabilistic arguments, the randomness is only
over the input data and noise.
2 Problem Formulation
We study the problem of robust and sparse linear regression, where the goal is to estimate a k-sparse
vector 6* E Rd (k < d) from a limited number of data points [(T;, y4) } where yi = (0", xx) Es, T, is i...d standard Gaussian vector, and e; is noise. Moreover, for simplicity of our subsequent analysis, we assume that 0* is a non-negative vector. We believe that this assumption can be relaxed without significant change our results.
Assumption 1 (Noise Model). Given a corruption probability p. the noise vector E = [E1 ... Em] E RTT is generated as follows: first, a subset C [m]] with cardinality pm is chosen uniformly at random { Then, for each entry i E S, the value e; is drawn independently from a distribution Po. and all the remaining entries are set to zero. Moreover, a random variable under the distribution P. satisfies Ep, [S] O and P([[] to) 2 Po. for some strictly positive constants to and po-
Our considered noise model does not impose any assumption on the magnitude of the noise or the specific form of its distribution, which makes it particularly suitable for modeling outliers. Note that the assumption [|=|| 2 to) 2 Po is very mild and satisfied for almost all common distributions. Roughly speaking, it implies that the noise takes nonzero value with a nonzero probability.
To capture the onput-output relationship, we consider a class of N-layer diagonal linear neural networks of the form fw (x) = (wi ① ... ② WN, 2T), where w == (wi,''. , wx) collects the weights of the layers Wi, wN E Rd. Due to the sparse-and-large nature of the noise, it is natural to minimize the so-called empirical risk with -loss:
1 m
m
min L(w) w
=
Σ m
(1,) - Mal
Σ m
(w) O ... OWN x.) -ys-
(1)
Other variants of empirical risk minimization for linear regression have been studied in the literature. For instance, [1O] study the solution trajectory of gradient flow on lo-loss, showing that it converges to a solution with the smallest l -norm. Similar analysis has also appeared in more general deep linear neural networks
[3 14] However, is well-known that loss highly sensitive to outliers, and llsss is a better alternative to identify and reject large-and-spant sparse noise.
Later, we will show that simple sub-gradient method converges to this balanced solution. To smoothen (z|, we replace it with Vr² + for e = 10-7
3 Here, for simplicity we assume pm is integer.
3

---

A solution w is called global if it corresponds to global minimizer of L(w). Moreover, a local solution w corresponds to the minimum of [(w) within an open ball centered at Finally, tree solution w satisfies Wi ④ ... wN 0*
3 Main Results
3.1 Absence Benign Landscape
We show that for any arbitrary corruption probability 0 < < 1/2 and any number of layers N 2 1, there exists least one true solution with a strictly negative descent direction, provided that the problem is pver-parumeterized, i.e., m. S d.
Theorem 1 (unidentifiable true solutions). Define W = {w: : w1 C ....... . WN = 8r as the set of all true solutions of N -laayer model. For any N 2 1 and 0 < 1/2, the following statements hold:
(Over--prrameterized regime) If m S 0.1dd with probability of at least 1/16, we have
inf EWW willw- woww-wllggs Sy {L(w) L(w")} 2 -PoPY,
inf
(2)
for any 7 S lo-
-(Under-paraametritzed regime) 1f (1-2p)2. with probability of least 1 -9((d) we have
inf inf (f(w) - L(w*)) 0. W.EW
(3)
The above proposition unravels a sharp transition in the landscape of robust linear regression with an N-layer model: when m S d, some of the true solutions are likely to be non-critical points, and hence, cannot be recovered via any first-order algorithm. As soon as m Z d, true solutions become global. This is in stark contrast with the recent results the benign landscape of robust low-rank matrix recovery with filloss, which show that, under the so-called restricted isometry property (RIP), all the true solutions are global and vice versa 26 p 1o The vector version of RIP is known to hold with (((k) samples (see e.g. B for simple proof). Theorem 1 shows that, unlike the low-rank matrix recovery, RIP not enough to guarantee the equivalence between the true and global solutions in deep linear models.
The detailed proof of this theorem can found Appendix Cal Here, we provide a proof sketch for N = 1 and N = 2 to elucidate the key ideas.
Proof sketch of Theorem For 1-layer model, the set of true solutions W reduces singleton {0*}. Upon choosing C(0*) L(0" A0)
8*, we prove the existence of a perturbation || S y that satisfies
O. The perturbed loss takes the following form
C (0 + +10)
Σ (AA,
Σ iES
KA0,x;)
m
iES
Consider the following feasibility problem:
find s.t. (a,x,) = = Vi (a,x;)= Vi S.
Since m S and {z. are i.i.d. standard Gaussian vectors, they are linearly independent almost surely. Moreover, with high probability, at least one of e,'s will be nonzero. Therefore, with high probability, the above system of linear equations has at least one nonzero feasible solution. Suppose that & # 0 is one such solution. Define ÅO 7ā/ ||ق||| for some 0 < 7 ||ā||. One can write
C L(O + A0) 1
Σ
Jeal < (0*), YES
|
implying that A is indeed a descent direction. Now, consider a 2-layer model. It easy to verify the existence of true solution perturbation of the form Aw = (0, Awz). One can write
(W1, (2) such that wi ur 0* and ||willo lo d. Consider
1 Σ
((w O Aw2, 1 Σ
L (w Aww
(wi @ Aw2, -eil
iE8

---

Since wi is devoid of zero elements, there exists a nonzero Awy such that w1 @ Awy 70/ ||ā|| for Y ||a Arguments analogous to llaayer model can then be invoked to show that the constructed
perturbation is indeed a descent direction. A similar idea can be naturally extended to N 2 3. M
Theorem implies that, despite their convexity, 1-layer models
suitable for the robust linear regression since the set of true solutions (which is a singleton W {6r }) is unidentifiable. However, despite the existence of unidentifiable true solutions in N-layer models with N 2, we will show that a simple SubGM converges to a balanced true solution, even if an arbitrarily large fraction of the measurements are corrupted with arbitrarily large noise values. This further sheds light on the desirable landscape of deeper models in the context of linear regression.
Algorithm 1 Sub-gradient Method
Input: Data points (())))));=) number of iterations T, the initial point Was and the step-size (n/"))=
Output: Solution (T)
for / < T do
Select direction ( from the sub-differential (9) defined as:
0m, ((w)= = 1 m
Σ
Sign
II
Wk: F3
x 3 Wx:
(4)
m j=1
k
Set w ((-1) w(t) - (1)0
end for
3.2 Convergence of Sub-gradient Method
At every iteration i, SubGM selects a direction ( from the sub-differential of the fllsoss (defined as 4., and updates the solution w(++1) w(f) d(;; see Algorithm D for details. Our next two theorems characterize the performance of SubGM with small initialization on N-layer models. We consider the cases N 2 and N 2 3 separately, as SubGM behaves differently on these models. We define = m 1 as the condition number, where 0 and 6i... are the maximum and minimum nonzero elements of 8", respectively.
Theorem 2 (2-layer model). Consider the iterations of SubGM {w(O)/ TT applied to L(w) with N and step-size S 1. Suppose that the initial point satisfies w/)) = ((Val) j = 1,2, where log"(m) (m) log(d) log([10" Then, the following (1-p)²
0 < a S dmm/k. k. Moreover, suppose that m 2 k3 log"
statements hold with probability of -Ce -(()),
Convergence guarantee: After "
1 log (2) ST < k2/2 log (1) iterations, we have
8* I n max VoLma 1- (m=mp)m
we have Balanced property: For every 0 s t T,
[ (t)
S a
0.5-6
Vi
Long escape time: For every T <ts
m(1-p) T,
m(
we have
| ow (4) 0+ S 1n10max max
V Vi
Via pm 0.5-
Furthermore, if m 2 dllo(m)/(4 p)², with probability of 111-Ce Ce Ce-((()) and every t 2 T, we
have
|10 @ whth 00| x "0 VVdema 1-6
Vmill ws3 (1 (1-22 (nNd)) 4-8
5

---

We provide the main idea behind the proof of Theorem 2 in Section 4 The formal proof can be found in the appendix. A few observations are in order based on Theorem 2
First, for any = >> 0, SubGM is guaranteed to satisfy |uof') Ow?" - S after (((1/) log (d/e)) iterations, provided that
? (e)) and =² mm) Based our numerical results (provided in the appendix), we believe that it is possible to establish a linear convergence for SubGM with a geometric step-size; a rigorous verification of this conjecture is considered future work. Second, although SubGM converges to vicinity of a true solution quickly, will stay there for a significantly longer time-in particular,
/m([1 p)² times longer than its initial convergence time. Such behavior is also exemplified in our simulations (see Figure le). After this escape time, the algorithm may slowly converge to an overfitted solution with a better training loss. Moreover, if m Z d, SubGM will continuously converge to true solution at an exponential rate, and will never diverge. Finally, Theorem 2 shows that SubGM implicitly favors balanced solutions, i.e. solutions whose factors have similar magnitudes. Combined with the convergence result of SubGM, we immediately conclude that SubGM converges particular solution of the form (v8*, vB*). Therefore, the solution found by SubGM will enjoy the same (approximate) sparsity pattern as 0*
Theorem 3 -N-layer models). Consider the iterations of SubGM {To applied to L(w) with N 2 3 and step-size 1) S ~~ Suppose that the initial point satisfies w/) ((a2/N1) 1), where 0 < a S dm/k. Moreover, suppose that m 2 following statements hold with probability of - Ce -(()))
"N².
Rxx log" (m) log(d) logi I1/a). Then, the
(p=))²
2as2 <TS
Convergence guarantee: After
Nn a
x
Ny
N iterations, we have
(T) W
8r S Nnfmax Vddma
Balanced property: For every 0 S T. we have
1 w jí
(t)
(t)
0 (a!/N).
forlsi<j 0,
(() (0)
Ö (00 1/0ivh3 /13/m))
firlsi< N, 0f # 0.
Long escape time: For every T sts
m(1 m(1-p)2 T. we have
k
(t) w
gr
S NN V VdPma
Furthermore, if m 2 d 2 log(m)/(1 - p)2, with probability of at least 1 - Ge -((k) and for every t t> T, we have
8r S SNno v v ( Vdd (t (1-T)+1
Jdma
N
The proof of this theorem can be found in the appendix. Theorem B sheds light on an important benefit of N-layer models with N 2 3 compared to 2-layer models: for sufficiently small step-
size, deeper models improve the generalization error by a factor of (1/a) ((1²/ ((12//(( V(0 m()) This improvement is particularly significant when both a and m are small. However, such improvement comes at the expense of a slower convergence rate. In particular, after setting r = ((e/N), and
= e/= SubGM needs O (11/)) 1+ N=2 iterations obtain e-accurate solution. Evidently,
the convergence rate deteriorates with N. ultimately approaching O (1/=²) for infinitely deep models. This can be observed in practice: Figures I and show that 3-layer model enjoys better generalization error compared to 2-leyer model, but suffers from a slower convergence rate. This slower convergence rate also manifests itself in a more stable behavior of the algorithm: for deeper models, SubGM stays close to the ground truth for a longer time. Finally, the balanced property of the solution obtained via SubGM extends to N N-layer models. In particular, SubGM converges to particular solution of the form V0-,.... (@*), thereby inheriting the same sparsity pattern as 0*.

---

3.3 Local Landscape Around Balanced Solution
In the previous section, we showed that SubGM converges to a balanced solution. In this section, we characterize the local landscape around this balanced solution, proving that it becomes flatter for deeper models.
Theorem 4 (flatness around balanced solution). Suppose that l klog(d)/11 -2p)² E m I 0.1d and 1/2. Let w" = ( (Vor..... V0r). Then, for any N 2 2 and S to/vd / A 1. the following
statements hold:
With probability at least
C EDD(),, we have
inf w:llw- aallwwwwlla.5 Sy
{L(w*) - L L(w)]
/m y% yp
With probability at least 1/16, we have
([(w") - L ((w)) Pop d w://w-w Il ST
inf
m
Theorem 4 shows that, within a y-neighborthood of w", the most descent direction from w can reduce the loss by at most O (d/ fm . >))). which decreases exponentially with N. Moreover, in the noisy setting, the above theorem implies that w* likely to be neither local nor global minimum since it has a descent direction. However, the flatness of the landscape around w enables SubGM to stay close to the balanced solution for long time.
Remark 1. Note that the choice of to -ball for the perturbation set is to ensure that the size of the possible perturbutions per layer remains independent of the depth of the model. This is indeed crucial to ensure fair comparison between models with different depths: alternative choices of the perturbation set, such as ly ba-ball with 1 S q < oo (e.g. Ez-ball) would shrink the size of the feasible per-layer perturbations with N, thereby leading to an unfair advantage to deeper models.
4 Proof Techniques
At the crux of our proof technique for Theorems and 3 lies the following decomposition of the sub-differential:
dl(w)= = & 5.C(w) + (
for some strictly positive &.
expected subdiiff.
subdiff. deviation
In the above decomposition, L(w) is called expected loss, and is defined as [(w) = I[l ... WN 11 As will be shown later, Z(w) captures the expected behavior of the empir- ical loss L(w). To analyze the behavior of SubGM on L(w), we first consider the ideal scenario, where L(w) coincides with its expectation. Then, we extend our analysis to the general case by controlling the aab-differentia deviation. In particular, we show that the desirable convergence properties of SubGM extends to L(w), provided that its sub-differentials
"direction-preservinng i.e. d 2 çd, for every d E (.(w), d E aL(w) and some ç > 0. To formalize this idea, we first provide concise characterization of AL(w):
9 UK o E EE
II
II wkk ( k
where Q(:)
1 Σ Sign ((x1, 2) + Ei) ae. T=1
Definition (approximately sparse vectors). We say a vector u E Rd is (k, apapproxxiittt sparse there exists a vector u, such that ||u|lo I le and u|u -il S
Proposition 1 (direction-preseeviing preserving property). Suppose that m Z klog"(mm) log( for some (1-p)"8"
R, 0,,88 0. Then, with probability of at least 1 Ce-R(m8) the following inequality holds for any q E Q(2) and any (ke 0) -approximately sparse vector that satisfies /dm/ K- log (1/0) S ||||| S R:
(1
p. le- =(21==111]
2
<
8.
(5)
|||||
Moreover, if dllg(m) (1- with probability of Ce P
holds for every E Rd.
7

---

Proposition[]
is is analogous to Sign-RIP condition introduced in 20 23 for the robust low-rank matrix
recovery, and is the heart of our proofs for Theorems 2 and 3
Suppose that #* -Il wy is (max; {Tleys Wx) 8,
(k, ()) approximmatl sparse and satisfies S Then, we have ||d م|ا s
which in turn provides upper bound on the sub-differential deviation.
4.1 Proof Sketch of Theorem
To streamline the presentation, here we only provide simplified versions of our key ideas, which inevitably lead to looser guarantees. To streamline the proof, we assume that 01 2 ... 2 0% >
02 0z O. Moreover, for simplicity of notation, we denote w and u w2-
Consider the following decomposition:
u B e = U101 Ug 1K++UU++1 Uaud
(6)
The vectors S and E are called signal and residual terms, respectively. Evidently, we have u u = 6" if and only if S [8r..... .......,66 0%] and E Based on this observation, our goal is show that the signal term converges ........ 0t1 exponentially fast, while the error term remains small throughout the solution trajectory.
Lemma 1 (signal dynamic; informal), Suppose that holds for = 0 u(t) @ (t)), and Then, we have
00- (t) @ |l
Z 1 |10*1|
u ( ((+1) 2 1-21
07 u, 2
(1) (4)
+ 8,
))
u, (
(1)
[u(tt) o vl)) 0-
for some [6:] S 5 and every i= I....,k. Lemma 2 (residual dynamic; informal), Suppose that |0- (+) @ (t|l|| 2 1 ||0"]. Then, we have
5 holds for = 0" (((() o v(0) and
u4 (1(+1))=
- o
( s5--
(1))))))))))))))))))))))))))))))
(1))))
(8)
for every i = k + I.....dd d Lemma 3 (difference dynamic; informal). Suppose that
5 holds for 2 = 8* (0()) o v(0), and
00- (+) @ oltil| 2 1) ||0'|. Then, we have
u vi (++1) - -uu)0- (1-1
(t+1)
o.!))
11 ((())
0
u U.
(8) (1)
no;
(9)
O v(t)
8-
for some |0a| S 8 and every i = I,...,d. d.
Convergence guarantee. For any fixed i = I...., k. we show that u. (/0000) 01 = 0()) |00*| after (110111000)) log(1/a)) iterations. To see this, suppose that T, is the largest iteration such that
ui (1) (t) < or for every S T,. Moreover, suppose that (| @ u((t] < C' [I0*]] for sufficiently large
C' (this is proven in the appendix). Under these assumptions, reduces to
(1+1) (1+1) >
( + 2(1)
70t
(4) (1) u 0
(10)
|10-1
which implies that T, S |10*11/(10) log(1 (/ax). For any <> T. define (2) = 03 u, write
(1) (t) One can
1 ((+1) < (1)
no |
y (0)
1100
(11)
Hence, with additional O (110*1) [|1001//(0000 (m(01) iterations, we have u. (t),,(() 0 + ( 10 I|. On the other
hand, Lemma 2 implies that, for any ls + I,...,d and S 110 11011/(v000 log(l//) (1/a), have
(1))) a (1(00())))) ( (10!) me(()) - (00kk() (u))) +
8

---

gereritatir
10
10'
157
Eoration
Recation 7
(a) 2-layer matrix recovery
(b) l-yyeer matrix recovery
(c) 4-layer matrix recovery
0.4
pal ins
empitial bis
geravizztie untr
0.4
03
33
Borol 01
(d) 2-layer ReL. network
(c) 3-layer ReLU network
(f) 4-layer ReLU network
Figure 2: Deep matrix recovery (first row). The ground truth X E 20x with rank(X* = 3 chosen randomly. The elements of the measurement matrices are selected from // 1). and the sample size is set to 0.05 with distribution (0, 100). We use SubGM with
= 180. The corruption probability is set step-size 0.001 and Gaussian initialization with an initialization scale (second row). The samples are chosen from y, sin(@" x.) + &, where 8 _ randomly generated with
1 10-a. ReLU models
|| 2. x; ~ (0, Is,), and E, ~ (0, 25) with corruption probability p = 0.05. The sample size set be m 1500. We use SubGM with step-size 0.001 and Gaussian initialization (0, a//N /d).
where K= = /0 is the condition number of 0* Combining the above dynamics, we have Iw
[[0"| - [
In the appendix, we provide more refined analysis that relaxes the dependency of the final error on ó and k.
Long escape time. We show in the appendix that after the first stage, the residual becomes the dominant term in the final error. This together with Lemma implies that, for every S
[|8* log(1/a), we have |E| S V-EevV
n0
Balanced property. We have u. o S or for every E [k], and lu(" S a (l-O(()))) for every h: + 1....,d. d. Therefore, Lemma can be invoked to verify u ((+1) 1/ ((+1) S
(1+ O(5)) uu - _!0| This turn leads to
uu 0 S Va(1+ of
||0-|| not
(t)
S a 0.3 O(V-Okk))))
5 Numerical Experiments: Beyond Linear Regression
In this section, we empirically verify that the benefits of depth extend to the robust variants of deep matrix recovery and ReLU networks with fllsss..
Deep Matrix Recovery. In low-rank matrix recovery, the goal is recover low-rank matrix X E Rddxd from a limited number of noisy measurements of the form yi = (A, X+) + E,. To recover X we consider deep factorized model of the form W, W.... .. WN. where W; E Rd for i == 1...... N, and minimize the folsoss (1/m) 19 1y; (A,. W, W via SubGM. When N 2, the above model reduces to the famous Burer-Monteiro approach [ We assume that 5% of the measurements are grossly corrupted with noise. The first row of Figure 2 shows the performance of SubGMM on 2-, 3-, and 4-layer models. It can seen that the 4-layer model outperforms shallower models, achieving generalization error that is proportional to the step-size.

---

Deep ReLU Network on Synthetic Dataset. As another experiment, we analyze the effect of depth on the performance of SubGM with ReLU networks and lloss. Given an ipput E R the output of an N-layer ReLUU network is defined as /w (w))) = Wx (WN-1 ... (Wix)... ...). where W1 E Rmxxd, W2,... , E I=xx" and WN E I Moreover, axx = max (0,z) is the ReLU activation function. Given the true function f*) = sin sin( z), our goal is to train ReLU model to approximate f* as accurately as possible. To this goal, minimize the -loss (1/m) > 1y: - /w((x)) The second row of Figure 2 illustrates the performance of SubGM. It worth noting that, unlike robust linear regression and deep matrix recovery, there always exists non-diminishing model-mismatch error between the true and considered ReLUU model (shown as a dashed line). Nonetheless, SubGM can achieve this model-mismatch error on 4-layer ReLU model with only 1500 samples, even if 5% of the measurements are corrupted with large noise.
Deep ReLU Network on CIFAR Dataset. We verify that the desirable performance of SubGM with lloss can be extended to its stochastic variant with mini-batches on CIFAR-IO and CIFAR-100 24 outperforming cross-entropy (CE) loss, which is considered as one of the most suitable loss functions for CIFAR datasets. To show this, we use standard ResNet architectures 21 with loss and compare with the cross-entropy loss on noisy CIFAR datasets, where we randomize the labels of 10% of the training dataset. For CIFAR- 100 experiment, we use the "loss scaling" trick introduced in [222. The training details are deferred to Section B33] The best test accuracy for both CIFAR- 10 and CIFAR-100 100 is reported in Table I One can see that fllsoss outperforms cross-entropy loss significantly, demonstrating that our framework may be extended to more realistic settings. Moreover, we do observe that the deeper model performs better CIFAR-100, which aligns with our theoretical result. Based on our simulations, an interesting and important future direction would be to study the optimization landscape of -loss with more general neural network architectures.
CIFAR-10
CIFAR-100
ResNet-18
ResNet-33
ResNet-50
ResNet-18 -8
ResNet-34
ResNet-50
CE loss
91.52% 94.16%
91.53% 93.13%
90.87%
70.17% 73. 14%
71.22% 74.86%
71.30% 76.46%
flssoss
92.68%
Table 1: Test accuracy for ResNets on CIFAR-10 and CIFAR- 100 datasets with 10% label noise.
Conclusion
Modern problems in machine learning are naturally nonconvex but can be solved reasonably well in practice. To explain this, a recent body of work has postulated that many optimization problems in machine learning are "convex-like", i.e., they are devoid of spurious local minima. Our work shows that such global property is too restrictive to hold even in the context of linear regression, and instead propose a more refined trajectory analysis to better capture the landscape of the problem around the solution trajectory. We show that convex models may be fundamentally ill-suited for linear models, and deeper models-despite their nonconvexity-bave provably better optimization landscape around the solution trajectory. Empirically, we show that our analysis may extend beyond linear regression; formal verification of this conjecture is considered an enticing challenge for future research.
Acknowledgements
We thank Richard Y. Zhang, Cédric Jósz, and Tiffany Wu for helpful discussions and feedback. We thank Ruiqi Gao and Jiaye Teng for insightful discussions in the initial phase of this work. We are also thankful to an anonymous reviewer for pointing out the relationship between the perturbation ball and the depth of linear models. This research is supported, in part, by NSF Award DMS-2152776, ONR Award N00014-22-1-212 MICDE Catalyst Grant, MIDAS PODS grant, and Startup funding from the University of Michigan.
10

---

References
[1] Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint arXiv:2001.0444 2020.
[2] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, (2: 32:7413-74424, 2019.
[3] Richard Baraniuk, Mark Davenport, Ronald Vore, and Michael Wakin. A simple proof of the restricted isometry property for random matrices. Constructive Approximation, 28(3):253-22) 2008.
[4] Dimitris Bertsimas, Angela King, and Rahul Mazumder. Best subset selection via a modern optimization lens. The annals of statistics, 44(2):813-855 2016.
[5] Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Global optimality of local search for low rank matrix recovery. arXiv preprint arXiv: 2016.
[6] Peter Bickel, Ya' acov Ritov, and Alexandre B Tsybakov. Simultaneous analysis of lasso and dantzig selector. The Annals of statistics, 37(4):1705 173-17222, 2009.
[7] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael Bernstein, Jeannette Bohg. Antoine Bosselut, Emma Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07255: 2021.
[8] Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming. 95(2):329-33) 2003.
[9] Emmanuel Candes and Terence Tao. The dantzig selector: Statistical estimation when p is much larger than n. The annals of Statistics, 35(6):2313-2333 2007.
[10] Hung-Hsu Hsu Chou, Johannes Maly, and Holger Rauhut. More is less: Inducing sparsity via overparameterization. arXiv preprint /2 1027, 2021.
[11] Damek Davis and Dmitriy Drusvyatskiy. Stochastic subgradient method converges at the rate ok-11/4) on weakly convex functions. arXiv preprint arXiv:/802.00 /802.02988, 2018.
[12] Lijun Ding, Liwei Jiang, Yudong Chen, Qing Qu, and Zhihui Zhu. Rank overspecified robust matrix recovery: Subgradient method and exact recovery. Advances in Neural Information Processing Systems, 34, 2021.
[13] Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks International Conference on Machine Learning, pages 1655-1664. PMLR, 2019.
[14] Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep ho- mogeneous models: Layers automatically balanced. arXiv preprint 2018.
00900,
[15] Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on learning theory, pages 907-940. PMLR, 2016.
[16] Salar Fattahi and Somayeh Sojoudi. Exact guarantees on the absence of spurious local minima for non-negative rank-1 robust principal component analysis. Journal of machine learning research, 2020.
[17] Jerome Friedman, Trevor Hastie, Robert Tibshirani, et al. The elements of statistical learning, volume 1. Springer series statistics New York, 2001.
[18] Daniel Gissin, Shai Shalev-Shwartz, and Amit Daniely. The implicit bias of depth: How incremental learning drives generalization. arXiv preprint arXiv:1909. 12051, 2019.
[19] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent linear convolutional networks. arXiv preprint arXiv:1806.0044 00468, 2018.
11

---

[20] Jeff Z HaoChen, Colin Wei, Jason Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. In Conference on Learning Theory, pages 2315-2357. PMLR, 2021.
[21] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[22] Like Hui and Mikhail Belkin, Evaluation of neural architectures trained with square loss vs cross-entropy in classification tasks. In International Conference on Learning Representations, 2020.
[23] Kenji Kawaguchi. Deep learning without poor local minima. arXiv preprint arXiv: 105.01160,.,7110, 2016.
[24] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[25] Jiangyuan Li, Thanh Nguyen, Chinmay Hegde, and Ka Wai Wong. Implicit sparse regularization: The impact of depth and early stopping. Advances in Neural Information Processing Systems, 34, 2021.
[26] Xiao Li, Zhihui Zhu, Anthony Man-Cho So, and Rene Vidal. Nonconvex robust low-rank matrix recovery. SIAM Journal on Optimization,
686, 2020.
[27] Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. arXiv preprint 20X99990/2.09839 2020.
[28] Jianhao Ma and Salar Fattahi. Sign-rip: A robust restricted isometry property for low-rank matrix recovery. arXiv preprint arXiv:2102.02966 2021.
[29] Jianhao Ma and Salar Fattahi. Global convergence of sub- uub-gradient method for robust matrix recovery: Small initialization, noisy measurements, and over-parameterization. arXiv preprint arXiv:2202.08788, 2022.
[30] Rahul Mazumder, Peter Radchenko, and Antoine Dedieu. Subset selection with shrinkage: Sparse linear modeling when the snr is low. arXiv preprint (iXXiv1708.032288 2017.
[31] Roman Novak, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl- Dickstein. Sensitivity and generalization in neural networks: an empirical study. arXiv preprint 1rXiv:1802.087600 2018
[32] Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Minimax rates of estimation for high-dimensional linear regression over by-balls. IEEE transactions information theory, 57(10):6976-6994, 2011.
[33] Itay Safran and Jason D Lee. Optimization-based separations for neural networks. arXiv preprint arXiv:21 2021.
[34] Matus Telgarsky. Representation benefits of deep feedforward networks. arXiv preprint arXiv:1509.08001, 2015.
[35] Matus Telgarsky. Benefits of depth neural networks. In Conference on learning theory, pages 1517-1539. PMIR,, 2016.
[36] Sara Van de Geer. The deterministic lasso. Seminar für Statistik, Eidgenössische Technische Hochschule (ETH) Zürich, 2007.
[37] Aad W Van Der Vaart, Adrianus Willem van der Vaart, Aad van der Vaart, and Jon Wellner. Weak convergence and empirical processes: with applications statistics. Springer Science & Business Media, 1996.
[38] Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. Advances in Neural Information Processing Systems, 32:2972-2983, 2019.
12

---

[39] Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[40] Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages
PMLR, 2020.
[41] Peng Zhao, Yun Yang, and Qiao-Chu He. Implicit regularization via hadamard product over- parametrization in high-dimensional linear regression. arXiv preprint arXiv: 193.:9990 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of theoretical results? [Yes] The complete proofs are provided in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [No] We provided all
the details for our experiments to be reproducible.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] The details are provided in the appendix.
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "qol0TUVnHW", "reviewer": "Reviewer_x9hu", "summary": "This paper studies an interesting problem called \"grossly corrupted linear model\", where the ground truth is a linear model and a portion of output samples corrupted with noises with considerable variances. A diagonal linear network with depth N is used to learn the model, and the authors prove/propose several interesting results:\n1) There exist parameters that correspond to the ground truth, but are neither local-min nor global-min.\n2) The authors propose a sub-gradient optimization method, termed SubGM, that provably converges to the ground truth solution.\n3) The deeper models have relatively better landscape around the ground truth solution. As the depth grows, SubGM indeed is more likely to converge to the ground truth solution.\n\nEmpirical results show that SubGM also works well on matrix recovery and Cifa-10 classification (with deep ReLU networks), and phenomenon 3) is also observed in these two problems.\n", "questions": "1. In the abstract, t would be better to mention that this paper only considers diagonal linear networks. I am not aware of this until I read Section 1.1.\n2. The experiments on ReLU networks did not rule out the effect of representation power. In particular, the better performance of deeper models may be (partially) due to the stronger expressivity.\n3. I feel \"bless of depth\" suits the title better. Once N>1, the model is no longer convex, but increasing depth still improves the performance of SubGM.", "limitations": "The author may want to discuss how to extend the results to realistic neural-net settings. So far the results are limited to diagonal linear models which are not commonly used in practice. I am curious about the main challenge of applying a similar analysis to fully-connected linear networks or a non-linear DNN.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**: \n\nThe paper is clearly presented. It was believed that for neural networks, the depth increases the expressivity power, while the width helps optimization [1]. If we want to train very deep networks (say, more than 50 layers), certain tricks like skip connections and normalization must be applied. This paper, as far as I am concerned, provides a somewhat surprising insight: depth can also benefit the optimization landscape. With a proper learning algorithm, increasing the depth helps the optimization and the recovery of the ground truth. \n\nThis paper studies the landscape from some novel angles: \n- (a) The solution we want (ground truth) is not necessarily a local-min or a global-min\n- (b) Given (a), analyzing the local landscape around the solution we want, instead of the landscape around the global-min, can better help the optimization.\n\nThe paper establishes the theories based on the above ideas. It showed that the ground truth of the grossly corrupted linear model may not be the global-min of the optimization problem. Subsequently, it provides a landscape analysis to show that depth \"smooths\" the landscape around the ground truth solution. Then, it proposes an effective algorithm to recover the ground truth, with a convergence proof for any depth N≥2. Although the theory is not on neural-net settings, the experiments demonstrate that similar results can be observed in matrix recovery and image classification with neural networks.\n\nOverall, this is a nice paper. It clearly sheds light on the optimization study of machine learning.\n\n**Weakness**\n\nThe main weakness is that the diagonal linear models are not commonly used in practice. To me, it is a simplification of deep linear neural networks, which in turn is a simplification of fully-connected non-linear DNN. It is not clear whether the main theoretical conclusion (depth flattens the local landscape around the ground truth solution) still holds for practical settings.\n\n[1] Sun et. al., The Global Landscape of Neural Networks: An Overview, arXiv:2007.01429.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "otI8DLHeM7", "reviewer": "Reviewer_kMm7", "summary": "This paper studies the problem of robust and sparse linear regression under an over-parameterized setting. The authors show that this problem does not have a benign landscape. But for any N-layer model with $N \\ge 2$, a simple sub-gradient with small initialization will converge to a small neighborhood of a balanced true solution, the algorithm will stay close to the ground truth for a longer time, and depth flattens the optimization landscape around the solution obtained by SubGM.", "questions": "What is the reference [42] in Appendix A? I think the authors should carefully the references.\n\nConsidering the similar setting but noiseless data, what would the results be?", "limitations": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe paper studies an interesting question related to the over-parameterized problem. In particular, the authors show interesting and important findings that deeper models have provably better optimization landscape around the solution trajectory.\n\nPaper is written well.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OjyF9Sxa2OB", "reviewer": "Reviewer_9hKR", "summary": "The paper studies the training dynamics of deep linear regression models. Specifically, it explores the effect of depth on the loss landscape of robust deep linear models. The results are mainly in two aspects: First, there is a phase transition in the loss landscape of the robust linear regression problem: when the dimension of the feature is much larger than the number of data samples, there exists a true solution that is not a critical point of the $\\ell_1$-loss; otherwise, all true solutions are global minima. Second, sub-gradient methods converge to a global minimum that is close to the true solution, and moreover, depth slows down the training rate but improves the generalization error.", "questions": "1. It seems that the feasible region of $m$ in Theorem 1 and Theorem 2 intersects. Does that mean that subgradient methods will find a solution that has exactly $O(d)$ loss?\n\n2. Is there any result showing that training rate and generalization error is directly correlated with the depth $N$?\n\n3. In Line 174, it is mentioned that the improvement is significant if $m$ is small. How large is this $m$? It seems that by the assumption in Theorem 3, $m$ is not that small.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is technically sound. The characterization of the phase transition in the landscape of deep linear models looks interesting, especially as RIP does not work in this case. The technique of the analysis may also be potentially applied to other settings.\n\nI am a bit confused about the main information this paper wants to convey. In my humble opinion, the main information is that: for robust deep linear models, some true solutions may not be obtained by first-order methods, but sub-gradient method obtains a solution that is close enough. This information is not that related to the depth. The information related to depth is: depth flattens the local landscape around the true solution, slows down the training rate and improves the generalization error. The latter two points are obtained by comparing the results of two-layer and (more-than-)three-layer networks, which seems a little strange: it does not claim that adding depth after depth exceeds three still improves the generalization error, so I'm not sure whether depth plays a role here.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9eKOmK3htW_", "reviewer": "Reviewer_ffkC", "summary": "The paper discusses the relation between the optimization landscape around the true solution and the depth of deep neural networks. They theoretically prove that a simple sub-gradient method (SubGM) converges to a neighborhood of the balanced true solution whose radius is determined by the depth N of the model via an N-layer linear neural network with noise. They also experimentally verify their conclusion on ResNet of CIFAR-10.\n\n**post-rebuttal**\n\nThe rebuttal answers most of my questions and I decide to change my score. But I think the author should claim that the focus on diagonal linear model in the main boy to avoid confusion.", "questions": "Same as the Weakness.", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work", "rating": 5, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Theoretically prove the relation between optimization landscape/generalization error and the depth of the neural network.\n\nWeakness:\n1. A little bit curious about the statement \"deeper models generalize better\" in line 18. In my understanding, the too deep model will cause the problem of overfitting, especially without the residual block. Could the author explain this statement?\n\n2. The structure of the linear neural network seems to be incorrect. The author uses the Hadamard product when defining the N-layer linear neural network. Take 2-layer linear network and $x\\in\\mathbb{R}^2$ as an example. The output of the network is defined as $y=<w_1⊙w_2 ,x>= w_{11}w_{21}x_1+w_{12}w_{22}x_2$. So here comes the problem: what is the number of neurons in the hidden layer? The structure of the linear model that the proof of the whole paper based on is really strange and I am curious whether the conclusion drawn in the paper is correct.\n\n3. The author only considers the linear network without the activation function. However, the nonlinear activation function is quite important in deep learning to enhance the expression ability of models in more general and sophisticated application scenarios. I am curious does the performance of deep learning models consists with the theory proven on the linear models? The author only provides the generalization error performance on 2-4 layers simple neural network and I don't think it is convincing enough. In appendix B.3, I only find the test and train accuracy of Resnets and do not find the generalization error performance of Resnets. I think the author should do more experimental research.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5F2xrc8FjAg", "reviewer": "Reviewer_vNfZ", "summary": "This paper considers the implicit bias of the deep (diag) linear model. The previous analysis need the loss to be a l2 loss. In this paper, the author consider a robust statistic model where l1 loss should be applied. by ananlysising the landscape around the true solution, The author discovered that the true solutions are likely to be non-critical points under the one-layer convex parameterization, but have a good local property when multilayer nonconvex parameterization is applied.", "questions": "- The author can provide more proof initution in the main text. In the main text, the convergence result of the population dynamic and how the initialization scaling changes the stability result is missing. (I'm also curious about it)\n- Can you compare the results when the network becomes deeper? It's a trade off or deeper is better?", "limitations": "No", "rating": 9, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is quite interesting and I strongly recommend to accept. The proof technique is also new to me. The results include converging of the sub-gradient method and long escape time after arrived the balanced solution. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept