Gradient descent biases towards stable rank networks for nearly-orthogonal data.
problem Understanding implicit bias in non-smooth neural networks trained by gradient descent.
method Analysis of two-layer ReLU and leaky ReLU networks trained by gradient descent on nearly-orthogonal data.
result Gradient descent biases towards networks with stable rank and uniform margin for nearly-orthogonal data.
Deep networks without non-linearities are equivalent to shallow ones.
problem Training deep orthogonal linear networks with no non-linearity.
method Riemannian gradient descent and gradient descent on factorization.
result Training deep overparametrized networks is equivalent to shallow ones.
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.
New method for sampling on constrained domains using orthogonal-space gradient flow.
problem Sampling on manifolds defined by constraints is challenging.
method Orthogonal-Space Variational Gradient Descent (O-Gradient)
result O-Gradient converges to the target constrained distribution efficiently.
OGD proves robustness to Catastrophic Forgetting in Continual Learning.
problem Catastrophic Forgetting in Continual Learning with deep neural networks.
method Theoretical framework based on Neural Tangent Kernel for OGD.
result First generalization bound for SGD and OGD in Continual Learning.
Transformers learn to recall with non-orthogonal embeddings in realistic settings.
problem Understanding how transformers store and retrieve knowledge in practical scenarios.
method Analyzing a single-layer transformer with random embeddings trained on a token-retrieval task.
result Explicit formulas for the model's storage capacity reveal a multiplicative dependence on sample size, embedding dimension, and sequence length.
New method for identifying autoregressive systems on manifolds.
problem Identifying autoregressive systems on Stiefel and Grassmann manifolds.
method Defining parameters as orthogonal group elements, averaging over observations, conjugate gradient descent on manifolds.
result System parameters can be estimated efficiently using the proposed algorithm.
In optimization, the negative gradient of a function denotes the direction of steepest descent. Furthermore, traveling in any direction orthogonal to the gradient maintains the value of the function. In this work, we show that these orthogonal directions that are ignored by gradient descent can be critical in equilibri…
In this paper, we propose a scalable algorithm for spectral embedding. The latter is a standard tool for graph clustering. However, its computational bottleneck is the eigendecomposition of the graph Laplacian matrix, which prevents its application to large-scale graphs. Our contribution consists of reformulating spect…
ORFit trains models on streaming data with one pass, minimizing memory and computational costs.
problem Training large models on a stream of data without retraining on previous data.
method Orthogonal Recursive Fitting (ORFit) using orthogonal gradient descent and recursive least-squares.
result ORFit updates parameters orthogonally to past gradients, leading to efficient memory and computational usage.
We analyze stochastic gradient descent for optimizing non-convex functions. In many cases for non-convex functions the goal is to find a reasonable local minimum, and the main concern is that gradient updates are trapped in saddle points. In this paper we identify strict saddle property for non-convex problem that allo…
Gradient descent memorizes many Gaussians efficiently.
problem Memorizing many Gaussians with minimal parameters.
method Gradient descent on a depth-two neural network.
result One step of gradient descent memorizes $Ω\left(\frac{dq}{\log^4(d)}
ight)$ Gaussians.
SpecNet2 improves spectral embedding without orthogonalization, achieving better performance and efficiency.
problem Improving spectral embedding methods for better performance and efficiency.
method Optimizes an equivalent objective of the eigen-problem without orthogonalization, allowing separate row and column sampling.
result Local and global convergence of the new objective using batch-based gradient descent is proven, and improved performance and efficiency are demonstrated on simulated and image datasets.
Gradient descent dynamics in quadratic regression models are analyzed, revealing five phases: monotonic, catapult, periodic, chaotic, and divergent.
problem Analyzing the dynamics of gradient descent in quadratic regression models.
method Fine-grained bifurcation analysis of gradient descent dynamics using a cubic map parameterized by the step-size.
result Gradient descent dynamics in quadratic regression models exhibit five distinct phases: monotonic, catapult, periodic, chaotic, and divergent.
Gradient descent with large steps leads to chaotic parameter space and unpredictable outcomes.
problem Understanding the behavior of gradient descent with large step sizes in matrix factorization.
method Analyzing the fractal structure of the parameter space and deriving critical step sizes for convergence.
result Gradient descent with large steps exhibits chaotic behavior and sensitivity to initialization, creating a fractal boundary between converging and diverging minimizers.
Gradient descent fails to learn simple neural networks efficiently.
problem Learning one-layer neural networks efficiently using gradient descent.
method Gradient descent and statistical query algorithms.
result Superpolynomial lower bounds for learning one-layer neural networks.
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.
Muon optimizer simplifies matrix optimization with spectral orthogonalization.
problem Matrix optimization challenges, especially with large condition numbers.
method Simplified Muon optimizer using spectral orthogonalization of gradients.
result Simplified Muon converges linearly with independent scalar sequences, outperforming gradient descent and Adam.
The paper generalizes optimization algorithms using category theory.
problem Optimizing functions in a category-theoretic setting.
method Using the Cartesian reverse derivative to generalize gradient descent and Newton's method.
result Properties of optimization algorithms are preserved in the generalized setting, including invariances and convergence.
Recurrent neural networks (RNNs) have been successfully used on a wide range of sequential data problems. A well known difficulty in using RNNs is the \textit{vanishing or exploding gradient} problem. Recently, there have been several different RNN architectures that try to mitigate this issue by maintaining an orthogo…
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.
This paper explores how Transformers predict next tokens in autoregressive tasks.
problem Understanding the success of Transformers in autoregressive learning.
method Trained a Transformer on a next-token prediction task, focusing on commuting orthogonal matrices.
result Trained Transformers can be seen as implementing gradient descent for a specific objective function.
This study investigates how gradient-based methods bias neural networks trained on high-dimensional data.
problem The implicit biases of gradient-based optimization algorithms in neural networks trained on high-dimensional data.
method Investigation of gradient flow and gradient descent in two-layer fully-connected neural networks with leaky ReLU activations.
result Gradient flow and gradient descent lead to neural networks with low-rank solutions and linear decision boundaries.
SpecGD mitigates misalignment in phase retrieval models with anisotropic inputs.
problem Misalignment during gradient descent in phase retrieval models with anisotropic inputs.
method Spectral gradient descent modifies gradient updates to preserve directional information and remove spike amplification.
result SpecGD removes spike amplification, leading to stable alignment and accelerated noise contraction.
Neural networks are achieving state of the art and sometimes super-human performance on learning tasks across a variety of domains. Whenever these problems require learning in a continual or sequential manner, however, neural networks suffer from the problem of catastrophic forgetting; they forget how to solve previous…
The paper interprets diffusion models as gradient descent and proposes a new sampler.
problem Improving the efficiency and quality of diffusion models.
method Interprets diffusion models as gradient descent and proposes a new sampler.
result The new sampler achieves state-of-the-art FID scores and generates high quality samples.
A new pruning method reduces neural network computation without retraining.
problem Efficiently reduce neural network computation while maintaining accuracy.
method Structured directional pruning via perturbation orthogonal projection.
result Achieves state-of-the-art pruned accuracy without retraining.
Gradient descent outperforms ridge regression under certain covariance matrix decay conditions.
problem Comparing the performance of gradient descent and ridge regression in linear models.
method Investigated gradient descent and ridge regression for linear regression with random isotropic ground truth.
result Gradient descent outperforms ridge regression under specific covariance matrix decay conditions.
The paper tackles CF in CL by analyzing NTK overlap matrix and proposing OGD.
problem Catastrophic Forgetting in continual learning.
method Analysis of NTK overlap matrix, OGD with PCA.
result Proposes OGD to mitigate CF, supported by experiments.
OrthoGrad improves neural calibration by constraining gradient updates orthogonally.
problem Overconfidence in neural networks, leading to poor uncertainty estimates.
method Orthogonal gradient updates to optimize for decision boundaries and reduce overconfidence.
result Significant improvements in test loss, predictive entropy, and confidence measures.
OPT framework improves neural network generalization by learning an orthogonal transformation.
problem Improving neural network generalization.
method Orthogonal over-parameterized training (OPT) framework that minimizes hyperspherical energy.
result OPT framework provably minimizes hyperspherical energy and improves empirical generalization.
Conformal Autoencoders infer intrinsic dimensionality and impose invariance.
problem Detecting intrinsic dimensionality and imposing invariance in nonlinear manifold data.
method Imposing orthogonality conditions on latent variables to infer intrinsic dimensionality and build coordinate invariance.
result The method can infer intrinsic dimensionality and build coordinate invariance on submanifolds.
Study functional confounders in causal inference, enabling estimable effects.
problem Causal inference challenges with functional confounders violating positivity.
method Functional interventions, functional positivity, gradient fields, Level-set Orthogonal Descent Estimation (LODE).
result Valid causal effect estimation under certain conditions.
Gradient descent can efficiently learn a target function with diverse and near-orthogonal features.
problem Learning a target function with additive structure and diverse features.
method Gradient descent training of a two-layer neural network.
result A large subset of polynomial target functions can be efficiently learned.
Batch normalization makes deep neural networks' representations increasingly orthogonal.
problem Orthogonality of deep neural network representations.
method Random linear transformations in successive batch-normalizations.
result Orthogonality of representations improves SGD performance.
Study on neural networks forgetting in continual learning.
problem Forgetting in neural networks during continual learning.
method Gradient descent analysis on XOR-cluster datasets.
result Explicit bounds on forgetting rate and generalization gap.
Gradient descent biases neural networks to use an average of features, leading to non-robustness.
problem Non-robustness in neural networks due to feature averaging.
method Theoretical analysis and experiments on binary classification tasks.
result Gradient descent trains networks to rely on an average of features, making them vulnerable to adversarial attacks.
Efficiently optimizes orthogonal and Stiefel matrices on parallel units.
problem Optimization over orthogonal groups on parallel units.
method CWY and T-CWY transforms for parametrization and optimization.
result CWY and T-CWY methods lead to convergence on parallel units.
Several variants of recurrent neural networks (RNNs) with orthogonal or unitary recurrent matrices have recently been developed to mitigate the vanishing/exploding gradient problem and to model long-term dependencies of sequences. However, with the eigenvalues of the recurrent matrix on the unit circle, the recurrent s…
SketchOGD improves memory efficiency for continual learning.
problem Catastrophic forgetting in continual learning.
method Matrix sketching to compress model gradients.
result SketchOGD outperforms existing memory-efficient OGD variants.
Optimizing over the set of orthogonal matrices is a central component in problems like sparse-PCA or tensor decomposition. Unfortunately, such optimization is hard since simple operations on orthogonal matrices easily break orthogonality, and correcting orthogonality usually costs a large amount of computation. Here we…
New method estimates SDE parameters efficiently using WCE and SGD.
problem Parameter estimation for stochastic differential equations.
method Wiener Chaos Expansion and Stochastic Gradient Descent.
result Accurate parameter recovery from noisy observations.
New convergence guarantees for learning with unknown nuisance parameters.
problem Learning problems with unknown nuisance parameters.
method Stochastic gradient optimization with Neyman orthogonality and approximately orthogonalized updates.
result Stochastic gradient algorithms can converge under conditions of nuisance parameters.
Recent work has established an empirically successful framework for adapting learning rates for stochastic gradient descent (SGD). This effectively removes all needs for tuning, while automatically reducing learning rates over time on stationary problems, and permitting learning rates to grow appropriately in non-stati…
Integrates momentum into RNNs to improve training.
problem Vanishing gradient in RNNs during training.
method Established connection between RNN dynamics and GD, integrated momentum.
result MomentumRNNs alleviate vanishing gradient issue and improve convergence.
Develops first and second-order pseudo-mirror descent methods for nonnegative function estimation.
problem Nonnegative function estimation in settings like MLE and trajectory optimization.
method First and second-order pseudo-mirror descent with pseudo-gradients and projections.
result Establishes tradeoffs and non-asymptotic bounds on model complexity.
SGD batch size affects autoencoder global minima sparsity and sharpness.
problem Investigating how batch size impacts autoencoder learning.
method Non-convex autoencoder training with SGD, varying batch sizes.
result SGD batch size influences global minimum sparsity and sharpness.
This paper considers the recovery of a rank r positive semidefinite matrix XXT∈Rn×n from m scalar measurements of the form yi:=aiTXXTai (i.e., quadratic measurements of X). Such problems arise in a variety of applications, including covariance sketching of high-dimensional data…