Noisy Interpolation Learning with Shallow Univariate ReLU Networks

• URL: http://arxiv.org/abs/2307.15396v3
• Date: Thu, 21 Mar 2024 23:38:52 GMT
• Title: Noisy Interpolation Learning with Shallow Univariate ReLU Networks
• Authors: Nirmit Joshi, Gal Vardi, Nathan Srebro,
• Abstract summary: Mallinar et. al. 2022 noted that neural networks seem to often exhibit tempered overfitting'', wherein the population risk does not converge to the Bayes optimal error. We provide the first rigorous analysis of the overfitting behavior of regression with minimum weights.
• Score: 33.900009202637285
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Understanding how overparameterized neural networks generalize despite perfect interpolation of noisy training data is a fundamental question. Mallinar et. al. 2022 noted that neural networks seem to often exhibit ``tempered overfitting'', wherein the population risk does not converge to the Bayes optimal error, but neither does it approach infinity, yielding non-trivial generalization. However, this has not been studied rigorously. We provide the first rigorous analysis of the overfitting behavior of regression with minimum norm ($\ell_2$ of weights), focusing on univariate two-layer ReLU networks. We show overfitting is tempered (with high probability) when measured with respect to the $L_1$ loss, but also show that the situation is more complex than suggested by Mallinar et. al., and overfitting is catastrophic with respect to the $L_2$ loss, or when taking an expectation over the training set.

Related papers

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:19:27Z)
• Deep learning from strongly mixing observations: Sparse-penalized regularization and minimax optimality [0.0]
  We consider sparse-penalized regularization for deep neural network predictor. We deal with the squared and a broad class of loss functions.
  arXiv  Detail & Related papers  (2024-06-12T15:21:51Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it. In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
  arXiv  Detail & Related papers  (2023-11-18T04:41:07Z)
• Theoretical Characterization of the Generalization Performance of Overfitted Meta-Learning [70.52689048213398]
  This paper studies the performance of overfitted meta-learning under a linear regression model with Gaussian features. We find new and interesting properties that do not exist in single-task linear regression. Our analysis suggests that benign overfitting is more significant and easier to observe when the noise and the diversity/fluctuation of the ground truth of each training task are large.
  arXiv  Detail & Related papers  (2023-04-09T20:36:13Z)
• Benign Overfitting for Two-layer ReLU Convolutional Neural Networks [60.19739010031304]
  We establish algorithm-dependent risk bounds for learning two-layer ReLU convolutional neural networks with label-flipping noise. We show that, under mild conditions, the neural network trained by gradient descent can achieve near-zero training loss and Bayes optimal test risk.
  arXiv  Detail & Related papers  (2023-03-07T18:59:38Z)
• Semantic Strengthening of Neuro-Symbolic Learning [85.6195120593625]
  Neuro-symbolic approaches typically resort to fuzzy approximations of a probabilistic objective. We show how to compute this efficiently for tractable circuits. We test our approach on three tasks: predicting a minimum-cost path in Warcraft, predicting a minimum-cost perfect matching, and solving Sudoku puzzles.
  arXiv  Detail & Related papers  (2023-02-28T00:04:22Z)
• Implicit Regularization Leads to Benign Overfitting for Sparse Linear Regression [16.551664358490658]
  In deep learning, often the training process finds an interpolator (a solution with 0 training loss) but the test loss is still low. One common mechanism for benign overfitting is implicit regularization, where the training process leads to additional properties for the interpolator. We show that training our new model via gradient descent leads to an interpolator with near-optimal test loss.
  arXiv  Detail & Related papers  (2023-02-01T05:41:41Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  Modern machine learning models often employ a huge number of parameters and are typically optimized to have zero training loss. We examine how these benign overfitting phenomena occur in a two-layer neural network setting. We show that it is possible for the two-layer ReLU network interpolator to achieve a near minimax-optimal learning rate.
  arXiv  Detail & Related papers  (2021-06-06T19:08:53Z)
• An efficient projection neural network for $\ell_1$-regularized logistic regression [10.517079029721257]
  This paper presents a simple projection neural network for $ell_$-regularized logistics regression. The proposed neural network does not require any extra auxiliary variable nor any smooth approximation. We also investigate the convergence of the proposed neural network by using the Lyapunov theory and show that it converges to a solution of the problem with any arbitrary initial value.
  arXiv  Detail & Related papers  (2021-05-12T06:13:44Z)
• Structure Learning in Inverse Ising Problems Using $\ell_2$-Regularized Linear Estimator [8.89493507314525]
  We show that despite the model mismatch, one can perfectly identify the network structure using naive linear regression without regularization. We propose a two-stage estimator: In the first stage, the ridge regression is used and the estimates are pruned by a relatively small threshold. This estimator with the appropriate regularization coefficient and thresholds is shown to achieve the perfect identification of the network structure even in $0M/N1$.
  arXiv  Detail & Related papers  (2020-08-19T09:11:33Z)

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.