Representing smooth functions as compositions of near-identity functions with implications for deep network optimization

By Peter L. Bartlett, Steven N. Evans, Philip M. Long. 2018

34 citations recorded by the source corpus.

We show that any smooth bi-Lipschitz $h$ can be represented exactly as a composition $h_m \circ ... \circ h_1$ of functions $h_1,...,h_m$ that are close to the identity in the sense that each $\left(h_i-\mathrm{Id}\right)$ is Lipschitz, and the Lipschitz constant decreases inversely with the number $m$ of functions composed. This implies that $h$ can be represented to any accuracy by a deep residual network whose nonlinear layers compute functions with a small Lipschitz constant. Next, we consider nonlinear regression with a composition of near-identity nonlinear maps. We show that, regarding Fr\'echet derivatives with respect to the $h_1,...,h_m$, any critical point of a quadratic criterion in this near-identity region must be a global minimizer. In contrast, if we consider derivatives with respect to parameters of a fixed-size residual network with sigmoid activation functions, we show that there are near-identity critical points that are suboptimal, even in the realizable case. Informally, this means that functional gradient methods for residual networks cannot get stuck at suboptimal critical points corresponding to near-identity layers, whereas parametric gradient methods for sigmoidal residual networks suffer from suboptimal critical points in the near-identity region.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Simple and Principled Uncertainty Estimation with Deterministic Deep Learning via Distance Awareness (2020, methodology): “…spaces X and H is well-established in the learning theory and the generative modeling literature, but the application of these results in the context of uncertainty estimation for DNN appear to be new (Bartlett et al., 2018; Behrmann et al., 2019; Hauser and Ray, 2017; Rousseau et al., 2020).”
Architecture Matters in Continual Learning (2022, background): “…have been done to explain why skip connections are useful: Hardt and Ma (2016) show that skip connection tends to eliminate spurious local optima; Bartlett et al. (2018b) study the function expressivity of residual architectures; Bartlett et al. (2018a) show that gradient descent provably learns…”
Gradient Descent with Identity Initialization Efficiently Learns Positive-Definite Linear Transformations by Deep Residual Networks (2018, methodology): “The motivation for this work comes from the papers of Hardt & Ma (2017) and Bartlett et al. (2018).”
Step Size Matters in Deep Learning (2018, methodology): “Then the gradient descent algorithm with random initialization can converge to a solution {Ŵj}j∈[L] only if the step size δ satisfies δ ≤ 2 ∑L j=1 p 2 j−1q 2 j+1 (3)”
Data Driven Governing Equations Approximation Using Deep Neural Networks (2018, background): “It was shown in [3] that any smooth bi-Lipschitz function can be represented as compositions of functions, each of which is near-identity in Lipschitz semi-norm.”