New stochastic gradient descent with random search directions improves efficiency and convergence.
problem Efficiency and convergence of stochastic gradient descent methods.
method Developed a new class of stochastic gradient descent algorithms with random search directions.
result Established almost sure convergence and provided Lp rates of convergence. Mirror descent linked to information ratio via Bayesian regret bounds.
problem Understanding stability in mirror descent and its relation to information ratio.
method Developed a connection between mirror descent and information ratio using Bayesian regret bounds.
result Mirror descent with suitable estimators and distributions achieves bounds similar to information-directed sampling.
Yau's Affine Normal Descent optimizes smooth unconstrained problems with geometrically adapted directions.
problem Optimizing smooth unconstrained problems with geometrically adapted directions.
method Yau's Affine Normal Descent (YAND) uses the equi-affine normal of level-set hypersurfaces as search directions.
result YAND converges globally under standard smoothness assumptions and locally quadratically near nondegenerate minimizers.
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.
Gradient descent implicitly follows regularization for general losses.
problem The implicit bias of gradient descent methods in machine learning.
method Empirical risk minimization over linear predictors with arbitrary convex, strictly decreasing losses.
result Gradient descent and regularization paths converge to the same direction for non-attained risks.
GANs excel at learning high dimensional distributions, but they can update generator parameters in directions that do not correspond to the steepest descent direction of the objective. Prominent examples of problematic update directions include those used in both Goodfellow's original GAN and the WGAN-GP. To formally d…
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…
SGD benefits from a directional bias in kernel regression models.
problem Improving generalization in kernel regression models.
method Generalized directional bias property of SGD in kernel regression.
result SGD converges along the eigenvector of the largest eigenvalue of the Gram matrix.
PGD-trained models have a preferential direction in their gradients, which improves robustness.
problem Mathematical lack of clarity in the direction of preferential gradient alignment after adversarial training.
method Proposed a novel definition of preferential direction and evaluated it using a metric based on GANs.
result PGD-trained models have higher alignment with the proposed preferential direction than baseline models.
Stochastic Gradient Descent shows directional bias with moderate learning rates, impacting optimization outcomes.
problem Understanding the bias of SGD with moderate learning rates in practical scenarios.
method Analyzing SGD and GD on an overparameterized linear regression problem.
result SGD converges along large eigenvalue directions, GD along small ones, affecting early stopping outcomes.
ConMeZO speeds up zeroth-order optimization for large language models.
problem Slow convergence in high-dimensional parameter spaces of large language models.
method Adaptive directional sampling in a cone centered around a momentum estimate.
result Achieves the same convergence rate as MeZO but up to 2X faster.
This paper provides a block coordinate descent algorithm to solve unconstrained optimization problems. In our algorithm, computation of function values or gradients is not required. Instead, pairwise comparison of function values is used. Our algorithm consists of two steps; one is the direction estimate step and the o…
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.
Gradient descent, when applied to the task of logistic regression, outputs iterates which are biased to follow a unique ray defined by the data. The direction of this ray is the maximum margin predictor of a maximal linearly separable subset of the data; the gradient descent iterates converge to this ray in direction a…
Direct proof shows adaptive gradient descent converges near-linearly for convex functions.
problem Proving near-linear convergence of adaptive gradient descent for convex functions.
method Direct Lyapunov-based argument for convex functions with unique minimizer.
result Direct proof of near-linear convergence for convex functions.
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.
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…
We study the implicit bias of gradient descent methods in solving a binary classification problem over a linearly separable dataset. The classifier is described by a nonlinear ReLU model and the objective function adopts the exponential loss function. We first characterize the landscape of the loss function and show th…
Gradient descent, or negative gradient flow, is a standard technique in optimization to find minima of functions. Many implementations of gradient descent rely on discretized versions, i.e., moving in the gradient direction for a set step size, recomputing the gradient, and continuing. In this paper, we present an appr…
New insights into neural network feature learning through multi-step gradient descent.
problem Understanding feature learning in two-layer neural networks with limited width.
method Characterization of feature learning through two steps of gradient descent with specific step sizes.
result The second step of gradient descent reveals multiple learned directions, not limited to a single direction as in the first step.
A new fast algorithm solves SLOPE optimization problem.
problem Inefficient algorithms for SLOPE optimization in high dimensions.
method Combines proximal gradient descent and proximal coordinate descent steps.
result Our method outperforms competing algorithms in benchmarks.
New algorithm reduces complexity for SPD manifold optimization.
problem Efficiently minimize functions over SPD manifold.
method Low-complexity Riemannian subspace descent with sparse updates.
result Innovative updates avoid costly matrix operations.
Gradient descent near stability threshold shows sharpness oscillations.
problem Understanding sharpness and stability in non-Euclidean norms during gradient descent.
method Interpreted EoS through Directional Smoothness, defined generalized sharpness for arbitrary norms.
result Non-Euclidean GD exhibits sharpness oscillations around the stability threshold.
Gradient descent near stability threshold exhibits sharpness oscillations.
problem Understanding sharpness behavior near stability threshold in non-Euclidean norms.
method Interpreted EoS through Directional Smoothness and generalized sharpness under arbitrary norms.
result Non-Euclidean GD with generalized sharpness shows sharpness oscillations near 2/η. GD iterates for non-homogeneous deep nets increase margin and converge in direction.
problem Understanding implicit bias in non-homogeneous deep networks.
method Characterization of GD iterates' properties starting from small empirical risk.
result GD iterates converge in direction despite diverging norms, satisfying KKT conditions.
The paper analyzes how noise geometry influences the performance of SGD in machine learning.
problem Understanding how noise geometry affects the performance of stochastic gradient descent.
method Developed two metrics to quantify noise alignment strength and analyzed their effects on loss and subspace projection dynamics.
result Noise geometry can be used to guarantee alignment under certain conditions, aiding SGD's ability to escape from sharp minima.
Gravilon improves gradient descent for neural networks.
problem Improving efficiency and accuracy of gradient descent methods.
method Uses geometric modification of gradient step lengths.
result Promising experimental results on MNIST classification.
GD at EoS edge minimizes logistic loss without monotonic convergence.
problem Understanding GD's implicit bias at the edge of stability.
method Theoretical analysis of logistic regression with constant stepsize GD.
result GD with any constant stepsize minimizes logistic loss over long time scales.
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.
Paper accelerates Bayesian few-shot classification using mirror descent.
problem Non-conjugate inference in Bayesian few-shot classification.
method Integrates mirror descent-based variational inference into Gaussian process-based few-shot classification.
result Accelerated convergence and improved uncertainty quantification.
Two popular examples of first-order optimization methods over linear spaces are coordinate descent and matching pursuit algorithms, with their randomized variants. While the former targets the optimization by moving along coordinates, the latter considers a generalized notion of directions. Exploiting the connection be…
Gradient-free method solves infinite-dimensional optimization problems.
problem Optimizing functions in infinite-dimensional spaces.
method Uses directional derivatives and a pre-basis for Hilbert space.
result Proves convergence for solving PDEs using PINNs.
Gradient descent and its variants are widely used in machine learning. However, oracle access of gradient may not be available in many applications, limiting the direct use of gradient descent. This paper proposes a method of estimating gradient to perform gradient descent, that converges to a stationary point for gene…
The paper explores how symmetries and noise in SGD influence parameter dynamics.
problem Understanding the dynamics of parameter updates in SGD with symmetries.
method Proved the existence of noise equilibria and showed their role in balancing gradient noise.
result Gradient noise creates a systematic motion of parameters to a unique fixed point, called noise equilibria.
We present a unifying framework for adapting the update direction in gradient-based iterative optimization methods. As natural special cases we re-derive classical momentum and Nesterov's accelerated gradient method, lending a new intuitive interpretation to the latter algorithm. We show that a new algorithm, which we …
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…
Proposes new stochastic algorithms for multi-objective optimization.
problem Multi-objective optimization in machine learning problems.
method Direction-oriented multi-objective formulation and Stochastic Direction-oriented Multi-objective Gradient descent (SDMGrad).
result Stochastic algorithms converge to Pareto stationary points with improved complexities.
New method optimizes SDE models using continuous-time gradient descent.
problem Optimizing over the stationary distribution of SDE models.
method Continuous-time stochastic gradient descent for SDE models.
result Asymptotic convergence to the direction of steepest descent.
We present here a new model and algorithm which performs an efficient Natural gradient descent for Multilayer Perceptrons. Natural gradient descent was originally proposed from a point of view of information geometry, and it performs the steepest descent updates on manifolds in a Riemannian space. In particular, we ext…
A new pruning method finds sparse minimizers in flat regions of deep neural networks.
problem Finding sparse minimizers in flat regions of deep neural networks.
method Directional pruning using an ℓ1 proximal gradient algorithm. result Empirical results show promising sparsity (92%) and comparable minima to SGD.
The mirror descent algorithm (MDA) generalizes gradient descent by using a Bregman divergence to replace squared Euclidean distance. In this paper, we similarly generalize the alternating direction method of multipliers (ADMM) to Bregman ADMM (BADMM), which allows the choice of different Bregman divergences to exploit …
Novel algorithm for decentralized optimization in time-varying networks with delays.
problem Decentralized optimization in networks with communication delays.
method DT-GO algorithm, applicable to general directed graphs, converges to same complexity as centralized SGD.
result Algorithm DT-GO achieves convergence rates for convex and non-convex objectives, similar to centralized SGD.
Deep ReLU networks escape from the origin via saddle points with a low-rank bias.
problem Understanding the dynamics of gradient descent in deep ReLU networks.
method Analysis of escape directions and singular values of weight matrices.
result The first singular value of the ℓ-th layer weight matrix is at least ℓ41 larger than any other singular value. Gradient descent converges to minimum Bayes risk for two-layer ReLU networks in mean field regime.
problem Training two-layer ReLU networks using gradient descent in the mean field regime.
method Describes a condition for convergence to minimum Bayes risk, extending previous results to ReLU-activated networks.
result The condition for convergence does not depend on initialization and concerns weak convergence of network realization.
Neural networks learn faster with correlated latent variables.
problem Efficiently learning from higher-order correlations in neural networks.
method Analytical derivation and simulations of two-layer neural networks.
result Correlations between latent variables speed up learning from higher-order correlations.
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.
Two-layer neural networks learn features through a few gradient descent steps, improving approximation capacity.
problem Improving approximation capacity of two-layer neural networks.
method Theoretical investigation of a two-layer neural network's adaptation to target function through a few gradient descent steps.
result Learning multiple target directions requires a larger batch size and more gradient steps, improving approximation capacity.
A quantum generalization of Natural Gradient Descent is presented as part of a general-purpose optimization framework for variational quantum circuits. The optimization dynamics is interpreted as moving in the steepest descent direction with respect to the Quantum Information Geometry, corresponding to the real part of…