Online Learning and Information Exponents: On The Importance of Batch size, and Time/Complexity Tradeoffs
<|reference_start|>Online Learning and Information Exponents: On The Importance of Batch size, and Time/Complexity Tradeoffs: We study the impact of the batch size $n_b$ on the iteration time $T$ of training two-layer neural networks with one-pass stochastic gradient descent (SGD) on multi-index target functions of isotropic covariates. We characterize the optimal batch size minimizing the iteration time as a function of the hardness of the target, as characterized by the information exponents. We show that performing gradient updates with large batches $n_b \lesssim d^{\frac{\ell}{2}}$ minimizes the training time without changing the total sample complexity, where $\ell$ is the information exponent of the target to be learned \citep{arous2021online} and $d$ is the input dimension. However, larger batch sizes than $n_b \gg d^{\frac{\ell}{2}}$ are detrimental for improving the time complexity of SGD. We provably overcome this fundamental limitation via a different training protocol, \textit{Correlation loss SGD}, which suppresses the auto-correlation terms in the loss function. We show that one can track the training progress by a system of low-dimensional ordinary differential equations (ODEs). Finally, we validate our theoretical results with numerical experiments.<|reference_end|>
@article{arnaboldi2024online,
    title={Online Learning and Information Exponents: On The Importance of Batch
  size, and Time/Complexity Tradeoffs},
    author={Luca Arnaboldi, Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca
  Pesce, Ludovic Stephan},
    journal={Proceedings of the 41st International Conference on Machine
  Learning, PMLR 235:1730-1762, 2024},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.02157},
    primaryClass={stat.ML cs.LG}
}