Improved optimization guarantees for deep learning models with Nesterov acceleration.
problem Optimization in non-convex deep learning landscapes.
method Analysis of Nesterov acceleration in benignly non-convex landscapes.
result Identical guarantees can be obtained in optimization problems with weak geometric assumptions, especially in overparametrized deep learning.
Heavy Ball method speeds up finding global optima in non-convex problems.
problem Finding global optima in non-convex optimization problems.
method Heavy Ball momentum in non-convex optimization.
result Heavy Ball helps iterates enter a benign region faster, containing a global optimal point.
WSFN overcomes saddle points for non-convex functionals in Wasserstein space.
problem Minimizing non-convex functionals over the Wasserstein space with saddle point avoidance.
method WSFN is a second-order method that preconditions the Wasserstein gradient to avoid saddle points.
result WSFN escapes saddle regions and reaches a global minimizer in polynomial time.
This work analyzes a two-stage algorithm for single index models, showing precise asymptotics of gradient descent.
problem Learning single index models with non-convex optimization.
method Spectral initialization followed by gradient descent, with detailed analysis of dynamics and asymptotics.
result Gradient descent converges to long-time fixed points in the large system limit, representing mean field behavior.
SGD converges to global minimum for certain non-convex functions.
problem Theoretical challenges in optimizing non-convex functions in machine learning.
method Perturbed SGD on a broad class of non-convex functions.
result SGD converges to global minimum for certain non-convex functions.
Paper proves global optimality of a simple optimization scheme for learning DAG models.
problem Learning acyclic directed graphical models from data.
method Path-following optimization scheme for bivariate setting.
result Simple optimization scheme globally converges to global minimum.
Deep learning methods find near-optimal solutions without explicit regularization.
problem Theoretical challenges in understanding deep learning's success.
method Analysis of gradient methods, overparametrization, and implicit regularization.
result Gradient methods can find near-optimal solutions and exhibit excellent predictive accuracy without explicit regularization.
Optimizes MMD learning for generative models with theoretical guarantees.
problem Theoretical guarantees for optimizing non-convex MMD objectives.
method Analyzes MMD optimization landscape for specific distributions.
result Gradient-based methods globally minimize MMD objective for certain distributions.
Study on benign overfitting in leaky ReLUs with moderate input dimensions.
problem Understanding when overfitting is beneficial in neural networks.
method Two-layer leaky ReLU networks trained with hinge loss, considering signal-to-noise ratio.
result Characterization of conditions for benign overfitting based on signal-to-noise ratio.
SGD generalizes well in high dimensions without regularization.
problem Generalization of overparameterized models in high dimensions.
method Stochastic Gradient Descent (SGD) for convex and locally convex loss functions.
result Generalization error is independent of the ambient dimension p under certain conditions. Attention models can overfit without harming test performance.
problem Understanding benign overfitting in single-head attention models.
method Analyzing conditions for benign overfitting in a single-head softmax attention model.
result A single-head attention model can overfit without harming test performance under certain conditions.
ResNet models overfit benignly on Cifar10 but not on ImageNet due to label noise.
problem Understanding why benign overfitting fails in real-world classification tasks with label noise.
method Theoretical analysis of benign overfitting under a mild overparameterization setup.
result Benign overfitting can fail in the presence of label noise, unlike in heavy overparameterization settings.
Paper finds conditions for benign overfitting in neural networks.
problem Benign overfitting in leaky ReLU two-layer neural networks.
method Established directional convergence and classification error bounds.
result Benign overfitting occurs with high probability on mixture data.
New insights into when benign overfitting occurs in linear and classification tasks.
problem Understanding when benign overfitting happens in linear and classification models.
method Analysis of a generic data model and comparison of predictors (minimum-norm interpolating and max-margin).
result The minimum-norm interpolating predictor is biased towards an inconsistent solution, preventing benign overfitting in linear regression.
Sharp condition found for Burer-Monteiro method to work for MaxCut-type SDPs.
problem MaxCut-type semidefinite programs with low-rank solutions.
method Sharp condition on Laplacian matrix conditioning for global minimizers of non-convex problem.
result Any second-order critical point is a global minimizer under the given condition.
The study examines when MAML's objective has a benign landscape.
problem Understanding when MAML's objective landscape is benign.
method Analyzing the landscape of MAML objective on LQR tasks.
result The benign landscape of the MAML objective depends on task similarities.
New insights into why neural networks can overfit without interpolating data.
problem Understanding why neural networks can overfit without interpolating data in fixed dimensions.
method Analyzing the smoothness of estimators and their derivatives.
result Benign overfitting is possible with estimators that have large enough derivatives, not just in high dimensions but also in fixed dimensions.
Study on size and depth of neural networks for approximating benign functions, showing barriers and explicit results.
problem Understanding how size and depth of neural networks affect their ability to approximate benign functions.
method Analyzing ReLU networks for benign functions, proving barriers and explicit results.
result Explicit benign functions that cannot be approximated by networks of certain sizes or depths, showing barriers to size and depth separation.
Two-layer CNNs can overfit without harm under certain conditions.
problem Understanding when and how overfitting occurs in neural networks.
method Theoretical analysis of a two-layer CNN trained by gradient descent.
result A sharp phase transition between benign and harmful overfitting based on signal-to-noise ratio.
Two-layer ReLU networks can overfit without harm, study finds.
problem Understanding when and how two-layer ReLU networks can overfit without harming generalization.
method Established algorithm-dependent risk bounds for two-layer ReLU convolutional neural networks with label-flipping noise.
result Gradient descent-trained ReLU networks can achieve near-zero training loss and Bayes optimal test risk.
Meta learning works well with overparameterized models, a phenomenon called 'benign overfitting'.
problem Understanding why overparameterized models perform well in few-shot learning.
method Analyzed the generalization performance of gradient-based meta learning with an overparameterized meta linear regression model.
result Demonstrated that overparameterized meta learning can still generalize well, a phenomenon called 'benign overfitting'.
Deep neural networks can generalize well even with perfect fits to noisy data.
problem Understanding the conditions under which deep neural networks generalize well in the presence of noise.
method Comprehensive study of linear maximum margin classifiers, focusing on noisy and noiseless cases.
result Discovery of a phase transition in test error bounds for the noisy model.
The paper explores how benign overfitting occurs in heavy-tailed input distributions.
problem Understanding overfitting in heavy-tailed input distributions.
method Analysis of maximum margin classifiers on unregularized logistic loss with gradient descent.
result Linear classifiers trained under certain conditions can asymptotically achieve the noise level as misclassification error.
New analysis shows bias term affects conditions for benign overfitting in linear classifiers.
problem Understanding conditions for good generalization in linear classifiers with bias terms.
method Extending Hashimoto et al.'s results to include bias terms, analyzing covariance structure and label noise.
result Benign overfitting persists in linear classifiers with bias terms, with new constraints on data's covariance structure.
The paper explores how noise in features can lead to benign overfitting in machine learning models.
problem Understanding the conditions for benign overfitting in machine learning models.
method Examined random feature models, specifically two-layer neural networks with fixed first layer weights, and analyzed the role of noise in features.
result Noise in features plays an important implicit regularization role in the phenomenon of benign overfitting.
Adversarial training can lead to overfitting without compromising robustness.
problem Explaining benign overfitting in adversarially robust linear classification.
method Theoretical analysis and numerical experiments on adversarial training.
result Adversarially trained linear classifiers can achieve near-optimal risks despite overfitting noisy data.
Neural networks can interpolate noisy data and still generalize well.
problem Generalization of neural networks trained on noisy data.
method Two-layer neural networks trained to interpolation by gradient descent on corrupted labels.
result Neural networks can achieve zero training error and optimal test error.
Unified framework explains why overfitting is benign in interpolating learning.
problem Understanding why overfitting is benign in highly overparameterized models.
method Spectral-transport stability framework.
result Sharp benign-overfitting criterion and explicit phase-transition rates.
The paper analyzes phase retrieval under limited samples, ensuring a benign local landscape for convergence.
problem Ensuring a benign local landscape for phase retrieval under limited samples.
method Fine-grained analysis of local landscape properties under the regime of limited samples.
result Gradient descent can converge to an od(1)-loss solution exponentially fast under certain conditions. Nonnegative low-rank matrix recovery can have spurious local minima.
problem Nonnegative low-rank matrix recovery problems can have spurious local minima.
method Investigated projected gradient methods for nonnegative low-rank recovery problems.
result Benign nonconvexity holds in the fully-observed case with RIP constant δ=0 but fails in the partially-observed case and higher-rank ground truths.
Study reveals learning curves and benign overfitting in spectral algorithms for large dimensions.
problem Understanding learning curves and benign overfitting in spectral algorithms for large-dimensional data.
method Analysis of learning curves and benign overfitting in spectral algorithms for inner-product kernels on the sphere and general domains.
result Characterization of three distinct regimes: over-regularized, under-regularized, and interpolation regimes, revealing benign overfitting across both under-regularized and interpolation regimes.
Linear models can overfit without harming OOD generalization under certain conditions.
problem Understanding how overparameterized linear models generalize to out-of-distribution data.
method Analyzing overparameterized linear models under covariate shift, providing guarantees for OOD generalization.
result Benign overfitting occurs in standard ridge regression under OOD conditions, with specific structural conditions on target covariance.
New study finds many neural networks are not benignly overfitting.
problem Understanding the behavior of overfitting in neural networks.
method Exploring kernel ridge regression and deep neural networks to identify overfitting behaviors.
result Many interpolating methods, including neural networks, exhibit tempered overfitting rather than benign or catastrophic.
ABO extends RLS for online learning in non-stationary time-series, improving accuracy and speed.
problem Online learning in non-stationary time-series with overparameterized models.
method QR-based exponentially weighted RLS algorithm with orthogonal-triangular updates.
result ABO maintains bounded residuals and stable condition numbers while achieving speed improvements.
The paper examines how spike strengths and alignments affect overfitting in linear regression models.
problem The impact of spike strengths and alignments on overfitting in linear regression models.
method Characterization of generalization error through exact expressions and analysis of spike strengths, aspect ratio, and target alignment.
result Increasing spike strength can lead to catastrophic overfitting before benign overfitting, especially in well-specified aligned problems.
New insights into how large models can interpolate noisy data and still generalize well.
problem Understanding how large models can interpolate noisy data and still generalize well.
method Conceptual shift focusing on almost benign overfitting, analyzing sample size and model complexity.
result Large models can achieve both good training fit and Bayes-optimal generalization even in classical regimes.
New research shows SVM and related methods can overfit without harm in multiclass classification.
problem Understanding benign overfitting in multiclass classification.
method Analyzing three training algorithms: ERM with cross-entropy, least-squares, and one-vs-all SVM.
result All three algorithms can lead to classifiers that interpolate training data and have equal accuracy under high overparameterization.
New insights into how linear classifiers and leaky ReLU networks can overfit without harming generalization.
problem Understanding conditions for benign overfitting in linear classifiers and leaky ReLU networks.
method Utilizing Karush--Kuhn--Tucker (KKT) conditions for margin maximization.
result Satisfaction of KKT conditions leads to benign overfitting in linear classifiers and leaky ReLU networks.
Deep learning models misclassify malware with added benign features.
problem Detecting malware with deep learning when it's mixed with benign code.
method Trained a deep neural network classifier using benign and malware features. Demonstrated the impact of adding benign features to malware. Used data augmentation to improve classifier robustness.
result Adding benign features to malware significantly increases false negatives.
New quantum kernels avoid overfitting by combining local and global components.
problem Exponential concentration in quantum kernels leads to overfitting.
method Local-global quantum kernels combining small subsystem and full-system measurements.
result Demonstrated benign overfitting in local-global quantum kernels.
New model leads to optimal test loss in sparse linear regression.
problem Sparse linear regression with low test loss despite interpolating training data.
method Developed a new parametrization of the model that combines benefits of ℓ1 and ℓ2 norms.
result Training via gradient descent leads to an interpolator with near-optimal test loss.
The phenomenon of benign overfitting is one of the key mysteries uncovered by deep learning methodology: deep neural networks seem to predict well, even with a perfect fit to noisy training data. Motivated by this phenomenon, we consider when a perfect fit to training data in linear regression is compatible with accura…
Study shows how over-parameterized classifiers can still perform well on noisy data.
problem Understanding how maximum margin classifiers perform in over-parameterized settings with noisy data.
method Analyzes maximum margin classifiers on sub-Gaussian mixtures, providing risk bounds.
result Characterizes conditions for 'benign overfitting' in linear classification problems.
This work characterizes benign overfitting in Vision Transformers.
problem Understanding generalization of Vision Transformers when trained to overfit.
method Gradient descent on a data distribution model, focusing on self-attention layer and softmax.
result Established a condition to distinguish between small and large test errors based on signal-to-noise ratio.
Deep networks can overfit benignly but still be vulnerable to adversarial attacks.
problem Adversarial vulnerability of deep neural networks trained with benign overfitting.
method Investigated causes of adversarial vulnerability, identified label noise as a key factor, and explored the impact of training procedures and representation learning.
result Adversarial robustness requires more complex decision boundaries than simple ones, suggesting the need for better representation learning.
Uniform convergence of interpolators proven for Gaussian data.
problem Interpolation learning in high-dimensional linear regression with Gaussian data.
method Generic uniform convergence guarantee in terms of Gaussian width.
result Consistency of interpolators for minimum-norm and near-minimal-norm cases.
Study shows linear models can predict CATE without overfitting, even with large data.
problem Overfitting in large-scale causal inference models.
method Investigated linear models for CATE prediction, considering samples with switching distributions.
result IPW-learner converges risk to zero if propensity score is known, while T-learner fails to achieve consistency.
New findings on how neural networks generalize with varying dimensions.
problem Understanding how neural networks generalize with different dimensions and noise levels.
method Study of 2-layer ReLU NNs in a classification setting, proving transitions in overfitting types.
result The type of overfitting transitions from tempered to benign as input dimension increases.