Study on noisy gradient descent in higher-dimensional minima.
problem Behavior of gradient descent in higher codimension.
method Computer experiments with noisy gradient descent.
result Effects of noise on gradient descent trajectories in higher codimension.
Study on privacy leakage in noisy gradient descent algorithms.
problem Information leakage of iterative randomized learning algorithms about training data.
method Analyzes the dynamics of Rényi differential privacy loss in noisy gradient descent algorithms.
result Privacy loss converges exponentially fast for smooth and strongly convex loss functions.
Deep learning models can overfit noisy data without losing generalization.
problem Understanding the generalization of deep learning models in noisy data.
method Empirical investigation of epoch-wise double descent in fully connected neural networks trained on CIFAR-10 with 30% label noise.
result The model achieves strong re-generalization on test data after overfitting noisy training data, corresponding to a 'benign overfitting' state.
Preconditioned non-convex gradient descent improves noisy matrix estimation.
problem Estimating low-rank matrices from noisy measurements.
method Preconditioned non-convex gradient descent for noisy measurements.
result Preconditioned method converges to minimax optimal estimate at a linear rate.
Deep learning with noisy gradient descent outperforms linear estimators in high dimensions.
problem Theoretical explanation of deep learning's superiority over linear methods.
method Theoretical analysis of excess risk of a deep learning estimator trained by noisy gradient descent.
result Deep learning achieves a faster learning rate than linear estimators, especially in high dimensions.
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.
Paper studies early-stopped mirror descent for noisy sparse phase retrieval.
problem Recovering a sparse signal from noisy quadratic measurements.
method Early-stopped mirror descent with hyperbolic entropy mirror map.
result Achieves nearly minimax-optimal rate of convergence for k-sparse signals. AGNES accelerates gradient descent with noisy gradients.
problem Minimizing smooth convex and strongly convex functions with noisy gradients.
method Generalization of Nesterov's accelerated gradient descent algorithm for noisy conditions.
result AGNES achieves acceleration for noisy gradients with a constant of proportionality up to 1.
New method improves convergence and reduces variance in noisy optimization problems.
problem Computing exact minimizers with noisy gradient information.
method Stochastic mirror descent with interacting particles.
result Interaction helps improve convergence and reduce variance.
Proposes coreset method for robust training of neural networks with noisy labels.
problem Overfitting of neural networks trained with noisy labels.
method Selects weighted subsets (coresets) of clean data points to approximate low-rank Jacobian matrix.
result Gradient descent applied to coreset subsets does not overfit noisy labels.
In this note, we observe the behavior of gradient flow and discrete and noisy gradient descent in some simple settings. It is commonly noted that addition of noise to gradient descent can affect the trajectory of gradient descent. Here, we run some computer experiments for gradient descent on some simple functions, and…
Deep networks can interpolate noisy data without losing generalization.
problem Characterizing the relationship between interpolation and generalization in overparameterized deep networks.
method Analyzing the loss landscape of neural network functions over volumes around training data points, varying model parameters and training epochs.
result Loss sharpness in the input space follows a double descent, with large models predicting noisy targets over larger volumes around training data points.
A method to learn from noisy labels without a clean validation set.
problem Learning from samples with noisy labels.
method Limited Gradient Descent: modifying labels to estimate optimal stopping timing.
result Comparable and sometimes superior generalization performance compared to methods relying on clean validation sets.
Paper analyzes gradient descent with noisy data copies for linear regression, showing regularization and acceleration effects.
problem Improving generalization in machine learning through data augmentation with noise.
method Gradient descent with on-line noisy copies for linear regression analysis.
result Training with on-line noisy copies is equivalent to ridge regularization with a specific regularization parameter.
Paper tackles private optimization for non-smooth objectives efficiently.
problem Private stochastic convex optimization for non-smooth objectives.
method Noisy mirror descent algorithm.
result Achieves optimal rates in statistical complexity and number of queries.
New findings show noisy gradient descent can generalize well, even with non-SGD noise.
problem The role of noise in gradient descent's generalization ability.
method Analyzed the structure of SGD noise and proposed a new noisy gradient descent algorithm.
result Noises in classes different from SGD can also effectively regularize gradient descent.
Theory and method for reducing prediction variance in noisy feature-subsampled ridge ensembles.
problem Reduction of prediction variance in noisy data with feature bagging.
method Developed analytical learning curves for noisy ridge ensembles, introduced heterogeneous feature ensembling.
result Subsampling shifts the double-descent peak, leading to improved performance over a single linear predictor.
Gradient descent with early stopping works well even with noisy labels in overparameterized neural networks.
problem Label noise in neural networks trained with overparameterized models.
method Gradient descent with early stopping, under a rich dataset model.
result Gradient descent with early stopping is robust to a constant fraction of noisy labels.
A new method for robust training under label noise using weighted gradient descent.
problem Overfitting to noisy examples in machine learning.
method Exponentiated gradient reweighting for flexible handling of noisy data.
result Improved generalization in noisy classification and PCA problems.
APGD algorithm efficiently recovers over-parameterized matrices from noisy measurements.
problem Matrix sensing problem with over-parameterization and noisy measurements.
method Alternating preconditioned gradient descent (APGD) algorithm incorporating preconditioning terms.
result APGD converges to a near-optimal error at a linear rate.
FGD reduces noisy gradient variance in SGD for neural networks.
problem Noisy and unreliable gradient estimation in SGD for deep learning.
method Solves an adaptive filtering problem to consistently estimate the local gradient.
result Significantly reduces gradient variance and accelerates convergence.
Regression models can interpolate noisy data and still perform well, contrary to the bias-variance tradeoff.
problem Understanding why overparametrized models can generalize well despite the bias-variance tradeoff.
method Analysis of minimum norm solutions and ridge regression, focusing on the smallest singular value of the regression matrix.
result Testing error exhibits double descent behavior as model order increases, contrary to the classical bias-variance tradeoff.
The study examines denoising and noisy-input regression under distribution shift, revealing double descent behavior and insights for data augmentation.
problem Understanding denoising in machine learning, especially under noisy inputs and distribution shift.
method Theoretical analysis of supervised denoising and noisy-input regression, considering low-rank data and proportional regime.
result The test error exhibits double descent under general distribution shift, indicating that overfitting the noise can be benign, tempered, or catastrophic.
PEGR improves deep learning models' robustness against noisy data.
problem Learning signals from noisy data in deep learning models.
method Per-example gradient regularization (PEGR) to suppress noise.
result PEGR enhances test error and robustness against noise perturbations.
It has been observed in a variety of contexts that gradient descent methods have great success in solving low-rank matrix factorization problems, despite the relevant problem formulation being non-convex. We tackle a particular instance of this scenario, where we seek the d-dimensional subspace spanned by a streaming…
Paper introduces a neural network training algorithm for noisy data that achieves optimal parameters and replicates real-world behaviors.
problem Theoretical gap between universal approximation theorems and practical machine learning with noisy data.
method Randomized training algorithm for neural networks trained on noisy data samples.
result Trained neural networks achieve optimal parameters and exhibit real-world behaviors like sub-linear complexity and interpolation.
The paper analyzes generalization of noisy iterative algorithms using communication theory.
problem Generalization of models trained by noisy iterative algorithms under different distributions.
method Connecting noisy iterative algorithms to additive noise channels in communication theory.
result Distribution-dependent generalization bounds for noisy iterative algorithms.
Although the standard formulations of prediction problems involve fully-observed and noiseless data drawn in an i.i.d. manner, many applications involve noisy and/or missing data, possibly involving dependence, as well. We study these issues in the context of high-dimensional sparse linear regression, and propose novel…
ConvMMD improves inference in noisy data.
problem Inference degradation due to measurement error in noisy data.
method Convolutional Maximum Mean Discrepancy (convMMD) for inference with noisy, heteroscedastic observations.
result Established consistency and asymptotic normality of the convMMD-based estimator.
Generalizes neural tangent kernel analysis for two-layer networks with noise and regularization.
problem Limitations of NTK analysis in deep learning practice.
method Generalized NTK analysis for two-layer neural networks with weight decay and gradient noise.
result Noisy gradient descent with weight decay exhibits 'kernel-like' behavior and converges linearly.
Study tackles nonlinear factor models with unknown monotone links from incomplete and noisy data.
problem Learning nonlinear factor models with unknown monotone links from incomplete and noisy data.
method Formulated as joint recovery of low-rank factors, loadings, and nonlinear link function; proposed BCD algorithm with regularization.
result Established convergence guarantees and sublinear regret bounds for link-function updates.
We study the problem of estimating low-rank matrices from linear measurements (a.k.a., matrix sensing) through nonconvex optimization. We propose an efficient stochastic variance reduced gradient descent algorithm to solve a nonconvex optimization problem of matrix sensing. Our algorithm is applicable to both noisy and…
Algorithm generates private continuous-time data for sensitive domains.
problem Private generation of continuous-time data for sensitive domains.
method Mean-field Langevin dynamics and noisy particle gradient descent.
result Strong privacy guarantees for one-time data contributions.
Neural networks learn clean data patterns first, then noisy data, leading to improved performance initially but deteriorating later.
problem Improvement in prediction error on clean data during early training of neural networks with noisy labels.
method Theoretical analysis and experiments to explore the dynamics of gradient descent and the impact of clean and noisy data.
result Neural networks prioritize learning clean data patterns first, leading to improved performance initially but deteriorating later due to diminishing gradient dominance of clean samples over noisy ones.
Study on SignGD optimization of two-layer transformer on noisy data.
problem Understanding how SignGD optimizes transformers and its generalization.
method Analysis of a two-layer transformer with SignGD on a linearly separable noisy dataset.
result SignGD converges fast but has poor generalization on noisy data.
New algorithms help machines forget old data efficiently.
problem Machine learning models can retain old data, hindering new learning.
method Developed TV-stable algorithms based on noisy SGD for convex and non-convex functions.
result Achieved efficient unlearning with upper and lower bounds on risk.
Study shows how algorithmic choices affect optimal batch sizes in neural networks.
problem Understanding how batch size impacts neural network training efficiency.
method Experiments and analysis of a simple quadratic model to study algorithmic choices.
result Preconditioned optimizers like Adam and K-FAC allow larger batch sizes before diminishing returns.
Gradient descent implicitly regularizes neural networks by penalizing large loss gradients.
problem How to optimize deep neural networks without explicit regularization.
method Backward error analysis to calculate implicit gradient regularization and demonstrate its effectiveness empirically.
result Implicit gradient regularization biases gradient descent toward flat minima, improving model robustness and test errors.
Optimal multistage method solves noisy minimax problems.
problem Minimizing/maximizing in noisy conditions with smooth and strongly convex-strongly concave settings.
method Multistage Stochastic Gradient Descent Ascent (M-GDA) and Optimistic Gradient Descent Ascent (M-OGDA).
result Achieves optimal linear decay rate with respect to initial error and condition number.
Algorithm detects corrupted data using gradient descent.
problem Detecting mislabeled samples in noisy training datasets.
method Optimizing network performance on clean validation set via gradient descent.
result Algorithm improves network performance on validation set.
We prove that stochastic gradient descent efficiently converges to the global optimizer of the maximum likelihood objective of an unknown linear time-invariant dynamical system from a sequence of noisy observations generated by the system. Even though the objective function is non-convex, we provide polynomial running …
SIGUA prevents overfitting in noisy data by forgetting unwanted memorization.
problem Overfitting in deep learning models with noisy labels.
method SIGUA combines gradient descent on good data and learning-rate-reduced gradient ascent on bad data.
result SIGUA improves the performance of two base learning methods significantly.
Improved averaging method for noisy observations converges strongly.
problem Noisy observations from random dynamical systems require stable estimates.
method Introduced p-EMA, a modified exponential moving average with subharmonic weight decay. result Stochastic convergence guarantees for p-EMA under mild assumptions. The paper analyzes the maximum margin algorithm's performance on noisy data.
problem Analyzing the performance of maximum margin algorithm on noisy data.
method Finite-sample analysis of maximum margin algorithm applied to noisy data.
result The maximum margin algorithm can achieve nearly optimal population risk with sufficient over-parameterization.
Overparameterized models generalize well despite fitting noisy data.
problem Understanding why overparameterized models generalize well despite fitting noisy data.
method Statistical signal processing perspective.
result Overparameterized models often outperform underparameterized models in test performance.
Optimizes private statistics with noisy methods.
problem Private inference in statistical models.
method Noisy optimization for M-estimators and confidence regions.
result Private estimators converge to non-private ones with high probability.
Gradient descent with noise converges to a unique optimum in nonconvex matrix factorization.
problem Gradient descent with noise converges to a unique optimum in nonconvex matrix factorization.
method A perturbed form of gradient descent with arbitrary initialization.
result Gradient descent with noise converges to a unique optimum.
The paper examines how gradient descent stabilizes low-rank matrix factorization in noisy conditions.
problem Stability of low-rank implicit regularization in perturbed deep matrix factorization.
method Derives spectral conditions for gradient descent to exhibit a low-rank phase in noiseless settings and analyzes perturbed dynamics.
result Gradient descent converges to a low-rank solution under perturbation, with explicit dependence on perturbation size.