The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learning

Wooseok Ha, Spencer Frei, Nikhil Ghosh, Bin Yu

TL;DR

Training a single-neuron autoencoder on orthogonal data using stochastic gradient descent (SGD) vs. full-batch gradient descent (GD) leads to completely different global minima. While full-batch GD converges to a dense mixture that barely deviates from its random initialization, mini-batch SGD acts as a "feature selector," converging almost surely to a single, 1-sparse data point. Surprisingly, the solutions found by SGD are strictly sharper (measured by Hessian trace) than those found by GD, challenging conventional deep learning folklore about flat minima.

What Problem Does This Paper Address?

In deep learning practice, small-batch SGD systematically outperforms large-batch GD in generalization. A widespread hypothesis attributes this to optimization geometry: mini-batch noise supposedly nudges training toward "flatter" minima.

However, existing theory often relies on unrealistic simplifications—such as modeling gradient noise as synthetic isotropic/label Gaussian noise or analyzing continuous-time gradient flows with infinitesimally small learning rates. The authors ask: Can standard mini-batch SGD with a constant step size provably converge to a qualitatively different global minimum than GD in non-convex settings, and does it actually prefer flatter minima?

Methods

The authors analyze a single-neuron weight-tied autoencoder: $$f(x; w) = w\,\phi(\langle w, x\rangle)$$ where $\phi$ is either the identity (linear) or ReLU activation, trained with squared reconstruction error on orthogonal data vectors $\{a_1, \dots, a_m\} \subset \mathbb{R}^n$.

  • Coordinate Evolution: Updates are tracked along data directions $c_t(i) = \langle w_t, a_i \rangle$.
  • Non-Homogeneous Random Walks: To prove constant step-size SGD convergence without step-size decay (a notoriously difficult open problem in non-convex optimization), the authors formulate the log-ratio of the top coordinate to the rest as a 1D stochastic process: $$R_t = \log \left( \frac{|c_t(i_t^*)|}{\sum_{\ell \neq i_t^*} |c_t(\ell)|} \right)$$ Using tools from probability theory (Menshikov & Wade, 2010), they prove this process is transient ($R_t \to \infty$ almost surely), establishing that SGD's last iterate collapses onto a single coordinate.

Datasets

Because this is a pure theoretical study, no empirical benchmark datasets (e.g., CIFAR, ImageNet) are used. The training dataset $\mathcal{D} = \{a_1, \dots, a_m\}$ consists of $m$ orthonormal vectors in $\mathbb{R}^n$ ($m \le n$), representing an orthogonal dictionary under a sparse coding model with 1-hot latent codes.

Key Insights and Ideas

  • Symmetry vs. Symmetry Breaking: Under full-batch GD, the update ratio $c_{t+1}(i) / c_t(i)$ is identical for every data coordinate. GD preserves the relative ratios set at initialization: it simply projects $w_0$ onto the data span and rescales it to unit norm. Under mini-batch SGD ($b < m$), subsampling repeatedly amplifies the mini-batch's dominant coordinate over excluded ones, triggering a "rich-get-richer" dynamic that breaks the symmetry.
  • Feature Learning vs. "Lazy" Regime: For random Gaussian initialization $w_0 \sim \mathcal{N}(0, \frac{\sigma^2}{n} I_n)$:
  • GD produces a dense mixture highly correlated with initialization ($\text{cossim}(w_{\text{GD}}, w_0) = \Theta(m/n)$) and poorly correlated with individual data points ($O(\sqrt{\log m / m})$).
  • SGD selects an exact data point ($\text{cossim}(w_{\text{SGD}}, \mathcal{D}) = 1$) and ends up nearly orthogonal to initialization ($O(\sqrt{\log m / n})$), demonstrating genuine data-dependent feature learning.
  • Flatter Isn't Always Better (or True for SGD): Deep learning intuition holds that small batches favor flatter minima. Here, measuring sharpness via the trace of the Hessian (generalized via one-sided derivatives for ReLU), SGD converges to a strictly sharper minimum than GD: $$\text{Tr}(H_{\text{SGD}}) \approx \text{Tr}(H_{\text{GD}}) + \frac{1}{2}$$ Both share the identical top eigenvalue ($\|H\|_2 = 4/m$), meaning standard spectral sharpness metrics fail to explain SGD's implicit bias here.

  • Batch Size Over Randomness: The authors show that cyclic SGD (deterministic alternating single-sample updates) also converges to a 1-sparse solution in $\mathbb{R}^2$. This implies that batch size itself—rather than gradient stochasticity alone—drives coordinate competition.

Key Results

  • Global Convergence: Under step size $0 < \eta \le 1/5$ and $\|w_0\| < 1$, both GD and SGD converge to the global minimum loss value of $\frac{m-1}{2m}$.
  • SGD Limit: For any batch size $b < m$, $w_t \to \text{sign}(\langle w_0, a_{i^*} \rangle) a_{i^*}$ almost surely for some $i^* \in [m]$.
  • Sharpness Discrepancy: For ReLU activations with Gaussian initialization ($|S^+| \approx m/2$): $$\text{Tr}(H_{\text{GD}}) = \frac{2n + 8 - m - |S^+|}{2m} \approx \frac{2n + 8 - 1.5m}{2m}$$ $$\text{Tr}(H_{\text{SGD}}) = \frac{2n + 7 - m}{2m}$$ Thus, $\text{Tr}(H_{\text{SGD}}) > \text{Tr}(H_{\text{GD}})$.

Limitations and Future Work

  • Stylized Model: The setup is restricted to a single neuron with weight tying on orthonormal data. Generalization error to unseen data cannot be directly evaluated because any orthogonal test point remains unlearned.
  • Uncertain Limit Distribution: While SGD provably converges to an individual data point $a_i$, the exact probability distribution over which $a_i$ is chosen is not determined.
  • Cyclic SGD Scope: The convergence of deterministic cyclic SGD is proven only for the 2D case ($m=n=2$).
  • Future Work: Extending the non-homogeneous random walk framework to multi-neuron architectures, deep networks, and classification losses, as well as obtaining explicit convergence rates.

Summary updated

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.
BibTeX
@misc{ha2023effect,
  author = {Wooseok Ha and Spencer Frei and Nikhil Ghosh and Bin Yu},
  title = {{The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learning}},
  year = {2023},
  eprint = {2308.03215},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2308.03215},
}

Loading related content...

Figure