New bound relaxes uniform gradient norm assumptions for PAC-Bayesian bounds.
problem Generalization bounds with strict assumptions like uniformly bounded loss.
method Relax uniform bounds assumptions to on-average bounded loss and gradient norm.
result Proposes a new generalization bound with a surrogate of model complexity.
AdaGrad-Norm achieves optimal convergence rates for non-convex objectives without tuning.
problem Optimal convergence rates for non-convex, smooth objectives with adaptive step sizes.
method Adaptive SGD (AdaGrad-Norm) with self-tuning step sizes, analyzing under unbounded gradients and affine variance scaling.
result AdaGrad-Norm achieves order optimal convergence rate of $\mathcal{O}\left(\frac{\mathrm{poly}\log(T)}{\sqrt{T}}
ight)$ under optimal assumptions.
This technical report describes an efficient technique for computing the norm of the gradient of the loss function for a neural network with respect to its parameters. This gradient norm can be computed efficiently for every example.
Equivalent tests for SGD batch size selection found.
problem Finding equivalent tests for adaptive batch size selection in SGD.
method Norm and inner product/orthogonality tests equivalence demonstration.
result Norm and inner product/orthogonality tests are equivalent under specific conditions.
Adam's hyperparameters implicitly regularize solutions, penalizing or impeding loss gradients' norms.
problem Implicit regularization in Adam's hyperparameters and training stage.
method Backward error analysis and ODE approximations to study Adam's behavior.
result Adam's implicit regularization depends on hyperparameters and training stage, involving different norms.
We prove that the norm version of the adaptive stochastic gradient method (AdaGrad-Norm) achieves a linear convergence rate for a subset of either strongly convex functions or non-convex functions that satisfy the Polyak Lojasiewicz (PL) inequality. The paper introduces the notion of Restricted Uniform Inequality of Gr…
A method predicts GNS of transformer layers using normalization layer norms.
problem Estimating gradient noise scale with minimal variance.
method Simultaneously compute per-example gradient norms and parameter gradients.
result Total GNS is predicted well by normalization layer GNS.
Gradient flow on softmax attention minimizes nuclear norm of weight matrices.
problem Classification with separate key and query weight matrices.
method Gradient flow on exponential loss, separability assumption, reparameterization, approximate KKT conditions.
result Gradient flow implicitly minimizes nuclear norm of weight matrices, contrasting with Frobenius norm minimization.
Training neural networks under a strict Lipschitz constraint is useful for provable adversarial robustness, generalization bounds, interpretable gradients, and Wasserstein distance estimation. By the composition property of Lipschitz functions, it suffices to ensure that each individual affine transformation or nonline…
This work improves OOD detection using deep generative models by approximating Fisher information metrics.
problem Deep generative models often incorrectly infer higher likelihoods for out-of-distribution data.
method Approximating Fisher information metrics using gradient norms of data points.
result The method outperforms existing OOD detection techniques.
We model how Lipschitz continuity changes during neural network training.
problem Understanding how Lipschitz continuity evolves during training.
method We use a system of stochastic differential equations to capture the dynamics of Lipschitz continuity under SGD.
result We identify three factors driving the evolution of Lipschitz continuity: gradient flow projection, gradient noise, and Hessian projection.
Noise injection before gradient steps helps in regularization for neural networks.
problem Improving generalization in overparametrized neural networks.
method Injecting small noise perturbations before computing gradient steps, especially in layer-wise fashion.
result Small noise perturbations can explicitly regularize neural networks without variance explosion.
We study a hybrid conditional gradient - smoothing algorithm (HCGS) for solving composite convex optimization problems which contain several terms over a bounded set. Examples of these include regularization problems with several norms as penalties and a norm constraint. HCGS extends conditional gradient methods to cas…
RTC-GTNLN model recovers traffic data from missing values and noise.
problem Simultaneous missing data and noise in traffic data.
method Gradient tensor nuclear L1-L2 norm for robust tensor completion.
result RTC-GTNLN model outperforms existing methods in complex recovery scenarios.
Gradient flow with weight decay shows grokking effect in deep learning.
problem Understanding the grokking effect in deep learning.
method Analyzing gradient flow dynamics with weight decay.
result Weight decay causes slow norm reduction, explaining grokking.
We study the iteration complexity of stochastic gradient descent (SGD) for minimizing the gradient norm of smooth, possibly nonconvex functions. We provide several results, implying that the O(ε−4) upper bound of Ghadimi and Lan~\cite{ghadimi2013stochastic} (for making the average gradient norm less than…
Proposes a new adaptive gradient method based on gradient differences.
problem Manual tuning of stepsize in vanilla gradient methods.
method Adaptation driven by cumulative squared norms of gradient differences.
result More robust than AdaGrad in various settings.
Muon dynamics study uses spectral Wasserstein flow for optimization stability.
problem Optimizing deep learning models with gradient normalization.
method Introduces Spectral Wasserstein distances for matrix flows, proving equivalence with Benamou--Brenier formulation.
result Gradient-flow interpretation of mean-field normalized training dynamics.
The paper constructs optimal confidence bands for kernel gradient flow estimators.
problem Estimating generalization error and constructing confidence bands for kernel gradient flows.
method Established convergence rates and constructed optimal confidence bands under capacity-source condition.
result Optimal confidence bands for kernel gradient flows have shrinkage rates close to minimax optimal rates.
Motivated by some applications in signal processing and machine learning, we consider two convex optimization problems where, given a cone K, a norm ∥⋅∥ and a smooth convex function f, we want either 1) to minimize the norm over the intersection of the cone and a level set of f, or 2) to minimize over the…
Single ReLU neuron's gradient dynamics reveal support vectors as key to generalization.
problem Understanding the generalization capability of ReLU networks.
method Examined gradient flow dynamics and support vectors in single ReLU neuron training.
result Support vectors play a crucial role in the generalization of ReLU networks.
We present a proof due to Duistermaat that the gradient flow of the norm squared of the moment map defines a deformation retract of the appropriate piece of the manifold onto the zero level set of the moment map. Duistermaat's proof is an adaptation of Lojasiewicz's argument for analytic functions to functions which ar…
Proves inequality linking function deviation to gradient norm on compact manifolds.
problem Analyzing coupled elliptic systems on compact manifolds.
method Develops a new Poincaré-Sobolev inequality with a density-free reference average.
result Poincaré constant depends on the density's gradient norm.
Gradient descent achieves optimal learning for elliptic PDEs via Sobolev norms.
problem Learning elliptic PDEs from noisy data.
method Gradient descent on Sobolev norm objective functions.
result Gradient descent achieves statistical optimality for elliptic PDEs.
This paper presents a new mechanism for producing sanitized statistical summaries that achieve \emph{differential privacy}, called the \emph{K-Norm Gradient} Mechanism, or KNG. This new approach maintains the strong flexibility of the exponential mechanism, while achieving the powerful utility performance of objective …
Adversarial training is a principled approach for training robust neural networks. Despite of tremendous successes in practice, its theoretical properties still remain largely unexplored. In this paper, we provide new theoretical insights of gradient descent based adversarial training by studying its computational prop…
Adaptive gradient methods such as AdaGrad and its variants update the stepsize in stochastic gradient descent on the fly according to the gradients received along the way; such methods have gained widespread use in large-scale optimization for their ability to converge robustly, without the need to fine-tune the stepsi…
Paper addresses fault-tolerance in distributed machine learning with stochastic gradient descent.
problem Fault-tolerance in distributed stochastic gradient descent (D-SGD) for machine learning.
method Proposes norm-based comparative gradient elimination (CGE) to robustify D-SGD against Byzantine faulty agents.
result CGE guarantees fault-tolerance against a bounded fraction of Byzantine agents under standard stochastic assumptions.
GraN detects adversarial and misclassified examples efficiently.
problem Detecting adversarial and misclassified examples in deep neural networks.
method GraN uses the layer-wise norm of the DNN's gradient regarding the loss of the current input-output combination.
result GraN achieves state-of-the-art performance on numerous problem set-ups.
GRAIN: Group Aggregation via Min-Norm Objective
problem Learning instability in large models
method Replacing mean aggregation with min-norm convex combination
result Improves performance and reduces variance
The paper accelerates ISTA and FISTA algorithms for composite optimization problems.
problem Improving convergence rates of ISTA and FISTA for composite optimization.
method Improved proximal subgradient norm minimization using Lyapunov function.
result Convergence rates of ISTA and FISTA are accelerated.
Characterizes inductive bias in multi-channel linear CNNs with bounded weight norm.
problem Understanding the inductive bias in multi-channel linear convolutional networks.
method Function space characterization and empirical testing of gradient descent.
result The inductive bias depends on the number of output channels for multi-channel inputs but not for single-channel inputs.
SAM improves generalization in overparameterized models, but its behavior in tensorized models is less understood.
problem Understanding the implicit regularization of SAM in tensorized models.
method Scale-invariance analysis and gradient flow analysis to derive Norm Deviation as a measure of core norm imbalance, and propose Deviation-Aware Scaling (DAS).
result DAS achieves competitive or improved performance over SAM, while offering reduced computational overhead.
In recent years, plenty of metrics have been proposed to identify networks that are free of gradient explosion and vanishing. However, due to the diversity of network components and complex serial-parallel hybrid connections in modern DNNs, the evaluation of existing metrics usually requires strong assumptions, complex…
New Banach spaces for ReLU networks enable better function approximation and gradient dynamics analysis.
problem Function approximation and gradient dynamics in multi-layer ReLU networks.
method Developed Banach spaces for ReLU networks, defined new function representations, and analyzed gradient flow dynamics.
result Gradient flow dynamics of the new representation is the continuous analog of gradient descent for ReLU networks.
Paper introduces a new G⋆ regret measure for online convex optimization with smooth losses.
problem Online convex optimization with smooth losses.
method Introduces a new G⋆ regret measure that depends on the cumulative squared gradient norm. result The G⋆ regret can be arbitrarily sharper than existing measures when losses have vanishing curvature. New algorithms solve complex minimax problems efficiently.
problem Nonconvex-strongly concave minimax problems in machine learning.
method Gradient norm regularized trust-region (GRTR) and Levenberg-Marquardt (LMNegCur) algorithms.
result Proved iteration complexities matching best known results.
Although stochastic gradient descent (SGD) is a driving force behind the recent success of deep learning, our understanding of its dynamics in a high-dimensional parameter space is limited. In recent years, some researchers have used the stochasticity of minibatch gradients, or the signal-to-noise ratio, to better char…
A popular heuristic for improved performance in Generative adversarial networks (GANs) is to use some form of gradient penalty on the discriminator. This gradient penalty was originally motivated by a Wasserstein distance formulation. However, the use of gradient penalty in other GAN formulations is not well motivated.…
The paper proposes an efficient algorithm for solving Schatten-p quasi-norm problems.
problem Finding low-rank solutions of linear inverse problems with Schatten-p quasi-norm regularization. method Dynamic proximal gradient algorithm using Cayley transformation and adaptive step size selection.
result The algorithm converges to a stationary point of the objective function under mild assumptions.
The k-support norm is a regularizer which has been successfully applied to sparse vector prediction problems. We show that it belongs to a general class of norms which can be formulated as a parameterized infimum over quadratics. We further extend the k-support norm to matrices, and we observe that it is a special …
A new interpolation method speeds up neural ODE training.
problem Efficiently approximating gradients in neural ODEs.
method Interpolation-based technique to approximate gradients.
result Our method trains neural ODEs faster than the reverse dynamic method.
This study explains gradient flow dynamics in neural networks for small initialisation.
problem Understanding the training dynamics of neural networks for small initialisation.
method Analysis of gradient flow dynamics for one-hidden layer ReLU networks with orthogonal inputs.
result Gradient flow converges to zero loss and characterizes implicit bias towards minimum variation norm.
The spectral k-support norm enjoys good estimation properties in low rank matrix learning problems, empirically outperforming the trace norm. Its unit ball is the convex hull of rank k matrices with unit Frobenius norm. In this paper we generalize the norm to the spectral (k,p)-support norm, whose additional para…
Gradient flow with infinitesimal initialization converges to Greedy Low-Rank Learning for matrix factorization.
problem Understanding implicit regularization in gradient descent for matrix factorization.
method Theoretical and empirical analysis of gradient flow with infinitesimal initialization and Greedy Low-Rank Learning.
result Gradient flow with infinitesimal initialization is mathematically equivalent to Greedy Low-Rank Learning for depth-2 matrix factorization under reasonable assumptions.
Unified algorithm for minimizing composite functions with flexible design.
problem Minimizing composite functions with specific structural properties.
method Unified accelerated algorithm for complementary composite minimization.
result Near-optimal algorithms for various optimization problems.
This paper introduces Libra to analyze and optimize generalization in Federated Learning.
problem Inconsistent local optima in Federated Learning lead to poor generalization performance.
method Introduces Libra, a generalization dynamics analysis framework for algorithm-dependent excess risk minimization.
result Libra highlights the trade-offs between model stability and gradient norms in Federated Learning.
New optimization method combines gradient clipping and non-Euclidean smoothness.
problem Improving optimization in non-Euclidean spaces for machine learning.
method Hybrid of steepest descent and conditional gradient, incorporating weight decay.
result Achieves optimal convergence rate and demonstrates effectiveness in deep learning.