Abstract
In this work, we investigate the dynamics of stochastic gradient descent (SGD) when training a single-neuron autoencoder with linear or ReLU activation on orthogonal data. We show that for this non-convex problem, randomly initialized SGD with a constant step size successfully finds a global minimum for any batch size choice. However, the particular global minimum found depends upon the batch size. In the full-batch setting, we show that the solution is dense (i.e., not sparse) and is highly aligned with its initialized direction, showing that relatively little feature learning occurs. On the other hand, for any batch size strictly smaller than the number of samples, SGD finds a global minimum which is sparse and nearly orthogonal to its initialization, showing that the randomness of stochastic gradients induces a qualitatively different type of "feature selection" in this setting. Moreover, if we measure the sharpness of the minimum by the trace of the Hessian, the minima found with full batch gradient descent are flatter than those found with strictly smaller batch sizes, in contrast to previous works which suggest that large batches lead to sharper minima. To prove convergence of SGD with a constant step size, we introduce a powerful tool from the theory of non-homogeneous random walks which may be of independent interest.
Introduction: Beyond Speed—The Implicit Bias of Batch Size
Deep learning practitioners have long observed that small batch sizes often lead to better generalization. However, the theoretical reason for this remains a subject of intense debate. Is it because small batches find "flatter" minima? Or is there a more fundamental "implicit bias" at play?
Most existing theoretical analyses simplify the problem by modeling SGD noise as Gaussian noise added to the labels or gradients. This paper tackles the problem head-on by analyzing the actual dynamics of mini-batch sampling. The authors investigate whether batch size alone can force a neural network to converge to qualitatively different types of solutions, even when both algorithms (SGD and full-batch GD) successfully minimize the training loss.
The Model: A Single-Neuron Autoencoder
The study focuses on a single-neuron weight-tied autoencoder with either linear or ReLU activations. To keep the analysis mathematically rigorous, the authors assume the training data consists of orthonormal vectors (a simplified version of a sparse coding model). Specifically, the training set $\mathcal{D} = \{a_1, \dots, a_m\}$ consists of $m$ orthonormal vectors in $\mathbb{R}^n$. While stylized, this setup allows the authors to isolate the effects of batch noise from the complexities of data correlations.
Symmetry Breaking and Feature Selection
A key insight of the paper is the distinction between "fair" and "biased" optimization. Full-batch GD is "too fair": because it sees all data points at once, it preserves the symmetry of the random initialization. It essentially just scales the initial weights, resulting in a dense solution that is highly aligned with the initial weights ($w_0$).
In contrast, the randomness of mini-batches in SGD breaks this symmetry. For any batch size $b < m$, SGD acts as a feature selector. It eventually "chooses" one specific data direction to follow, finding a 1-sparse solution aligned with a single data point ($a_i$). This represents significantly more "feature learning," as the weights move far from their initialization to incorporate data-dependent information.
The Sharpness Paradox
A common "rule of thumb" in deep learning is that small batches find flatter minima, which are thought to generalize better. This paper provides a surprising counterexample: for ReLU autoencoders, SGD actually finds sharper minima (measured by the trace of the Hessian) than full-batch GD. For large $m$, the trace of the Hessian at the SGD solution is approximately $0.5/m$ larger than at the GD solution. This suggests that "flatness" might not be the universal explanation for the success of small-batch SGD, and that the qualitative nature of the features learned (e.g., sparsity) may be more important.
Theoretical Contribution: Non-homogeneous Random Walks
To prove that SGD with a constant step size converges to a single point (rather than just bouncing around a region), the authors introduce a sophisticated tool from probability theory: the theory of non-homogeneous random walks. They demonstrate that SGD "amplifies" the correlation with one specific data point until the weights align with it perfectly, proving almost sure convergence to a global minimum even without learning rate decay.
Conclusion
This research demonstrates that the choice of batch size fundamentally changes the implicit bias of the learned model. While both GD and SGD find global minima in this setting, SGD induces a form of feature selection that GD lacks. By showing that SGD can find sharper yet potentially more useful sparse solutions, the paper challenges existing heuristics about the relationship between flatness and generalization, opening new avenues for understanding how stochasticity shapes neural network training.
Summary updated