ResNEsts and DenseNEsts: Block-based DNN Models with Improved Representation Guarantees
Authors: Kuan-Lin Chen
Ching-Hua Lee
Harinath Garudadri
Bhaskar D Rao
Venue: NeurIPS 2021 Poster (2021)
Keywords: optimization
local minima
residual networks
densely connected networks
nonlinear estimation

Abstract: Models recently used in the literature proving residual networks (ResNets) are better than linear predictors are actually different from standard ResNets that have been widely used in computer vision. In addition to the assumptions such as scalar-valued output or single residual block, the models fundamentally considered in the literature have no nonlinearities at the final residual representation that feeds into the final affine layer. To codify such a difference in nonlinearities and reveal a linear estimation property, we define ResNEsts, i.e., Residual Nonlinear Estimators, by simply dropping nonlinearities at the last residual representation from standard ResNets. We show that wide ResNEsts with bottleneck blocks can always guarantee a very desirable training property that standard ResNets aim to achieve, i.e., adding more blocks does not decrease performance given the same set of basis elements. To prove that, we first recognize ResNEsts are basis function models that are limited by a coupling problem in basis learning and linear prediction. Then, to decouple prediction weights from basis learning, we construct a special architecture termed augmented ResNEst (A-ResNEst) that always guarantees no worse performance with the addition of a block. As a result, such an A-ResNEst establishes empirical risk lower bounds for a ResNEst using corresponding bases. Our results demonstrate ResNEsts indeed have a problem of diminishing feature reuse; however, it can be avoided by sufficiently expanding or widening the input space, leading to the above-mentioned desirable property. Inspired by the densely connected networks (DenseNets) that have been shown to outperform ResNets, we also propose a corresponding new model called Densely connected Nonlinear Estimator (DenseNEst). We show that any DenseNEst can be represented as a wide ResNEst with bottleneck blocks. Unlike ResNEsts, DenseNEsts exhibit the desirable property without any special architectural re-design.

