Gradient descent's implicit bias is no longer set by initialization alone: step size tilts the limit toward a perturbed weighted L1 minimizer
Synopsis
The training limit of deep linear diagonal networks had been characterized only for gradient flow, the continuous version with vanishing step size, where the implicit bias is fixed entirely by initialization. This analysis rewrites discrete gradient descent and stochastic gradient descent themselves as perturbed mirror gradient descent, proves convergence of the iterates for any number of layers, and characterizes the limit as a convex minimization problem parameterized by a perturbed initialization. The perturbation shrinks linearly with step size, so the limit corresponds to weighted L1 minimization whose weights depend on initialization, step size and the whole iterate trajectory.
Interpretation
The limit of deep linear diagonal networks trained by discrete gradient descent now has a full characterization alongside the gradient-flow case, rather than only a continuous-time approximation. Earlier implicit-bias results mainly addressed gradient flow, the continuous limit with step size taken to zero; discrete gradient descent results were either restricted to two-layer networks or relied on Euler discretization error, requiring exponentially small step sizes or tolerating exponentially large error. For an arbitrary number of layers, provided the step sizes satisfy given upper bounds, the sequence of iterates is proven to converge and the limit is characterized as the unique solution of a strictly convex minimization problem.
The route is to translate gradient descent on the layer parameters into a perturbed mirror gradient descent on the end-to-end parameter, which makes mirror-method convergence tools available. Mirror gradient descent is an iterative scheme for optimization in non-Euclidean geometry, where each step regularizes a linearized objective with a Bregman divergence; here an extra perturbation term absorbs the gap between discrete updates and continuous dynamics. The analysis is first carried out for the positive model, where all weights start positive, then extended to solutions with negative entries through a difference model that splits the solution into positive and negative parts and doubles the parameter count; the stochastic gradient descent version uses martingale theory to prove almost sure convergence.
The weights of the limiting solution no longer depend on initialization alone; step size and the whole trajectory enter the weights, but this extra dependence vanishes linearly with step size. In the gradient-flow case the limit is a weighted L1 minimizer whose weights depend only on initialization, reducing to unweighted L1 minimization under uniform initialization; in the gradient-descent case the weights instead depend on the perturbed initialization. The norm of the difference between perturbed and original initialization is proven to scale linearly with the maximal step size, so the result returns to the gradient-flow characterization as step size goes to zero; numerical experiments observe this linear dependence at moderate step sizes as well.
Perspective
The conclusions concern linear diagonal networks: identity activation, zero biases, diagonal weight matrices, and balanced weight-shared initialization; the analysis covers the positive model and a difference model that splits the solution into positive and negative parts, and extends to mini-batch stochastic gradient descent. Convergence and the limit characterization assume step sizes satisfying given upper bounds, and the numerical experiments use Gaussian measurements with fixed ambient dimension, number of measurements and sparsity level.
The step-size bound is sufficient rather than necessary, and numerical experiments observe convergence even when step sizes exceed it, indicating the condition is not tight. The error vector depends on the whole iterate trajectory and gradients, and its explicit form appears only in the proof. The discussion of small initialization slowing convergence is explicitly noted by the authors to lack a matching lower bound, so it is not a rigorous proof.