Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced

Abstract

We study the implicit regularization imposed by gradient descent for learning multi-layer homogeneous functions including feed-forward fully connected and convolutional deep neural networks with linear, ReLU or Leaky ReLU activation. We rigorously prove that gradient flow (i.e. gradient descent with infinitesimal step size) effectively enforces the differences between squared norms across different layers to remain invariant without any explicit regularization. This result implies that if the weights are initially small, gradient flow automatically balances the magnitudes of all layers. Using a discretization argument, we analyze gradient descent with positive step size for the non-convex low-rank asymmetric matrix factorization problem without any regularization. Inspired by our findings for gradient flow, we prove that gradient descent with step sizes ${\eta }_t=O\left(t^{-\left(\frac{1}{2}+\delta \right)}\right)$ ($0<\delta \le \frac{1}{2}$) automatically balances two low-rank factors and converges to a bounded global optimum. Furthermore, for rank-$1$ asymmetric matrix factorization we give a finer analysis showing gradient descent with constant step size converges to the global minimum at a globally linear rate. We believe that the idea of examining the invariance imposed by first order algorithms in learning homogeneous models could serve as a fundamental building block for studying optimization for learning deep models.

arXiv commentIn NIPS 2018

References in corpus (19)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Path-SGD: Path-Normalized Optimization in Deep Neural Networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Recovery Guarantees for One-hidden-layer Neural Networks
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• Learning One-hidden-layer Neural Networks with Landscape Design
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Mathematics of Deep Learning
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• When is a Convolutional Filter Easy To Learn?
• Direct Runge-Kutta Discretization Achieves Acceleration
• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
• Are ResNets Provably Better than Linear Predictors?
• SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
• The Landscape of Deep Learning Algorithms
• Data-Dependent Path Normalization in Neural Networks

Cited by in corpus (9)

• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Implicit Regularization in Deep Matrix Factorization
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Noether: The More Things Change, the More Stay the Same
• Robust and On-the-fly Dataset Denoising for Image Classification
• Synaptic balancing: a biologically plausible local learning rule that provably increases neural network noise robustness without sacrificing task performance
• The Landscape of Matrix Factorization Revisited
• How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization