Gradient descent favors sparse solutions in deep linear networks

Implicit Bias of (Stochastic) Gradient Descent on Deep Linear Diagonal Networks

Machine Learning

Summary

Machine learning models often have more parameters than data, meaning many equally good solutions exist. The authors study how gradient descent, a common training method, chooses solutions in deep linear diagonal networks. They show that gradient descent tends to pick sparse solutions, meaning solutions with fewer nonzero parameters, especially when starting small. This work extends previous results to the more realistic stochastic gradient descent and explains how step sizes affect these choices.

What this means in practice

  • For machine learning engineers: Better understand how training methods implicitly select sparse models to improve generalization and guide step size tuning in deep linear networks.
  • For statistical signal processors: Use insights on implicit bias toward weighted sparse solutions to design algorithms in signal processing that rely on sparse recovery properties.

A theory result. No direct application yet.

Authors

Wiebke Bartolomaeus, Holger Rauhut

Abstract

Modern machine learning models are often overparameterized, i.e., have more parameters than training data. This typically implies that the loss function admits multiple minimizers so that training methods (and their hyperparameter choices) have significant influence on the computed solution. We study this so-called implicit bias phenomenon in the context of training deep linear diagonal networks. Previous work has shown that the gradient flow for learning such networks converges to (almost) sparse solutions when initialized small. For an arbitrary number of layers, we extend this analysis to the practically more realistic (stochastic) gradient descent iterations. Our approach identifies (stochastic) gradient descent as a perturbed (stochastic) mirror gradient descent. This allows us to establish convergence and characterize the limiting solution, relating it to weighted $\ell_1$-minimization. Moreover, we provide sufficient conditions on the step sizes and quantify the influence of the step sizes on the implicit bias.