Maximizing the robust margin provably overfits on noiseless data
Numerous recent works show that overparameterization implicitly reduces variance, suggesting vanishing benefits for explicit regularization in high dimensions. However, this narrative has been challenged by empirical observations indicating that adversarially trained deep neural networks suffer from robust overfitting. While existing explanations attribute this phenomenon to noise or problematic samples in the training data set, we prove that even on entirely noiseless data, achieving a vanishing adversarial logistic training loss is suboptimal compared to regularized counterparts.
Code (1)
Tasks
AttributeSimilar Papers 제목 키워드 기반
Margin Maximization as Lossless Maximal Compression
The ultimate goal of a supervised learning algorithm is to produce models constructed on the training data that can generalize well to new examples. In classification, functional margin maximization -- correctly classify…
General ClassificationAchieving Margin Maximization Exponentially Fast via Progressive Norm Rescaling
In this work, we investigate the margin-maximization bias exhibited by gradient-based algorithms in classifying linearly separable data. We present an in-depth analysis of the specific properties of the velocity field as…
Simple Alternating Minimization Provably Solves Complete Dictionary Learning
This paper focuses on the noiseless complete dictionary learning problem, where the goal is to represent a set of given signals as linear combinations of a small number of atoms from a learned dictionary. There are two m…
Dictionary LearningUnsupervised Visual Domain Adaptation: A Deep Max-Margin Gaussian Process Approach
In unsupervised domain adaptation, it is widely known that the target domain error can be provably reduced by having a shared input representation that makes the source and target domains indistinguishable from each othe…
Domain AdaptationGaussian ProcessesUnsupervised Domain AdaptationAlready Moderate Population Sizes Provably Yield Strong Robustness to Noise
Experience shows that typical evolutionary algorithms can cope well with stochastic disturbances such as noisy function evaluations. In this first mathematical runtime analysis of the $(1+\lambda)$ and $(1,\lambda)$ evol…
Evolutionary Algorithms