Gradient descent dynamics in nonconvex models explained with universality.
problem Understanding long-time behavior of nonconvex gradient descent.
method Developed a state evolution system for tracking gradient descent iterates.
result Gradient descent iterates are approximately independent of data and strongly incoherent with feature vectors.
We study the projected gradient descent method on low-rank matrix problems with a strongly convex objective. We use the Burer-Monteiro factorization approach to implicitly enforce low-rankness; such factorization introduces non-convexity in the objective. We focus on constraint sets that include both positive semi-defi…
Gradient descent finds better constellations for GMI-based learning.
problem Nonconvexity in end-to-end GMI learning.
method Gradient descent initialized with Gray-labeled APSK constellations.
result State-of-the-art constellations in 2D and 4D provide up to 26% reach increase.
Paper characterizes gradient descent in high-dimensional learning problems.
problem Understanding gradient descent dynamics in high-dimensional statistical learning.
method Non-asymptotic joint distributional characterization of gradient descent iterates and debiased statistics.
result Gradient descent iterates approximate normality after debiasing correction.
Stochastic gradient descent outperforms traditional force-directed methods.
problem Improving graph layout quality and efficiency.
method Applying stochastic gradient descent for stress minimization.
result Stochastic gradient descent is simpler and more robust than traditional methods.
Paper proposes ZO-NGD for more efficient black-box attacks.
problem Vulnerability of state-of-the-art DNNs to adversarial attacks.
method Zeroth-order natural gradient descent (ZO-NGD) for black-box attacks.
result ZO-NGD achieves significantly lower model query complexities.
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.
This paper studies how gradient descent in control systems can perform well on unseen data.
problem The extent of a learned controller's ability to extrapolate to unseen initial states.
method Theoretical study of policy gradient in Linear Quadratic Regulator (LQR) problems, focusing on the role of exploration.
result The performance of a learned controller on unseen initial states depends on the degree of exploration induced by the system.
Stochastic gradient methods are the workhorse (algorithms) of large-scale optimization problems in machine learning, signal processing, and other computational sciences and engineering. This paper studies Markov chain gradient descent, a variant of stochastic gradient descent where the random samples are taken on the t…
BSVGD improves sampling for multimodal distributions using branching.
problem Sampling from multimodal distributions.
method Random branching in Stein Variational Gradient Descent (SVGD).
result Theoretical convergence guarantee and empirical validation.
Gradient descent dynamics studied for DEQs in linear and single-index models.
problem Understanding gradient descent dynamics for DEQs.
method Rigorously studied gradient descent dynamics for DEQs in linear and single-index models.
result Gradient descent converges to a global minimizer for linear DEQs and single-index models.
Stochastic gradient descent improves Gaussian process regression.
problem Efficiently solving large linear systems in Gaussian process regression.
method Developed a stochastic dual descent algorithm using insights from optimisation and kernel communities.
result Stochastic gradient descent is highly effective when done right.
Paper develops unbiased gradient estimator for continuous-time models.
problem Estimating unbiased gradient of log-likelihood for continuous-time models.
method Doubly randomized scheme with coupled conditional particle filter (CCPF).
result Unbiased gradient estimate facilitates gradient-based algorithms.
Stochastic gradient descent approximates Gaussian process posteriors efficiently.
problem Efficiently sampling from Gaussian process posteriors with limited computational resources.
method Developed stochastic gradient optimization objectives for sampling from Gaussian process posteriors.
result Stochastic gradient descent produces accurate predictive distributions, even in non-convergent cases.
Paper proposes a pre-conditioning technique to speed up gradient-descent convergence in distributed linear least-squares problems.
problem Expediting convergence of gradient-descent method for ill-conditioned distributed linear least-squares problems.
method Iterative pre-conditioning technique to improve convergence rate of gradient-descent method.
result Pre-conditioned gradient-descent achieves superlinear convergence for unique solutions and improved linear convergence otherwise.
Analytical method finds deeper optima in two-layer ReLU networks.
problem Training two-layer ReLU networks with analytical methods.
method Analytically finding critical points of the loss function for one layer while keeping the other fixed.
result Significantly smaller training loss values on real datasets compared to gradient descent methods.
Proposes VSGD optimizer combining probabilistic and gradient-based methods.
problem Uncertainty modeling in deep neural networks.
method Combines probabilistic and gradient-based approaches using SVI.
result VSGD outperforms Adam and SGD on image classification tasks.
Gradient-based meta-learning methods leverage gradient descent to learn the commonalities among various tasks. While previous such methods have been successful in meta-learning tasks, they resort to simple gradient descent during meta-testing. Our primary contribution is the {\em MT-net}, which enables the meta-learner…
Adaptive step-size improves optimization in complex geometries.
problem Optimizing functions with non-Euclidean geometries.
method Adaptive step-size strategy for optimization algorithms.
result Guaranteed convergence for Adaptive Conditional Gradient Descent.
Characterizes problems solvable via linear convergence algorithms.
problem Optimization problems solvable with linear convergence.
method Riemannian gradient descent.
result Characterized problems solvable via linear convergence.
A new framework models multi-state events and biomarkers.
problem Limited representation of complex multi-state trajectories.
method General multi-state joint modeling framework.
result Accurate parameter recovery and personalized predictions.
We provide a new theoretical analysis framework to investigate online gradient descent in the dynamic environment. Comparing with the previous work, the new framework recovers the state-of-the-art dynamic regret, but does not require extra gradient queries for every iteration. Specifically, when functions are α stron…
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.
Transformers learn random walks optimally with gradient descent.
problem Transformer interpretability and learning random walks.
method Theoretical analysis and gradient descent training.
result Transformers can predict random walks optimally with gradient descent.
We propose a general purpose variational inference algorithm that forms a natural counterpart of gradient descent for optimization. Our method iteratively transports a set of particles to match the target distribution, by applying a form of functional gradient descent that minimizes the KL divergence. Empirical studies…
An ADRC-incorporated SGD algorithm improves latent factor analysis speed and accuracy.
problem Slow convergence in standard SGD for HDI matrix analysis.
method Incorporates ADRC principles to refine historical and future learning error states.
result Empirically outperforms state-of-the-art LFA models in HDI matrix prediction.
Many iterative procedures in stochastic optimization exhibit a transient phase followed by a stationary phase. During the transient phase the procedure converges towards a region of interest, and during the stationary phase the procedure oscillates in that region, commonly around a single point. In this paper, we devel…
Stochastic Gradient Descent introduces noise in training, affecting model decision boundaries.
problem Understanding the impact of noise in SGD on model decision boundaries.
method Characterized SGD and persistent SGD dynamics in a neural network model, measuring noise magnitude in both under- and over-parametrized regimes.
result Noisier algorithms lead to wider decision boundaries in constraint satisfaction problems.
Paper characterizes gradient descent dynamics for neural networks with finite width.
problem Characterize gradient descent dynamics for multi-layer neural networks.
method Non-asymptotic state evolution theory for finite-width networks.
result Gradient descent dynamics provide precise distributional characterization.
Recent years have seen a flurry of activities in designing provably efficient nonconvex procedures for solving statistical estimation problems. Due to the highly nonconvex nature of the empirical loss, state-of-the-art procedures often require proper regularization (e.g. trimming, regularized cost, projection) in order…
In reinforcement learning, temporal difference (TD) is the most direct algorithm to learn the value function of a policy. For large or infinite state spaces, exact representations of the value function are usually not available, and it must be approximated by a function in some parametric family. However, with \emph{no…
In this paper, we propose a geometric framework to analyze the convergence properties of gradient descent trajectories in the context of linear neural networks. We translate a well-known empirical observation of linear neural nets into a conjecture that we call the \emph{overfitting conjecture} which states that, for a…
Study of SGD with state-dependent noise, improving escape from local minima.
problem Understanding and improving the dynamics of SGD in non-convex optimization.
method Formal study on SGD with state-dependent noise, proposing power-law dynamic with state-dependent diffusion.
result Power-law dynamic can escape from sharp minima exponentially faster than flat minima.
Bayesian approach optimizes in-context learning for state space models.
problem Optimizing in-context learning for state space models.
method Bayesian optimal sequential prediction over latent sequence tasks.
result Bayesian optimal predictor converges to posterior predictive mean.
Improved privacy bounds enhance deep learning training efficiency.
problem Enhancing privacy guarantees in deep learning models.
method Deriving optimal DP parameters using f-divergences. result Significantly reduces the number of iterations needed for training deep learning models.
Blind Descent avoids gradient issues, using a different learning approach.
problem Gradient issues like exploding and vanishing gradients.
method Does not use gradients to guide learning; instead, it is a more fundamental learning process.
result Gradient descent is a specific case of Blind Descent.
MGDRec optimizes multiple objectives in recommender systems.
problem Optimizing for multiple, often conflicting objectives in recommender systems.
method Stochastic multi-gradient descent approach (MGDRec).
result MGDRec outperforms state-of-the-art methods in traditional objective mixtures.
Many machine learning, statistical inference, and portfolio optimization problems require minimization of a composition of expected value functions (CEVF). Of particular interest is the finite-sum versions of such compositional optimization problems (FS-CEVF). Compositional stochastic variance reduced gradient (C-SVRG)…
This paper presents a stochastic behavior analysis of a kernel-based stochastic restricted-gradient descent method. The restricted gradient gives a steepest ascent direction within the so-called dictionary subspace. The analysis provides the transient and steady state performance in the mean squared error criterion. It…
Two novel algorithms improve distributed machine learning in the presence of Byzantine adversaries.
problem Improving distributed machine learning in the presence of Byzantine adversaries.
method Two novel stochastic gradient descent algorithms, ByGARS and ByGARS++, using reputation scores for gradient aggregation.
result Robust to any number of multiplicative noise Byzantine adversaries and converge for strongly convex loss functions.
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 converges to Nash equilibria in competitive games.
problem Finding Nash equilibria in decentralized, competitive Markov games.
method Decentralized Optimistic Gradient Descent/Ascent with a critic.
result Converges to the set of Nash equilibria under self-play.
Improving sample efficiency has been a longstanding goal in reinforcement learning. This paper proposes VRMPO algorithm: a sample efficient policy gradient method with stochastic mirror descent. In VRMPO, a novel variance-reduced policy gradient estimator is presented to improve sample efficiency.…
Simple gradient descent algorithm escapes saddle points efficiently.
problem Escaping saddle points in nonconvex optimization.
method Gradient-based algorithm with polynomial iterations.
result Outputs ε-approximate second-order stationary points efficiently.
Generalizes NTK for surrogate gradient learning in neural networks.
problem Lack of theoretical foundation for surrogate gradient learning.
method Generalizes neural tangent kernel (NTK) for surrogate gradient learning (SGL).
result Surrogate gradient NTK provides a good characterization of SGL.
Gradient descent converges to a global minimum in nonlinear ReLU implicit networks with linear width.
problem Understanding convergence of gradient methods in nonlinear, infinitely deep ReLU networks.
method Introduced a scaling constant to ensure well-posedness of the equilibrium equation, proving convergence to a global minimum for linear width networks.
result Gradient descent converges to a global minimum at a linear rate for nonlinear ReLU implicit networks with linear width.
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.
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…