A unified law of robustness for Bregman divergence losses

• URL: http://arxiv.org/abs/2405.16639v3
• Date: Fri, 6 Sep 2024 07:24:18 GMT
• Title: A unified law of robustness for Bregman divergence losses
• Authors: Santanu Das, Jatin Batra, Piyush Srivastava,
• Abstract summary: We show that Bregman divergence losses form a common generalization of square loss and cross-entropy loss. Our generalization relies on identifying a bias-variance type decomposition that lies at the heart of the proof and Bubeck and Sellke.
• Score: 2.014089835498735
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In contemporary deep learning practice, models are often trained to near zero loss i.e. to nearly interpolate the training data. However, the number of parameters in the model is usually far more than the number of data points $n$, the theoretical minimum needed for interpolation: a phenomenon referred to as overparameterization. In an interesting piece of work that contributes to the considerable research that has been devoted to understand overparameterization, Bubeck and Sellke showed that for a broad class of covariate distributions (specifically those satisfying a natural notion of concentration of measure), overparameterization is necessary for robust interpolation i.e. if the interpolating function is required to be Lipschitz. However, their robustness results were proved only in the setting of regression with square loss. In practice, however many other kinds of losses are used, e.g. cross entropy loss for classification. In this work, we generalize Bubeck and Selke's result to Bregman divergence losses, which form a common generalization of square loss and cross-entropy loss. Our generalization relies on identifying a bias-variance type decomposition that lies at the heart of the proof and Bubeck and Sellke.

Related papers

• Towards Self-Supervised Covariance Estimation in Deep Heteroscedastic Regression [102.24287051757469]
  We study self-supervised covariance estimation in deep heteroscedastic regression. We derive an upper bound on the 2-Wasserstein distance between normal distributions. Experiments over a wide range of synthetic and real datasets demonstrate that the proposed 2-Wasserstein bound coupled with pseudo label annotations results in a computationally cheaper yet accurate deep heteroscedastic regression.
  arXiv  Detail & Related papers  (2025-02-14T22:37:11Z)
• Bias-variance decompositions: the exclusive privilege of Bregman divergences [0.8158530638728501]
  We study continuous, nonnegative loss functions that satisfy the identity of indiscernibles under mild regularity conditions. A $g$-Bregman divergence can be transformed into a standard Bregman divergence through an invertible change of variables.
  arXiv  Detail & Related papers  (2025-01-30T18:52:44Z)
• Generalization bounds for regression and classification on adaptive covering input domains [1.4141453107129398]
  We focus on the generalization bound, which serves as an upper limit for the generalization error. In the case of classification tasks, we treat the target function as a one-hot, a piece-wise constant function, and employ 0/1 loss for error measurement.
  arXiv  Detail & Related papers  (2024-07-29T05:40:08Z)
• Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise [51.87307904567702]
  Quantile regression is a leading approach for obtaining such intervals via the empirical estimation of quantiles in the distribution of outputs. We propose Relaxed Quantile Regression (RQR), a direct alternative to quantile regression based interval construction that removes this arbitrary constraint. We demonstrate that this added flexibility results in intervals with an improvement in desirable qualities.
  arXiv  Detail & Related papers  (2024-06-05T13:36:38Z)
• A U-turn on Double Descent: Rethinking Parameter Counting in Statistical Learning [68.76846801719095]
  We show that double descent appears exactly when and where it occurs, and that its location is not inherently tied to the threshold p=n. This provides a resolution to tensions between double descent and statistical intuition.
  arXiv  Detail & Related papers  (2023-10-29T12:05:39Z)
• Regularization properties of adversarially-trained linear regression [5.7077257711082785]
  State-of-the-art machine learning models can be vulnerable to very small input perturbations. Adversarial training is an effective approach to defend against it.
  arXiv  Detail & Related papers  (2023-10-16T20:09:58Z)
• Structured Radial Basis Function Network: Modelling Diversity for Multiple Hypotheses Prediction [51.82628081279621]
  Multi-modal regression is important in forecasting nonstationary processes or with a complex mixture of distributions. A Structured Radial Basis Function Network is presented as an ensemble of multiple hypotheses predictors for regression problems. It is proved that this structured model can efficiently interpolate this tessellation and approximate the multiple hypotheses target distribution.
  arXiv  Detail & Related papers  (2023-09-02T01:27:53Z)
