The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents

• URL: http://arxiv.org/abs/2402.03220v3
• Date: Sun, 30 Jun 2024 17:01:45 GMT
• Title: The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents
• Authors: Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka Zdeborová, Florent Krzakala,
• Abstract summary: We investigate the training dynamics of two-layer neural networks when learning multi-index target functions. We focus on multi-pass gradient descent (GD) that reuses the batches multiple times and show that it significantly changes the conclusion about which functions are learnable. We show that upon re-using batches, the network achieves in just two time steps an overlap with the target subspace even for functions not satisfying the staircase property.
• Score: 28.102697445508976
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the training dynamics of two-layer neural networks when learning multi-index target functions. We focus on multi-pass gradient descent (GD) that reuses the batches multiple times and show that it significantly changes the conclusion about which functions are learnable compared to single-pass gradient descent. In particular, multi-pass GD with finite stepsize is found to overcome the limitations of gradient flow and single-pass GD given by the information exponent (Ben Arous et al., 2021) and leap exponent (Abbe et al., 2023) of the target function. We show that upon re-using batches, the network achieves in just two time steps an overlap with the target subspace even for functions not satisfying the staircase property (Abbe et al., 2021). We characterize the (broad) class of functions efficiently learned in finite time. The proof of our results is based on the analysis of the Dynamical Mean-Field Theory (DMFT). We further provide a closed-form description of the dynamical process of the low-dimensional projections of the weights, and numerical experiments illustrating the theory.

Related papers

• Dynamic Decoupling of Placid Terminal Attractor-based Gradient Descent Algorithm [56.06235614890066]
  Gradient descent (GD) and gradient descent (SGD) have been widely used in a number of application domains. This paper carefully analyzes the dynamics of GD based on the terminal attractor at different stages of its gradient flow.
  arXiv  Detail & Related papers  (2024-09-10T14:15:56Z)
• Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions [20.036783417617652]
  We investigate the training dynamics of two-layer shallow neural networks trained with gradient-based algorithms. We show that a simple modification of the idealized single-pass gradient descent training scenario drastically improves its computational efficiency. Our results highlight the ability of networks to learn relevant structures from data alone without any pre-processing.
  arXiv  Detail & Related papers  (2024-05-24T11:34:31Z)
• Asymptotics of feature learning in two-layer networks after one gradient-step [39.02152620420932]
  We investigate how two-layer neural networks learn from data, and improve over the kernel regime. We model the trained network by a spiked Random Features (sRF) model. We provide an exact description of the generalization error of the sRF in the high-dimensional limit.
  arXiv  Detail & Related papers  (2024-02-07T15:57:30Z)
• Layer-wise Feedback Propagation [53.00944147633484]
  We present Layer-wise Feedback Propagation (LFP), a novel training approach for neural-network-like predictors. LFP assigns rewards to individual connections based on their respective contributions to solving a given task. We demonstrate its effectiveness in achieving comparable performance to gradient descent on various models and datasets.
  arXiv  Detail & Related papers  (2023-08-23T10:48:28Z)
• Implicit Stochastic Gradient Descent for Training Physics-informed Neural Networks [51.92362217307946]
  Physics-informed neural networks (PINNs) have effectively been demonstrated in solving forward and inverse differential equation problems. PINNs are trapped in training failures when the target functions to be approximated exhibit high-frequency or multi-scale features. In this paper, we propose to employ implicit gradient descent (ISGD) method to train PINNs for improving the stability of training process.
  arXiv  Detail & Related papers  (2023-03-03T08:17:47Z)
• The Equalization Losses: Gradient-Driven Training for Long-tailed Object Recognition [84.51875325962061]
  We propose a gradient-driven training mechanism to tackle the long-tail problem. We introduce a new family of gradient-driven loss functions, namely equalization losses. Our method consistently outperforms the baseline models.
  arXiv  Detail & Related papers  (2022-10-11T16:00:36Z)
• On the non-universality of deep learning: quantifying the cost of symmetry [24.86176236641865]
  We prove computational limitations for learning with neural networks trained by noisy gradient descent (GD) We characterize functions that fully-connected networks can weak-learn on the binary hypercube and unit sphere. Our techniques extend to gradient descent (SGD), for which we show nontrivial results for learning with fully-connected networks.
  arXiv  Detail & Related papers  (2022-08-05T11:54:52Z)
• FOSTER: Feature Boosting and Compression for Class-Incremental Learning [52.603520403933985]
  Deep neural networks suffer from catastrophic forgetting when learning new categories. We propose a novel two-stage learning paradigm FOSTER, empowering the model to learn new categories adaptively.
  arXiv  Detail & Related papers  (2022-04-10T11:38:33Z)
• Mean-field Analysis of Piecewise Linear Solutions for Wide ReLU Networks [83.58049517083138]
  We consider a two-layer ReLU network trained via gradient descent. We show that SGD is biased towards a simple solution. We also provide empirical evidence that knots at locations distinct from the data points might occur.
  arXiv  Detail & Related papers  (2021-11-03T15:14:20Z)
• The Impact of the Mini-batch Size on the Variance of Gradients in Stochastic Gradient Descent [28.148743710421932]
  The mini-batch gradient descent (SGD) algorithm is widely used in training machine learning models. We study SGD dynamics under linear regression and two-layer linear networks, with an easy extension to deeper linear networks.
  arXiv  Detail & Related papers  (2020-04-27T20:06:11Z)
• Investigating the interaction between gradient-only line searches and different activation functions [0.0]
  Gradient-only line searches (GOLS) adaptively determine step sizes along search directions for discontinuous loss functions in neural network training. We find that GOLS are robust for a range of activation functions, but sensitive to the Rectified Linear Unit (ReLU) activation function in standard feedforward architectures.
  arXiv  Detail & Related papers  (2020-02-23T12:28:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.