ResNEsts and DenseNEsts: Block-based DNN Models with Improved Representation Guarantees
Kuan-Lin Chen', Ching-Hua Lee', Harinath Garudadri', and Bhaskar D. Rao
DDparrment of Electrical and Computer Engineering, ?Qualcomm Institute University of California, San Diego
La Jolla, CA 92093, USA
(kuc029, ch1438, here1443,.grruuddaaa hgwrudddri.i brao @ucsd.edu
Abstract
Models recently used in the literature proving residual networks (ResNets) are better than linear predictors are actually different from standard ResNets that have been widely used in computer vision. In addition to the assumptions such scalar-valued output or single residual block, the models fundamentally considered in the literature have no nonlinearities at the final residual representation that feeds into the final affine layer. To codify such difference in nonlincarities and reveal linear estimation property, define ResNEsts, i.c., Residual Nonlinear Estimators, by simply dropping nonlinearitics at the last residual representation from standard ResNets. We show that wide ResNEsts with bottleneck blocks can always guarantee a very desirable training property that standard ResNets aim to achieve, i.e., adding more blocks does not decrease performance given the same set of basis elements. To prove that, we first recognize ResNEsts are basis function models that are limited by coupling problem in basis learning and linear prediction. Then, to decouple prediction weights from basis learning, we construct a special architecture termed augmented ResNEst (A- (A-ResNEst) that always guarantees worse performance with the addition of a block. As result, such an A- A-ResNEst establishes empirical risk lower bounds for a ResNEst using corresponding bases. Our results demonstrate ResNEsts indeed have problem of diminishing feature reuse; however, it can be avoided by sufficiently expanding widening the input space, leading to the menee-ment desirable property. Inspired by the densely connected networks (DenseNets) that have been shown outperform ResNets, we also propose corresponding new model called Densely connected Nonlinear Estimator (DenseNEst). We show that any DenseNEst can be represented as a wide ResNEst with bottleneck blocks. Unlike ResNEsts, DenseNEsts exhibit the desirable property without any special architectural re-design.
1 Introduction
Constructing deep neural network (DNN) models by stacking layers unlocks the field of deep learning,
leading to the early success in computer vision, such Netx Krizhevsky et al. 2012). Z.FNet
[Zeiler and Fergus, 2014), and VGG (Simonyan and Zisserman,
2015). However, stacking more
and more layers can suffer from worse performance [He and Sun 2015
Srivastava et al. 2015 He
(et al. [216aa]: thus, it is no longer a valid option to further improve DNN models. In fact. such degradation problem is not caused by overfitting, but worse training performance [He al.) 2016a] When neural networks become sufficiently deep, optimization landscapes quickly transition from being nearly convex to being highly chaotic [Li et al.) 2018). As result, stacking more and more layers in DNN models can easily converge to poor local minima (see Figure [He et al. 2016a]).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Ho
H1
H
H
H₂
W
G2 V2
1-1
1-1
V1
X
Wo
G2.
XL-2
XL-1
Figure 1: The proposed augmented ResNEst or A-ResNEst. A set of new prediction weights Hg, H,.... H are introduced on top the features in the ResNEst (see Zi. The A-ResNEst is always better than the ResNEst in terms of empirical risk minimization (see Proposition 2 Empirical results of the A-ResNEsst model are deferred to Appendix B in the supplementary material.
To address the issue above, the modern deep learning paradigm has shifted to designing DNN models based on blocks or modules of the same kind in cascade. A block or module comprises specific operations a stack of layers to avoid the degradation problem and learn better representations.
For example. Inception modules in the GoogLeNet [Szegedy et al. 2015). residual blocks in the
ResNet [He et al. 20 Zagoruyko and Komodakis [016,] Kim et al. 2016 Xie et al. 2017
Xiong et al. 2018 dense blocks in the DenseNet Huang et al. 2017]. attention modules in the Transformer Vaswani et al., 2017], Sgguezz-anndExcitaaii
(SE) blocks in the SE network (SENet) Hu et al. 2018 and residual U-blocks [Qin et al. 2020) in -2-Net. Among the above examples, the most populan lr block design is the residual block which merely adds skip connection (or residual connection) between the input and output of a stack of layers. This modification has led to huge success in deep learning. Many modern DNN models in different applications also adopt residual blocks in their architectures, e.g., V-Net in medical image segmentation (Milletari et al., 2016), Transformer in machine translation [Vaswani et al., 2017 and residual LSTM in speech recognition (Kim et al. 2017]. Empirical results have shown that ResNets can be even scaled up to 1001 layers or 333 bottleneck residual blocks, and still improve performance [He et al. 2016b].
Despite the huge success, our understanding of ResNets is very limited. To the best of our knowledge, no theoretical results have addressed the following question: Is learning better ResNets as easy as stacking more blocks? The most recognized intuitive answer for the above question is that a particular stack of layers can focus on fitting the residual between the target and the representation generated in the previous residual block; thus, adding more blocks always leads to no worse training performance. Such an intuition is indeed true for constructively blockwise training procedure; but not clear when the weights in a ResNet are optimized as a whole. Perhaps the theoretical works in the literature closest to the above question are recent results in an albeit modified and constrained ResNet model that every local minimum is less than or equal to the empirical risk provided by the best linear predictor [Shamir 2018 Kawaguchi and Bengio 2019 Yun et al. 2019]. Although the aims of these works are different from our question, they actually prove special case under these simplified models in which the final residual representation better than the input representation for linear prediction. We notice that the models considered in these works are very different from standard ResNets using pre-activation residual blocks (He et al. (016b) due to the absence of the nonlinearities at the final residual representation that feeds into the final affine layer. Other noticeable simplifications include scalar-valued output [Shamir] 2018 Yun et al. 2019) and single residual block Shamir 2018 Kawaguchi and Bengio 2019]. In particular, Yun et al. [2019] additionally showed that residual representations do not necessarily improve monotonically over subsequent blocks, which highlights a fundamental difficulty in analyzing their simplified ResNet models.
In this paper, we take a step towards answering the above-mennionee question by constructing practical and analyzable block-based DNN models. Main contributions of our paper are as follows:
Improved representation guarantees for wide ResNEsts with bottleneck residual blocks. We define a ResNEst as a standard single-stage ResNet that simply drops the nonlinearities at the last residual representation (see Figure 2 We prove that sufficiently wide ResNEstt with bottleneck residual blocks under practical assumptions can always guarantee a desirable training property that ResNets with bottleneck residual blocks empirically achieve (but theoretically difficult to prove), i... adding more blocks does not decrease performance given the same arbitrarily selected basis.

---

To be more specific, any local minimum obtained from ResNEsts has an improved representation guarantee under practical assumptions (see Remark 2 (a) and Corollary D. Our results apply to loss functions that are differentiable and convex; and do not rely on any assumptions regarding datasets, or convexitydiiferrnntablltt of the residual functions.
Basic vs. bottleneck. In the original ResNet paper, [e et al.] [0066a] empirically pointed out that ResNets with basic residual blocks indeed gain accuracy from increased depth, but are not as economical as the ResNets with bottleneck residual blocks (see Figure in (Zagoruyko and Komodakis 2016) for different block types). Our Theorem supports such empirical findings.
Generalized and analyzable DNN models. ResNEsts are more general than the models considered in (Hardt and Ma. 2017 [Shamir 2018 Kawaguchi and Bengio, 2019 Yun et al., 2019] due to the removal of their simplified ResNet settings. In addition, the ResNEst modifies the input by an expansion layer that expands the input space. Such an expansion turns out to be crucial in deriving theoretical guarantees for improved residual representations. We find that the importance on expanding the input space in standard ResNets with bottleneck residual blocks has not been well recognized in existing theoretical results in the literature.
Restricted basis function models. We reveal linear relationship between the output of the ResNEst and the input feature as well as the feature vector going into the last affine layer in each of residual functions. By treating each of feature vectors basis element, we find that ResNEsts basis function models handicapped by a coupling problem in basis learning and linear prediction that can limit performance.
Augmented ResNEsts. As shown in Figure 1 we present special architecture called augmented ResNEst or A- A-ResNEst that introduces a new weight matrix on each of feature vectors to solve the coupling problem that exists in ResNEsts. Due such a decoupling, every local minimum obtained from an A-ResNEst bounds the empirical risk of the associated ResNEst from below. A-ResNEsts also directly enable to see how features supposed to be learned. It is necessary for features to be linearly unpredictable if residual representations are strictly improved over blocks.
Wide ResNEsts with bottleneck residual blocks do not suffer from saddle points. At every saddle point obtained from a ResNEst, show that there exists at least one direction with strictly negative curvature, under the same assumptions used in the improved representation guarantee, along with the specification of squared loss and suitable assumptions the last feature and dataset.
Improved representation guarantees for DenseNEsts. Although DenseNets [Huang al. 2017 have shown better empirical performance than ResNets, we are not aware of any theoretical support for DenseNets. We define DenseNEst (see Figure 4 as a simplified DenseNet model that only utilizes the dense connectivity of the DenseNet model, i.e., direct connections from every stack of layers all subsequent stacks of layers. We show that any DenseNEst can be represented as a wide ResNEst with bottleneck residual blocks equipped with orthogonalities. Unlike ResNEsts, any DenseNEst exhibits the desirable property, i.e., adding more dense blocks does not decrease performance, without any special architectural re-design. Compared to A- A-ResNEsts, the way the features are generated in DenseNEsts makes linear predictability even more unlikely, suggesting better feature construction.
2 ResNEsts and augmented ResNEsts
In this section, we describe the proposed DNN models. These models and their new insights are preliminaries to our main results in Section Section 2. recognnis the importance of the expansion layer and defines the ResNEst model. Section points out the basis function modeling interpretation and the coupling problem in ResNEsts, and shows that the optimization on the set of prediction weights is non-convex. Section 2.3 proposes the A-ResNEst to avoid the coupling problem and shows that the minimum empirical risk obtained from a ResNEst is bounded from below by the corresponding A-ResNEst. Section 2.4 shows that linearly unpredictable features are necessary for strictly improved residual representations in A- NeEts.
3

---

Wi
W2
W
Naulimu
W 2eo
VZ
Wo
W L+1
y yReNTe
Vo
XiI
X1
XL-1
Figure A generic vector-valued ResNEst that has chain of I. residual blocks (or units). Redrawing the standard ResNet block diagram in this viewpoint gives considerable new insight. The symbol "+" represents the addition operation. Different from the ResNet architecture using pre-activation residual blocks in the literature [He et al. 2016b), our ResNEst architecture drops nonlinearities at X1, so as to reveal a linear relationship between the output YReSNEs and the features Vo, Vi, Vr. Empirical results of the ResNEst model are deferred to Appendix B in the supplementary material.
2.1 Dropping nonlincarities in the final representation and expanding the input space
The importance on expanding the input space via Wo (see Figure in standard ResNets has not been well recognized in recent theoretical results ([haamir 2018 Kawaguchi and Bengio 2019 Yun et al. 2019]) although standard ResNets always have an expansion implemented by the first layer before the first residual block. Empirical results have even shown that a standard 16-layer wide ResNet outperforms a standard 1001-layer ResNet [Zagoruyko and Komodakis 2016], which implies the importance of a wide expansion of the input space.
We consider the proposed ResNEst model shown in Figure 2 following input-output relationship:
whose i-th residual block employs the
= = W,G, (x,-1;
(1)
for = 1,2..... L. The term excluded the first term X;-1 on the right-hand side is composition of a nonlinear function G, and linear transformation 1 which is generally known as residual function. W, R.M... forms linear transformation and consider G, (x,-1: 0,) R
RK.
function implemented by a neural network with parameters 0, for all E {1,2. ... L}. We define the expansion Xo Wox x for the input E RN... to the ResNEst using linear transformation with a weight matrix Wo E k The output VReSNESI E R. (or LesRNN to indicate L blocks) of
the ResNEst is defined as ý Le-NNN (x) W W++12 where W E R N.N.M. M is the expansion factor and N. is the output dimension of the network. The number of blocks L is a nonnegative integer. When L = 0, the ResNEst is two-layer linear network Yo-ResNEs (x) W Wox.
Notice that the ResNEst we consider this paper (Figure) is more general than the models in (Hardt and Ma 2017 Shamir 2018 Kawaguchi and Bengio 2019 Yun et al.) 2019) because our residual space R dz
(the space where addition is performed at the end of each residual block) not constrained by the input dimension due to the expansion we define. Intuitively, wider expansion (larger M) is required for a ResNEst that has more residual blocks. This because the information collected in the residual representation grows after each block, and the fixed dimension M of the residual representation must be sufficiently large to avoid any loss of information. turns out a wider expansion in ResNEst is crucial in deriving performance guarantees because it assures the quality of local minima and saddle points (see Theorem I and
2.2 Basis function modeling and the coupling problem
The conventional input-output relationship of standard ResNet is not often easy to interpret. We find that redrawing the standard ResNet block diagram (He et al. 2016 bJ with different viewpoint, shown in Figure 2, can give us considerable new insight. As shown in Figure 2 the ResNEst now reveals a linear relationship between the output and the features. With this observation, we can write down a useful input-output relationship for the ResNEst:
y L. ResNEsi (x) = WL (x)
(2)
For any affine function (Xx.) = Ann Xea + b, if desired, one can use y(x) A
b)
X
= Ax
where A [A.. b] and x Xxow and discuss the linear function instead. All the results derived in this paper hold true regardless of the existence of bias parameters.

---

i-1 W 0.) for i 1,2,..., ,L. Note that we do not impose any requirements for each G; other than assuming that it is implemented by neural network with a set of parameters 0,. We define vo = vo(x) = x as the linear feature and regard V1, V2,".", V nonlinear features of the input since G2 is in general nonlinear. The benefit of our formulation (2) is that the output of a ResNEst ý L-ResNEst now can be viewed as a linear function of all these features. Our point of view of ResNEsts in (2) may be useful to explain the finding that ResNets are ensembles of relatively shallow networks [Veit et al. 2016).
where vi (x) G. (x) G. (Eizo
As opposed to traditional nonlinear methods such as basis function modeling (chapter 3 in the book by|Bishop 2006) where a linear function is often trained on set of handcrafted features, the ResNEst jointly finds features and a linear predictor function by solving the empirical risk minimization (ERM) problem denoted as (P) on (Wo.... W 1 01,-... ....................... 0r, fr.). We denote as the empirical risk (will be used later on). Indeed, one can view training ResNEst as basis function modeling with trainable
basis by treating each of features as basis vector (it is reasonable to assume all features are not linearly predictable, see Section 2.4). However, unlike a basis function modeling, the linear predictor function in the ResNEst is not entirely independent of the basis generation process. We call such phenomenon of ResNEsts. To see this, note that feature (basis) vectors V;+1, ... VL can be different W is changed (the product W L+1 W is the linear predictor function for the feature V2). Therefore, the set of parameters Φ = - changed with different linear predictor functions. It follows that W 1++1 and W,, 1, are the only weights which can be adjusted without changing the features. We refer to W,, and W r++1 as prediction weights and & (W, --, 0,)/=1 as feature finding weights in the ResNEst. Obviously, the set of all the weights in the ResNEst is composed of the feature finding weights and prediction weights.
coupling problem which can handicap the performance
0:) 0
needs to be fixed to sufficiently guarantee that the basis is not
Because G, is quite general in the ResNEst, any direct characterization the landscape of ERM problem seems intractable. Thus, we propose to utilize the basis function modeling point of view in the ResNEst and analyze the following ERM problem:
(P&)
min R L. WL+1: WL11
where R (Wr, L. Wi+1i = t EnY E (yh.ReSNTA yx for any fixed feature finding weights Φ. We have used l and ))))" to denote the loss function and training data, respectively. S L-RReNEu denotes a ResNEst using a fixed feature finding weights Ø. Although (P&)) has less optimization variables and looks easier than (P), Proposition shows that it is non-convex problem. Remark I explains why understanding (P&) is valuable.
Remark 1. Let the set of all local minimizers of (P&) using any possible features equip with the corresponding &. Then, this set is superset of the set of all local minimizers of the original ERM problem (P). Any characterization of (P () can then be translated to (P) (see Corollary for example).
Assumption 1. V (x") * 0 and EN= VL (x") VL (x")) is full rank.
VL
Proposition 1. If & is the squared loss and Assumption iis satisfied, then (a) the objective function of (P&) is non-convex and non-concave; (b) every critical point that is not a local minimizer is saddle point in (P
The proof of Proposition is deferred Appendix A. in the supplementary material. Due the
product W L++ W L. in R LW, WL+15 Φ), our Assumption is similar to one of the important data assumptions used in deep linear networks [Baldi and Hornik 1989 Kawaguchi] 2016). Assumption [ is casy to be satisfied as we can always perturb & if the last nonlinear feature and dataset do not fit the assumption. Although Proposition I (a) examines the non-convexity for fixed Φ, the result can be extended to the original ERM problem (P) for the ResNEst. That is, if there exists at least one &f such that Assumption iss satisfied, then the objective function for the optimization problem (P) is also non-convex and non-concave because there exists at least one point in the domain at which the Hessian is indefinite. As result, this non-convex loss landscape in (P) immediately raises issues about suboptimal local minima in the loss landscape. This leads to an important question: Can we guarantee the quality of local minima with respect to some reference models that are known to be good enough?
5

---

2.3 Finding reference models: bounding empirical risks via augmentation
To avoid the coupling problem in ResNEsts, we propose a new architecture Figure | called augmented ResNEst or A-ResNEst. An L-block Ees introduces another set of parameters (H. to replace every bilinear map on each feature in with linear map:
L-A-ResNEsst (x)
H.v, (x).
(4)
Now, the function Nes--R is linear with respect to all the prediction weights {H, Note that the parameters (W.) (W) still exist and now dedicated to feature finding. On the other hand, W and W L++1 are deleted since they are not used in the A-ResNEst. As a result, the corresponding ERM problem (PA) is defined on (Ho... Hy, Φ). We denote as the empirical risk in A-ResNEsts. The prediction weights are now different from the ResNEst as the A-ResNEst uses {H,} Because any A-ResNEst prevents the coupling problem, it exhibits nice property shown below.
Assumption 2. The loss function y is differentiable and convex in y for any y. Proposition 2. Let (Ho:
Hi.) be any local minimizer of the following optimization problem:
(PA
min A(H,, ,,H HL:O)
(5)
Ho. HE
where A (Ho..... HL:d) v Em= l (52 (LL--RONN (x*) If Asssspptiin satisfied, then the optimization problem in is convex and
<WL, W WL+i Φ) R (Wi, Wi+1i AH, :2
for any local minimizer
W W Wi+1) (f (P+) using arbitrary feature finding parameters Φb
The proof of Proposition 2 is deferred to Appendix A.2 in the supplementary material. According to Proposition 2 A-ResNEst establishes empirical risk lower bounds (ERLBs) for a ResNEst. Hence, for the same & picked arbitrarily, an A-ResNEst is better than a ResNEst in terms of any pair of two local minima in their loss landscapes. Assumption 2 practical because it is satisfied for two commonly used loss functions in regression and classification, i.e., the squared loss and cross-entropy loss. Other losses such as the logistic loss and smoothed hinge loss also satisfy this assumption.
2.4 Necessary condition for strictly improved residual representations
What properties are fundamentally required for features to be good, i.c., able to strictly improve the residual representation over blocks? With A-ResNEsts, we able to straightforwardly answer this question. A fundamental answer is they need to be at least linearly unpredictable. Note that v; must be linearly unpredictable by Vo. V if
A (H. Hi, ... H O, ... ,0, > HH ... , 0, 0, ..
for any local minimum (H..... H x-) in (PA). In other words, the residual representation x; is not strictly improved from the previous representation x;-I if the feature v, is linearly predictable by the previous features. Fortunately, the linearly unpredictability of v; is usually satisfied when G, is nonlinear; and the set of features can be viewed as basis function. This viewpoint also suggests avenues for improving feature construction through imposition of various constraints. By Proposition 2 the relation in (7) always holds with equality, i.c., the residual representation x; is guaranteed to be always no worse than the previous one x;-1 at any local minimizer obtained from an A- A-RtsNEst.
Wide ResNEsts with bottleneck residual blocks always attain ERLBs
Assumption 3. M 2 No.
Assumption 4. The linear inverse problem XL-1 Ei- Wiv; has unique solution.
Theorem 1. If Asssmption 2 and are sutisfied, then the following two properties are true in (P&) under any & such that Assumption holds: (a) every critical point with full rank W L41 is global minimizer; (b) for every local minimizer.

---

The proof of Theorem[] I is deferred to Appendix A.3 in the supplementary material. Theorem provides sufficient condition for critical point to be a global minimum of (P&). Theorem (b) gives an affirmative answer for every local minimum in (P&) to attain the ERLB. To be more specific, any pair of obtained local minima from the ResNEst and the A-ResNEst using the same arbitrary & are equally good. In addition, the implication of Theorem (b) is that every local minimum of (Pa is also a global minimum despite its non-convex landscape (Proposition [T. which suggests there exists no suboptimal local minimum for the optimization problem (P&). One can also establish the same results for local minimizers of (P) under the same set of assumptions by replacing "(Pø) under any ø with just "(PY" in Theorem [ Such modification may gain more clarity, but is more restricted than the original statement due to Remark II Note that Theorem T is not limited to fixing any weights during training; and it applies both normal training (train all the weights in network as a whole) and blockwise or layerwise training procedures.
3.1 Improved representation guarantees
By Remark 1 and Theorem (b), we can then establish the following representational guarantee.
Remark 2. Let Assumption 2 and be true. Any local minimizer of (P) such that Assumption 4 is satisfied guarantees (a) monotonically improved (no worse) residual representations over blocks; (b)
every residual representation is better than the imput representation in the linear prediction sense.
Although there may exist suboptimal local minima in the optimization problem (P), Remark suggests that such minima still improve residual representations over blocks under practical conditions. Mathematically, Remark 2 (a) and Remark 2 are described by Corollary aad the general version of Corollary [ respectively. Corollary I compares the minimum empirical risk obtained at any two representations among X1 to x for any given network satisfying the assumptions; and Corollary [ extends this comparison to the input representation.
Corollary 1. Let Assumption 2 and 3 be true. Any local minimum of (Pa) is smaller than or equal to any local minimum of (P²) under Assumption for any a ( --1, lm and B
Lop where T. and T.g are positive integers such that Tia > Lg-
The proof of Corollary 1 is deferred to Appendix A.4 in the supplementary material. Because Corollary T holds true for any properly given weights, one can apply Corollary T to proper local minimizers of (P). Corollary@Jensuress that ResNEsts are guaranteed to be no worse than the best linear predictor under practical assumptions. This property useful because linear estimators are widely used in signal processing applications and they can now be confidently replaced with ResNEsts.
Corollary
2. Let
(W
Wi Wi+1 .i................ .07,
be any local minimizer of (P) 2 and are satisfied, then (a) N
and 0
(Wi-1,0))
If Assumption
R Wi Wi.,,, 8
m= l (Ax", y"";; (b) the above inequality is strict if A (H5. 0, .,... ,,, > A (H.. ... HH,, )²).
87
min A
N
The proof of Corollary 2 is deferred to Appendix A.5 in the supplementary material. To the best of our knowledge, Corollary is the first theoretical guarantee for vector- valued ResNet-like models that have arbitrary residual blocks to outperform any linear predictors. Corollary is more general than the results in (Shamir 2018 Kawaguchi and Bengio 2019 Yun et al.) [019] because is not limited to assumptions like scalar-valued output or single residual block. In fact, we can have even more general statement because any local minimum obtained from (Pa) with random or any & is better than the minimum empirical risk provided by the best linear predictor, under the same assumptions used in Corollary 2 This general version fully describes Remark 2 (b).
Theorem I Corollary I and Corollary 2 are quite general because they are not limited to specific loss functions, residual functions, or datasets. Note that we do not impose any assumptions such as differentiability or convexity on the neural network G; for = 1, 2, ... L in residual functions. Assumption is practical because the expansion factor M usually larger than the input dimension Nin: and the output dimension N₂ is usually not larger than the input dimension for most supervised learning tasks using sensory input. Assumption states that the features need to be uniquely invertible from the residual representation. Although such an assumption requires a special architectural design, we find that it is always satisfied empirically after random initialization or training when the "bottleneck condition" is satisfied.
7

---

3.2 How to design architectures with representational guarantees?
Notice that one must be careful with the ResNEst architectural design so as to enjoy Theorem Corollary and Corollary 2 A ResNEst needs to be wide enough such that M 2 E Kg to necessarily satisfy Assumption 4 We call such sufficient condition on the width and feature dimensionalities as a bottleneck condition. Because each nonlinear feature size K; for i < L (say L > 1) must be smaller than the dimensionality of the residual representation M. each of these residual functions a bottleneck design (He al. 20166a Zagoruyko and Komodakis 2016] forming bottleneck residual block. We now explicitly see the importance of the expansion layer. Without the expansion, the dimenionality of the residual representation is limited to the input dimension. As a result, Assumption 4 cannot be satísfied for I. > 1; and the analysis for the ResNEst with multiple residual blocks remains intractable or requires additional assumptions on residual functions.
Loosely speaking, sufficiently wide expansion satisfaction of the bottleneck condition implies Assumption 4 If the bottleneck condition is satisfied, then ResNEsts are equivalent to A RestNEst for a given Ø, i.e., 0. If not (e.g., basic blocks are used in a ResNEst), then ResNEst can have a problem of diminishing feature reuse or end up with poor performance even though it has excellent features that can be fully exploited by an A-ResNEst to yield better performance, i.e., e <>> O. From such a viewpoint, Theorem [ supports the empirical findings in [He et al., (2116a) that bottleneck blocks more economical than basic blocks. Our results thus recommend AeResNEsts over ResNEsts if the bottleneck condition cannot be satisfied.
3.3 Guarantees on saddle points
In addition to guarantees for the quality of local minima, we find that ResNEsts can easily escape from saddle points due to the nice property shown below.
Theorem 2. If is the squared loss. and Assumption and are satisfied, then the following two properties are true every saddle point of (P&) under any & such that Assumption f holds: (a) WL+1 is refi-defi (b) there exists at least one direction with strictly negative curvature.
The proof of Theorem 2 is deferred to Appendix A.6 in the supplementary material. In contrast to Theorem [] (a), Theorem (a) provides necessary condition for saddle point. Although (P&)
is a non-convex optimization problem according to Proposition I (a), Theorem 2 (b) suggests a desirable property for saddle points in the loss landscape. Because there exists at least one direction with strictly negative curvature at every saddle point that satisfies the bottleneck condition, the
second-order optimization methods can rapidly escape from saddle points (Dauphin et al., 2014). If the first-order methods are used, the randomness in stochastic gradient helps the first-order methods escape from the saddle points [Ge et al., 20155. Again, we require the bottleneck condition to be satisfied in order to guarantee such a nice property about saddle points. Note that Theorem 2 is not limited to fixing any weights during training, and it applies to both normal training and blockwise training procedures due to Remark
DenseNEsts are wide ResNEsts with bottleneck residual blocks equipped with orthogonalities
Q2
Q
V1
V2
VL
x Vp
W L+1
DeaseNEat
X1
X
Figure 3: A generic vector- DenseNEst that has a chain of L dense blocks (or units). The symbol "Ø" represents the concatenation operation. We intentionally draw DenseNEst in such form to emphasize its relationship to a ResNEst (see Proposition
Instead of adding one nonlinear feature in each block and remaining in same space R,, the DenseN- Est model shown in Figure preserves each of features in their own subspaces by a sequential concatenation at each block. For an L-block DenseNEst, we define the i-th dense block as function M. + Mr of the form
x; X.-1QQ (x-1:0,)
(8)
8

---

10
Q2
Q
W L=1
DenseNsst
Figure 4: An equivalence to Figure emphasizing the growth of the input dimension at each block.
for i 1....... where the dense function Q, is general nonlinear function; and x; is the output of the i-th dense block. The symbol C concatenates vector x; 1 and vector Q (x:-1; 0,)
and produces a higher-dimensional vector xx_= Q (x)-1:0))) We define Xo x where E R.Vin is the input to the DenseNEst. For all (1,2, L... (x;x;;;; MR + R Dr is function implemented by neural network with parameters 0; where D; = Mi M;-1 2 1 with Mo Nm Du- The output of DenseNEst defined as DDeesNNEs
WL+1X1 for
WL+1 E NNMMM, which can be written as
W WL+1 (xg QQ (Xo; 01) 0.2 (xL-1;0 = E W W1+1,VV:()) 100
(9)
where vi (x) = Qx; 0,) = Ov Cv,,,1; for 1,2,..., are re- garded nonlinear features of the input x. We define vo
the linear feature. WL+1
WL+ WL+IL is the prediction weight matrix in the DenseNEst as all the weights which are responsible for the prediction is in this single matrix from the viewpoint of basis function modeling. The ERM problem (PD) for the DenseNEst is defined on (Wi+1,0, 1,.... 0z). To fix the features, the set of parameters ERM problem for any fixed features, denoted as (PD&), is fairly straightforward as it only requires to optimize over single weight matrix, i.e.,
WL++0 WL+1.1
{0.) 1- needs be fixed. Therefore, the DenseNEst
(PD&) min D D(W L+1:0) WL+1
(10)
where D (W = EN ( (x*) ym Unlike ResNEsts, there is no such cou-
pling between the feature finding and linear prediction in DenseNEsts. Compared to ResNEsts or A A-stsNEsts, the way the features are generated in DenseNEsts generally makes the linear predictabil- ity even more unlikely. To see that, note that the Q directly applies on the concatenation of all previous features; however, the G, applies the sum of all previous features.
Different from ResNEst which requires Assumption 2 and to guarantee its superiority with respect to the best linear predictor (Corollary 2). the corresponding guarantee in DenseNEst shown in Proposition 3 requires weaker assumptions.
Proposition 3. If Assumption 2 is satisfied, then any local minimum of (PD) is smaller than or equal to the minimum empirical risk given by any linear predictor of the input.
The proof of Proposition]] 3 is deferred to Appendix A.7 in the supplementary material. Notice that no special architectural design in DenseNEst required to make sure it always outperforms the best linear predictor. Any DenseNEst always better than any linear predictor when the loss function differentiable and convex (Assumption
2 Such an advantage can be explained by the WL+1 in the DenseNEst. Because WL+1 the only prediction weight matrix which is directly applied onto the concatenation all the features, (PD,) () is a convex optimization problem. We point out the difference of W 1 between the ResNEst and DenseNEst. In the ResNEst, W L++1 needs interpret W the features from the residual representation; while the W 1 i in the DenseNEst directly accesses the features. That is why we require Assumption 4 in the ResNEst eliminate any ambiguity on the feature interpretation.
Can ResNEst and DenseNEst be equivalent? Yes, Proposition 4 establishes a link between them. Proposition 4. Given any DenseNEst ý L-DemseNEa. there exists wide ResNEst with bottleneck residual blocks y ResNEa such that t L.RENEE (x) = ÿ DenseNes (x) for all E RiNi , addition. Assumption 2 and are satisfied, then 0 for every local minimizer of (P

---

The proof of Proposition Fi deferred to Appendix (..nndix(..8jnn in the supplementary material. Because the concatenation of two given vectors can be represented by an addition over two vectors projected onto higher dimensional space with disjoint supports, one straightforward construction for an equivalent ResNEst is to sufficiently expand the input space and enforce the orthogonality of all the column vectors in Wo: 0. W 1.-.. "1.... W.. L. As a result, any DenseNEst can be viewed as ResNEst that always 4 and of course the bottleneck condition no matter how we train the DenseNEst or select its hyperparameters, leading to the desirable guarantee, i.e., any local minimum obtained in optimizing the prediction weights of the resulting ResNEst from any DenseNEst always attains the lower bound. Thus, DenseNEsts are certified being advantageous over ResNEsts by Proposition 4 For example, a small M may be chosen and then the guarantee in Theorem T can no longer exist, ie., > 0. However, the corresponding ResNEst induced by DenseNEst always achieves 0. Hence, Proposition caa be regarded as a theoretical support for why standard DenseNets [Huang
satisfies Assumption
al. 2017 are in general better than standard ResNets (He al. 2016b
5
Related work
In this section, we discuss ResNet works that investigate on properties of local minima and give more details for our important references that appear in the introduction. We focus on highlighting their results and assumptions used so as to compare to our theoretical results derived from practical assumptions. The earliest theoretical work for ResNets can be dated back to [Hardt and Ma 2017) which proved a vector-valued ResNet-like model using linear residual function in each residual block has no spurious local minima (local minima that give larger objective values than the global minima) under squared loss and near-identity region assumptions. There are results (Li and Yuan 2017 Liu et al. 2019] proved that stochastic gradient descent can converge to the global minimum in ocalar-values two-layer ResNet-like models; however, such desirable property relies on strong assumptions including single residual block and Gaussian input distribution. Li al. (2018) visualized the loss landscapes of ResNet and its plain counterpart (without skip connections): and they showed that the skip connections promote flat minimizers and prevent the transition to chaotic behavior. Liang et al. [2018] showed that scalar- valued and single residual block ResNet-like models have zero training error at all local minima by making strong assumptions in the data distribution and loss function for a binary classification problem. In stead of pursuing local minima are global in the empirical risk landscape using strong assumptions, /Shamir (2018) first took a different route and proved that a scalar-valued ResNet-like model with a direct skip connection from input to output layer (single residual block) is better than any linear predictor under mild assumptions. To be more specific. he showed that every local minimum obtained in his model is no worse than the global minimum in any linear predictor under more generalized residual functions and no assumptions on the data distribution. He also pointed out that the analysis for the vector-valued case nontrivial. Kawaguchi and Bengio [219] overcame such a difficulty and proved that vector-valued models with single residual block is better than any linear predictor under weaker assumptions. Yun et al.) [2019] extended the prior work by Shamir (2018) to multiple residual blocks. Although the model considered is closer to a standard ResNet compared to previous works, the model output assumed to be valuud, All above-mentioned works do not take the first layer that appears before the first residual block standard ResNets into account. As a result, the dimensionality of the residual representation in their simplified ResNet models is constrained to be the same size the input.
Broader impact
One of the mysteries in ResNets and DenseNets is that learning better DNN models seems to be as easy as stacking more blocks. In this paper, we define three generalized and analyzable DNN architectures, i.e., ResNEsts, A A-ResNEsts, and DenseNEsts, to answer this question. Our results not only establish guarantees for monotonically improved representations over blocks, but also assure that all linear (affine) estimators can be replaced by our architectures without harming performance. We anticipate these models can be friendly options for researchers or engineers who value or mostly rely on linear estimators or performance guarantees in their problems. In fact, these models should yield much better performance as they can be viewed as basis function models with data-driven bases that guarantee to be always better than the best linear estimator. Our contributions advance the fundamental understanding of ResNets and DenseNets, and promote their use cases through a certificate of attractive guarantecs.
10

---

Acknowledgments and disclosure of funding
We would like thank the anonymous reviewers for their constructive comments. This work was supported in part by NSF under Grant CCF-2124929 and Grant IIS- UIS-1838830, in part by NIH/NIDDD under Grant R01DC015436, Grant R21DC015046, and Grant R33DC015046, in part by Halıcooglu Data Science Institute, and in part by Wrethinking, the Foundation.
References
P. Baldi and K. Homik. Neural networks and principal component analysis: Learning from examples without local minima. Neural Networks, 2(1):53-58, 1989.
C. M. Bishop. Pattern recognition and machine learning. springer, 2006.
Y. N. Dauphin, R. Pascanu, C. Gulcehre, Cho, S. Ganguli, and Y. Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. In Advances in Neural Information Processing Systems, pages 2933-2941, 2014.
R. Ge, F. Huang, C. Jin, and Y. Yuan. Escaping from saddle points stochastic gradient for tensor decomposition. In Conference on Learning Theory, pages 797-842, 2015.
M. Hardt and T. Ma. Identity matters in deep learning. In International Conference on Learning Representations, 2017.
K. He and J. Sun. Convolutional neural networks at constrained time cost. In Conference on Computer Vision and Pattern Recognition, pages 5353-5360. IEEE, 2015.
K. He, X. Zhang, S. Ren, and Sun. Deep residual learning for image recognition. In Conference on Computer Vision and Pattern Recognition, pages 770-778. IEEE, 2016a.
K. He, X. Zhang, Ren, and Sun. Identity mappings in deep residual networks. In European Conference on Computer Vision, pages 630-645. Springer, 2016b.
J. Hu, L. Shen, and G. Sun. Squeeze-and-exciiation networks. In Conference Computer Vision and Pattern Recognition, pages 1142.7141. IEEE, 2018.
G. Huang, Z. Liu, L. van der Maaten, and K. Q. Weinberger. Densely connected convolutional networks. In Conference on Computer Vision and Pattern Recognition, pages 4700-4708. IEEE, 2017.
K. Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems, pages 586-594, 2016.
K. Kawaguchi and Y. Bengio. Depth with nonlincarity creates no bad local minima in resnets. Neural Networks, 118:167-174, 2019.
Kim, J. Kwon Lee, and K. Mu Lee. Accurate image super-resolution using very deep convolutional networks. In Conference Computer Vision and Pattern Recognition, pages 1646-1654. IEEE, 2016.
J. Kim, M. El-Khamy, and J. Lee. Residual LSTM: Design of deep recurrent architecture for distant speech recognition. arXiv preprint 170X:v11700.3. 2017.
A. Krizhevsky. Learning multiple layers of features from tiny images. Tech Report, 2009.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. ImageNet classification with deep convolutional neural
networks. In Advances in Neural Information Processing Systems, pages 1097-1105, 2012.
H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein. Visualizing the loss landscape of neural nets. In Advances in Neural Information Processing Systems, pages 6389-6399, 2018.
Y. Li and Yuan. Convergence analysis of two-layer neural networks with relu activation. In
Advances in Neural Information Processing Systems, volume 30, pages 597-607, 2017.

---

S. Liang, R. Sun, Y. Li, and R. Srikant. Understanding the loss surface of neural networks for binary classification. In International Conference on Machine Learning, pages 2835-2843 2018.
L. Liu, M. Chen, M. Zhou, Du, Zhou, and Zhao. Towards understanding the importance of shortcut connections in residual networks. In Advances in Neural Information Processing Systems, 2019.
Milletari, N. Navab, and S.-A. Ahmadi. V-Net: Fully convolutional neural networks for volumetric medical image segmentation. In International Conference 3D Vision, pages 565-571, IEEE, 2016.
X. Qin, Z. Zhang, C. Huang, M. Dehghan, O. R. Zaiane, and M. Jagersand. - Going deeper with nested U-structure for salient object detection. Pattern Recognition, 106: 107404 2020.
O. Shamir. Are ResNets provably better than linear predictors? Advances in Neural Information Processing Systems, pages 507-516, 2018.
K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
R. K. Srivastava, K. Greff, and Schmidhuber. Highway networks. arXiv preprint arXiv:1505.003:0 2015.
C. Szegedy, W. Liu, Jia, P. Sermanet, S. Reed, D. Anguclov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In Conference on Computer Vision and Pattern Recognition, pages 1-9, IEEE, 2015.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, F.. Kaiser, and I. Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pages 9999-6008. 2017.
A. Veit, M. Wilber, and Belongie. Residual networks behave like ensembles of relatively shallow networks. In Advances in Neural Information Processing Systems, pages 550-558, 2016.
S. Xie, R. Girshick, P. Dollár, Z. Tu, and K. He. Aggregated residual transformations for deep neural networks. In Conference on Computer Vision and Pattern Recognition, pages 1492-1500. IEEE, 2017.
W. Xiong, L. Wu, Alleva, J. Droppo, X. Huang, and A. Stolcke. The Microsoft 2017 conversational speech recognition system. In International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5934-5938. IEEE, 2018.
C. Yun, S. Sra, and A. Jadbabaie. Are deep ResNets provably better than linear predictors? In Advances in Neural Information Processing Systems, pages 15686-15695, 2019.
S. Zagoruyko and N. Komodakis. Wide residual networks. In British Machine Vision Conference (BMVC), pages 87.1-87.12 12. BMVA Press, 2016.
M. D. Zeiler and R. Fergus. Visualizing and understanding convolutional networks. In European Conference on Computer Vision, pages 818-833. Springer, 2014.
12


Reviews:
[{"review_id": "w1Qmauz9oDD", "reviewer": "Reviewer_vBzc", "summary": "This work studies the representational power of Residual Networks and try to explain theoretically a desirable property of using ResNets, namely: does a residual network guarantee that stacking more residual blocks does not lead to a degradation in performance of the network. The main approach of the authors is to view the output of a ResNet as an ensemble of several shallow networks as opposed to a non-ResNet which is simply a very deep composition of non-linear functions. Given this view point, the authors identify some simplifying assumptions which make the associated Empirical Risk Minimization problem tractable: 1) introducing a sequence of \"de-coupling\" weights (H) which allow the weights (W) in the ensemble to be independent of each other 2) removing the non-linearity at the end of the residual block and before the final affine transformation and 3) a few assumptions on the loss function (differentiability and convexity). With these assumptions, the authors prove a few desirable properties of ResNet architectures. Firstly, the authors show that stacking more residual blocks cannot hurt in the representational sense, and can improve if the new feature is linearly independent of the other features in the ensemble basis. Secondly, the authors show that \"wide ResNets\" always attain the empirical risk minimization lower bound, which has an implication on the quality of local optima attained by the ResNets. The authors also prove analogous results for a related class of architectures (DenseNets), in particular showing that DenseNets may be approximated by wide ResNests.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This is a very interesting paper which studies an important problem from a theoretical angle, namely the representational power of Residual Networks, and what characterizes their empirical good performance compared to simply stacking dense functions. The work introduces some simplifications to make the problem more tractable, and show theoretically that in the setting when the final non-linearity is removed from a chain of residual blocks, we get a theoretical guarantee that stacking more residual blocks is guaranteed to not hurt performance in the optimization setting (modulo some assumptions). This seems like an important and very interesting observation, and I wonder if some of assumptions which the authors made to get to the theoretical result could lead us to design better real world architectures - for instance, would a \"decoupled\" ResNet lead to improvements over a regular ResNets empirically?\n\nThe paper is overall well written and easy to follow, although the main proofs of all the claims are in the Appendix which doesn't seem included. However, with the assumptions introduced by the authors, the conclusions of the theorems sound reasonable. In terms of future directions/improvements, I would encourage the authors to investigate this phenomenon empirically as well, to see if some of the assumptions hold in real world datasets, which would make the work more compelling.\n\nTypos/Clarifications:\n\nLine 234: It seems N_0 has not been defined before, is it some large constant we are assured the existence of?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "src9-hj8dln", "reviewer": "Reviewer_Mr4e", "summary": "The authors present several theoretical properties of a ResNet variant that is similar to a standard ResNet only without one of the non-linearities. Variants of DenseNets are also suggested with improved guarantees. Such variants are much closer to the real ResNet that is used in computer vision applications than the models that were previously analyzed. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is interesting and introduces some important theoretical concepts and proofs. However, it is tough to follow and understand. Even starting at Section 2.1, I could not quite understand for sure what the ResNEst model is. This has to be improved somehow. \n\nCan the authors show some results regarding how ResNEst performs in simple classification tasks compared to a standard ResNet? Usually, simpler variants with guarantees perform worse than the original, and it would be interesting to see just how much ResNEst loses in classification accuracy to get these guarantees. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not address those, but I do not see any issues or have any suggestions for improvement. ", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "nglS_GZ5Ken", "reviewer": "Reviewer_zqDC", "summary": "This paper studies a variant of ResNet/DenseNet, which removes the final nonlinearity. This makes the output a linear combination of a set of basis functions, which can be viewed as features extracted by the various blocks of the architecture. Based on this formulation, results regarding the optimization minima are examined. An augmented version of the architecture in question is also analyzed.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper analyzes ResNEsts, which are essentially ResNets without a final nonlinearity. This characterization leads to some interesting results:\n- Assuming all layers except the last one are fixed, the output can be viewed due to this formulation as a linear combination of basis functions $v_i(x)$, each outputted by the previous blocks of the network.\n- This characterization also serves as an inspiration for a slightly different architecture, Augmented ResNEsts. In those, the output of each residual block is kept and used at the end of the model, multiplied by another weight matrix $H_i$.\nThe paper also defines DenseNEsts, as an extension of the previous architecture similar to DenseNets, and also proves that they can be seen as a sufficiently wide ResNEst.\n\nThis work serves as a theoretical analysis of the above variation of ResNets, and the theorems/propositions included are technically sound. Proofs for some training properties (namely, directions of negative curvature in saddle points, and that wide ResNEsts attain their proposed ERLBs) are also included. Nevertheless, there are some issues which limit the impact of the paper:\n- Regarding ResNEsts, all theorems are done under the assumption that all weight matrices except the two last ones are fixed. Note though that this is done to keep the functions $v_i(x)$ fixed, and if I understand correctly the intent of the authors was to show via Theorem 1 that stacking extra blocks in the wide ResNEst will not decrease performance (since the A-ResNEst essentially includes ResNEsts of all previous block sizes). In this case, it may be less of a limit of novelty and more of a clarity issue.\n- Similarly, regarding A-ResNEsts, due to keeping the weight matrices of the intermediate layers (and thus, the $v_i(x)$) fixed, the analysis presented in this paper is the same as the analysis that would be done for a linear predictor, which has as input all the features $v_i(x)$ and a block diagonal weight matrix, with each part being equal to $H_i$. This is a very specific case of the proposed architecture.\n- Corollary 1 appears to be self-evident (as a class of models, ResNEsts already include linear predictors).\n\nThis submission is clear in general and mostly easy to follow, although I do have some questions for the authors:\n- If I am not mistaken, Remark 2 seems to imply that the intended use of ResNEsts is that training is done layer-by-layer, and the result is that doing so always improves the performance of the output. If this is indeed the case, then I suggest including it more prominently in the paper.\n- In lines 252-253, a condition is stated in order for Assumption 4 to be satisfied. Does this mean that Assumptions 3 and 4 can be combined?\nThe clarity of the text could also be improved by explicitly defining optimization problems (so that they can easily be referred to later), instead of keeping them inside the text. \n\nIn general, the paper has several different contributions, but most of them appear limited in scope and application. I think it would be useful for the authors to highlight how the basis functions $v_i(x)$ are obtained, or if they are assumed to be given for the application of the ResNEst.\n\n**Post-rebuttal comment**:\n\nAfter the author response, I have updated my score, based on my comments below.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately described the limitations present in each theorem/proposition made. Depending on how the $v_i(x)$ are obtained, I believe it is worthwhile to discuss this as well.\n\nRegarding negative social impacts, this is a purely theoretical work, and the models presented do not have any issues of such kind to be discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "ZLOSjm828Mi", "reviewer": "Reviewer_SQ4N", "summary": "This paper defines slightly modified variants of commonly used ResNet and DenseNet architectures, and shows that these architectures have attractive theoretical properties - increasing depth does not decrease performance (which in particular means that they should be guaranteed to outperform linear models in terms of training loss).", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The problem addressed (generalization properties of realistic modern neural network architectures) is important and relevant to the machine learning community, and the solution is novel and represents a substantial improvement over existing work. The paper is fairly well-written and clear.\n\nAlthough this is a theory paper, it would benefit from experiments to compare standard ResNets with ResNEsts and especially A-ResNEsts (and similarly DenseNets and DenseNEsts), since these are new model architectures being proposed. Although the theoretical justification for these new architectures appears to be sound, showing that they also work well in practice would substantially improve the paper, as that combined with the theoretical guarantees would provide strong support for practitioners to actually use these architectures. Although ResNEsts are a trivial modification of standard ResNets, this is not as true for the other new architectures proposed (and even ablating the effect of the minor difference between ResNet and ResNEst would be very useful).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is very little discussion of these. However, I do not think any negative societal impact would apply as this paper simply advances theoretical understanding.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Fg9aImtr7_T", "reviewer": "Reviewer_AWNq", "summary": "The authors proposed a couple modification of ResNet in order to improve the loss landscape. The main idea behind the modifications, if I understand correctly,  is to guarantee a direct skip connection (dense matrix or product of dense matrix) from the hidden features to the logits. The authors provide a  couple theoretical claims regarding the proposed models. No experimental results are provided. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Overall, I found the presentation of the paper unsatisfying and difficult to follow. From the abstract and introduction, I find myself difficult to extract the main theme and main contribution of the paper. Only after going thorough the papers twice, I finally realized the paper is about landscape analysis of ResNets and its variants. Regardless of the results of the paper, presentation requires substantial improvement and empirical supports are needed to support major claims. Moreover, methods/modifications that improve loss landscape of the SOTA models (e.g. ResNet) more often than not may not be useful at all, unless they could improve the original performance, or on par with it and improves the optimization, or simplifies the models and etc. As such, I do not support acceptance.   \n\nIn what follows, I try my best to summarize the main contribution and ideas of the paper. \nThe main complaint about ResNet of the paper is the *non-linearity* layer before the linear classifier and the authors propose to remove it. The main benefit of doing so is the logits $y$ could be written as a linear combination of hidden features of the networks, namely, \n$$\ny(x) = \\sum_{i=1}^L A_i v_i(x)\n$$\nwhere $v_i(x)$ is the hidden feature and $A_i$ is an affine transform which is product of two matrices. Under some rank assumptions, the authors claim that loss function associated to this modified model is non-convex but enjoys a good property: every critical point that is not a local minimum is a saddle point (proposition 1). Obvious, the fact $A_i$ being a product of two dense matrices creates many saddle points and the author propose add a skip-connection from $v_i$ directly to the logits layer and $A_i$ could be replaced by a dense matrix $H_i$, i.e. \n$$\ny(x) = \\sum_{i=1}^L H_i v_i(x)\n$$\nThe authors proceed to conclude that the new optimization problem is convex, which seems obvious since the new model is a linear function function the hidden features. They then apply similar tricks to DenseNet. \n\nOverall, these landscape results seem not very interesting nor significancy, at least to me. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Theoretical understanding of ResNet is important and indeed very important! Principle-guided approach to design architecture is also equally important. However, I don't think the paper made significant advances in these two problems, in particular, without strong empirical support. I would encourage the authors to provide experimental results to demonstrate the superior of the proposed architectures.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work studies the representational power of ResNets and aims to answer the question of when adding more residual blocks in a ResNet can be guaranteed to not lead to a degradation in performance. All 5 reviewers find the paper interesting and think its contribution is a valuable addition to the literature. All reviewers were active in discussion with the authors and with the committee. No serious concerns surfaced that would invalidate the contribution made by the paper. After committee discussion the reviewers reached a consensus recommendation to accept the paper.

Multiple reviewers indicated that the author response was especially useful and served to clear up some minor concerns that existed after the first round of reviews. Authors, please integrate this discussion into the camera ready version of the paper.
Decision: Accept (Poster)