• Robust Bayesian Inference for Berkson and Classical Measurement Error Models [9.712913056924826]
  We propose a nonparametric framework for dealing with measurement error. It is suitable for both Classical and Berkson error models. It offers flexibility in the choice of loss function depending on the type of regression model.
  arXiv  Detail & Related papers  (2023-06-02T11:48:15Z)
• Cut your Losses with Squentropy [19.924900110707284]
  We propose the "squentropy" loss, which is the sum of two terms: the cross-entropy loss and the average square loss over the incorrect classes. We show that the squentropy loss outperforms both the pure cross entropy and rescaled square losses in terms of the classification accuracy.
  arXiv  Detail & Related papers  (2023-02-08T09:21:13Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. We derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.
  arXiv  Detail & Related papers  (2022-11-02T16:39:42Z)
• More is Less: Inducing Sparsity via Overparameterization [2.885175627590247]
  In deep learning it is common to over parameterize neural networks, that is, to use more parameters than training samples. Quite surprisingly, generalize the neural network via (stochastic) gradient descent leads to that very well. Our proof relies on analyzing a certain Bregman divergence of the flow.
  arXiv  Detail & Related papers  (2021-12-21T07:55:55Z)
• Understanding Square Loss in Training Overparametrized Neural Network Classifiers [31.319145959402462]
  We contribute to the theoretical understanding of square loss in classification by systematically investigating how it performs for overparametrized neural networks. We consider two cases, according to whether classes are separable or not. In the general non-separable case, fast convergence rate is established for both misclassification rate and calibration error. The resulting margin is proven to be lower bounded away from zero, providing theoretical guarantees for robustness.
  arXiv  Detail & Related papers  (2021-12-07T12:12:30Z)
• Interpolation can hurt robust generalization even when there is no noise [76.3492338989419]
  We show that avoiding generalization through ridge regularization can significantly improve generalization even in the absence of noise. We prove this phenomenon for the robust risk of both linear regression and classification and hence provide the first theoretical result on robust overfitting.
  arXiv  Detail & Related papers  (2021-08-05T23:04:15Z)
• KL Guided Domain Adaptation [88.19298405363452]
  Domain adaptation is an important problem and often needed for real-world applications. A common approach in the domain adaptation literature is to learn a representation of the input that has the same distributions over the source and the target domain. We show that with a probabilistic representation network, the KL term can be estimated efficiently via minibatch samples.
  arXiv  Detail & Related papers  (2021-06-14T22:24:23Z)
• Fundamental Limits and Tradeoffs in Invariant Representation Learning [99.2368462915979]
  Many machine learning applications involve learning representations that achieve two competing goals. Minimax game-theoretic formulation represents a fundamental tradeoff between accuracy and invariance. We provide an information-theoretic analysis of this general and important problem under both classification and regression settings.
  arXiv  Detail & Related papers  (2020-12-19T15:24:04Z)
• Implicit Regularization in ReLU Networks with the Square Loss [56.70360094597169]
  We show that it is impossible to characterize the implicit regularization with the square loss by any explicit function of the model parameters. Our results suggest that a more general framework may be needed to understand implicit regularization for nonlinear predictors.
  arXiv  Detail & Related papers  (2020-12-09T16:48:03Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  We consider the fundamental problem of ReLU regression. The goal is to output the best fitting ReLU with respect to square loss given to draws from some unknown distribution.
  arXiv  Detail & Related papers  (2020-05-26T16:26:17Z)
• Classification vs regression in overparameterized regimes: Does the loss function matter? [21.75115239010008]
  We show that solutions obtained by least-squares minimum-norm, typically used for regression, are identical to those produced by the hard-margin support vector machine (SVM) Our results demonstrate the very different roles and properties of loss functions used at the training phase (optimization) and the testing phase (generalization)
  arXiv  Detail & Related papers  (2020-05-16T17:58:25Z)
• Imputation for High-Dimensional Linear Regression [8.841513006680886]
  We show that LASSO retains the minimax estimation rate in the random setting. We show that the co-root remains mphmph in this setting.
  arXiv  Detail & Related papers  (2020-01-24T19:54:09Z)

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.