New insights into matrix factorization show strict saddles have bounded eigenvalues.
problem Understanding the nature of critical points in matrix factorization.
method Analyzing orbits of critical points under the general linear group and identifying canonical points.
result Minimum eigenvalue of strict saddles is not uniformly bounded below zero.
New methods help escape strict saddle points in nonsmooth optimization.
problem Escaping strict saddle points in nonsmooth optimization.
method An inexact stochastically perturbed gradient method applied to the Moreau envelope.
result A variety of algorithms for nonsmooth optimization can efficiently escape strict saddle points of the Moreau envelope.
Gradient descent can use larger step sizes to avoid strict saddle points.
problem Avoiding strict saddle points in non-convex optimization.
method Proving that gradient descent with step-size up to 2/L avoids strict saddle points with high probability.
result Gradient descent with step-size up to 2/L almost surely avoids strict saddle points.
New theory explains how momentum SGD helps avoid saddle points in nonconvex optimization.
problem Understanding convergence properties of Momentum SGD in nonconvex optimization.
method Diffusion approximations for nonconvex optimization problems with strict saddle points and isolated local optima.
result Momentum helps escape from saddle points but hurts convergence near optima.
Proximal methods avoid local minima in weakly convex problems.
problem Weakly convex optimization problems with strict saddle properties.
method Proximal methods on nonsmooth functions with strict saddle guarantees.
result Proximal methods converge to local minimizers only, when initialized randomly.
New method speeds up GAN training by solving saddle point problem.
problem Slow convergence in training Generative Adversarial Networks (GANs).
method Fluid flow mass transport formulation for strict minimization.
result Quick convergence and meaningful metrics in optimization.
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…
New algorithm finds local minima in non-convex, non-smooth problems.
problem Finding local minimizers in non-convex and non-smooth optimization.
method Perturbed Proximal Descent, tailored for non-smooth cases.
result First known results for non-smooth optimization.
New theory shows predictive coding makes learning landscape easier to navigate.
problem Understanding the impact of predictive coding's inference procedure on learning efficiency.
method Analyzed the geometry of the energy landscape of deep linear networks, proving many non-strict saddles become strict in the equilibrated energy.
result All highly degenerate (non-strict) saddles of the loss become strict in the equilibrated energy, suggesting a more robust learning landscape.
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. A new method helps escape saddle points in non-convex optimization.
problem Escaping saddle points in non-convex optimization problems.
method CNC-SCSG method using a separate SGD step to help escape from strict saddle points.
result The method converges to a second-order stationary point with a rate of O(ε−2log(1/ε)). Riemannian gradient descent escapes some spurious critical points on low-rank matrix manifold.
problem Spurious critical points on the boundary of low-rank matrix manifold.
method Riemannian gradient descent with dynamical low-rank approximation and rescaled gradient flow.
result Riemannian gradient descent escapes some spurious critical points on the boundary of the manifold.
New algorithm helps escape saddle points in optimization problems.
problem Optimizing smooth non-convex functions to avoid saddle points.
method Perturbed Saddle-escape Descent (PSD) algorithm with explicit constants.
result PSD finds approximate second-order stationary points efficiently.
WSFN overcomes saddle points for non-convex functionals in Wasserstein space.
problem Minimizing non-convex functionals over the Wasserstein space with saddle point avoidance.
method WSFN is a second-order method that preconditions the Wasserstein gradient to avoid saddle points.
result WSFN escapes saddle regions and reaches a global minimizer in polynomial time.
New guarantees for SGD in non-convex optimization without strict noise bounds.
problem Efficiently escaping saddle points in non-convex optimization.
method Mean-square arguments and relaxed gradient noise variance bounds.
result Gradient descent can efficiently escape saddle points with a more relaxed gradient noise variance bound.
Linear speedup achieved in non-convex optimization for decentralized systems.
problem Achieving optimal performance in decentralized non-convex optimization.
method Examined the dependence of convergence guarantees on spectral properties of combination policies.
result Linear speedup in saddle-point escape time for symmetric combination policies.
SGD avoids critical points on weakly convex functions.
problem Non-convergence of SGD to critical points on specific manifolds.
method Stochastic subgradient descent, Verdier stratification, angle condition.
result SGD converges to local minimizers on weakly convex functions.
We propose a general theory for studying the \xl{landscape} of nonconvex \xl{optimization} with underlying symmetric structures \tz{for a class of machine learning problems (e.g., low-rank matrix factorization, phase retrieval, and deep linear neural networks)}. In specific, we characterize the locations of stationary …
Stochastic subgradient descent avoids critical points in definable functions.
problem Finding local minima in definable functions.
method Stochastic subgradient descent with density-like perturbation.
result SGD converges to a local minimum in definable functions.
Algorithm checks local optimality and escapes saddles in ReLU networks.
problem Checking local optimality and escaping saddles in ReLU networks with nondifferentiable points.
method Polyhedral geometry to reduce complexity, exploiting convex and nonconvex QPs.
result Algorithm efficiently solves local optimality and saddle point issues in ReLU networks.
SGD converges almost surely in non-convex problems, avoiding saddle points and accelerating convergence.
problem Understanding convergence of SGD in non-convex optimization problems.
method Analysis of SGD trajectories, focusing on boundedness, convergence to strict saddle points, and rate of convergence.
result SGD converges almost surely to a minimizer in non-convex problems, avoiding strict saddle points.
Optimistic mirror descent improves convergence in saddle-point problems.
problem Training generative adversarial networks (GANs) with saddle-point problems.
method Analyzed mirror descent (MD) and optimistic mirror descent (OMD) in coherent non-monotone problems.
result Optimistic mirror descent converges in all coherent problems, improving upon vanilla MD.
Paper explains neural collapse in neural networks using a new model.
problem Understanding neural collapse in neural networks during training.
method Introducing the unconstrained layer-peeled model (ULPM) to prove gradient flow convergence to critical points of a minimum-norm separation problem.
result Proves that all critical points are strict saddle points except the global minimizers exhibiting neural collapse.
Gradient descent trains both layers of a ReLU network to fit a linear model.
problem Training dynamics of a ReLU network to fit a linear target function.
method Jointly training both layers of a one-hidden-layer ReLU network in a realizable setting with Gaussian inputs and labels.
result Gradient descent from a small random initialization converges to a global minimizer at a linear rate with optimal sample complexity.
We provide two fundamental results on the population (infinite-sample) likelihood function of Gaussian mixture models with M≥3 components. Our first main result shows that the population likelihood function has bad local maxima even in the special case of equally-weighted mixtures of well-separated and spherical…
This work justifies neural collapse under MSE loss and analyzes the optimization landscape.
problem Understanding neural collapse in deep neural networks under MSE loss.
method Global landscape analysis of vanilla nonconvex MSE loss.
result The only global minimizers are neural collapse solutions.
Paper analyzes algorithms for nonstationary saddle-point optimization problems.
problem Nonstationary saddle-point optimization problems in game theory, reinforcement learning, and machine learning.
method Proposes extragradient and Frank-Wolfe algorithms for online and bandit settings.
result Establishes sub-linear regret bounds for the proposed algorithms.
Gradient-based methods struggle with saddle points; curvature exploitation helps.
problem Gradient-based methods struggle with saddle points, leading to undesired stable stationary points.
method Exploits curvature information to escape undesired stationary points.
result Different optimization methods, including gradient and Adagrad, can escape non-optimal stationary points when curvature exploitation is used.
Heavy-ball algorithms can always avoid saddle points with random initialization.
problem Optimizing nonconvex functions with saddle points.
method Developed a new mapping to interpret heavy-ball algorithms as iterations, proving they can escape saddle points.
result Heavy-ball algorithms can escape saddle points with random initialization.
Develops algorithm to escape saddle points in Byzantine settings.
problem Byzantine workers create fake local minima near saddle points.
method ByzantinePGD, a robust first-order algorithm.
result Converges to approximate true local minimizer with low iteration complexity.
FeDualEx tackles saddle point optimization in federated learning with composite objectives.
problem Saddle point optimization with constraints and non-smooth regularization in federated learning.
method Federated Dual Extrapolation (FeDualEx) algorithm for saddle point optimization and composite objectives.
result FeDualEx effectively solves saddle point optimization problems with composite objectives in federated learning.
Unified analysis of EG and OGDA for saddle point problems using proximal point method.
problem Solving saddle point problems in bilinear and strongly convex-strongly concave settings.
method Unified analysis as approximations of the proximal point method.
result Unified analysis of EG and OGDA for saddle point problems.
First-order methods avoid saddle points for most initializations.
problem Avoiding saddle points in optimization problems.
method First-order methods, including gradient descent and variants, analyzed using dynamical systems and the Stable Manifold Theorem.
result First-order methods avoid saddle points for almost all initializations.
Gradient descent can take exponentially long to escape saddle points in 2D.
problem Worst-case inefficiency of gradient descent in non-convex optimization.
method Analysis of gradient descent's performance on 2D functions.
result Gradient descent can take exponentially long to escape saddle points.
A new method avoids saddle points in training machine learning models.
problem Training machine learning models efficiently in the presence of saddle points.
method Modified Laplacian smoothing gradient descent (mLSGD).
result The attraction region for mLSGD is significantly smaller than for gradient descent, avoiding saddle points.
New algorithm speeds up solving saddle-point problems with large condition numbers.
problem Solving saddle-point problems with large condition numbers.
method Proposes a stochastic proximal point algorithm that accelerates variance reduction methods.
result Reduces logarithmic term of condition number for iteration complexity.
A new algorithm trains deep neural networks by adding neurons greedily.
problem Training deep neural networks efficiently and effectively.
method Neuron Pursuit (NP) algorithm, which alternates between neuron addition and loss minimization.
result The algorithm can train deep neural networks efficiently and effectively.
New method solves saddle-point problems faster than existing methods.
problem Large-scale saddle-point problems in optimization.
method Sequential subspace optimization with proximal regularization.
result Significantly better convergence compared to first-order methods.
This paper extends Newton's method to distributed learning, avoiding saddle points and handling Byzantine workers.
problem Avoiding saddle points in distributed non-convex optimization, especially in the presence of Byzantine workers.
method Extends cubic-regularized Newton method to distributed framework, addressing communication bottlenecks and Byzantine attacks.
result The method achieves improved iteration complexity compared to first-order methods, with a 25% improvement in experiments.
PWGF escapes saddle points in nonconvex optimization.
problem Escaping saddle points in nonconvex optimization.
method PWGF uses noisy perturbations via Gaussian process to escape saddle points.
result PWGF achieves second-order optimality for nonconvex objectives.
DLNs dynamics change with variance, leading to saddle-to-saddle training phases.
problem Understanding the dynamics of DLNs with varying initialization variance.
method Analyzing the phase transition of DLNs' dynamics as variance changes.
result Gradient descent visits a sequence of saddles, reaching a sparse global minimum.
This paper develops methods to solve saddle-point problems on Riemannian manifolds with exponential stability.
problem Solving saddle-point problems on Riemannian manifolds with exponential stability.
method Developed a projected dynamical system on a Riemannian manifold to solve saddle-point problems, leveraging the strong monotonicity of the gradient of the Lagrangian function.
result Established exponential stability and convergence of the projected dynamical system to the unique saddle-point.
Last iterate of Extragradient algorithm converges slower than averaged iterates in saddle point problems.
problem Smooth convex-concave saddle point problems
method Analysis of Extragradient (EG) algorithm convergence rates
result The last iterate of EG converges at a rate of O(1/√T), compared to O(1/T) for averaged iterates
New ODE models show saddle-point optimization methods converge differently, with last-iterate convergence for OGDA.
problem Analyzing convergence properties of saddle-point optimization methods.
method High-Resolution Differential Equations (HRDEs) to design differential equation models for saddle-point optimization methods.
result HRDEs reveal last-iterate convergence for Optimistic Gradient Descent Ascent (OGDA) in bilinear games.
We optimize saddle-point problems for large-scale Markov decision processes.
problem Optimizing policies in large-scale Markov decision processes.
method Characterized conditions for convergence and designed an optimization algorithm.
result Our algorithm converges faster and is state-space independent.
Study on neural networks in overparameterized cases, focusing on flat minima and saddle points.
problem Understanding the landscape of training error in neural networks with overparameterization.
method Three methods of embedding a network into a wider one with more hidden units, analyzing the embedded point's properties.
result Smooth and ReLU activation networks have different partially flat landscapes around the embedded point.
Houdini finds high-dimensional saddle points under few constraints.
problem Escaping from saddle points in high-dimensional spaces with constraints.
method Gradient descent methods under logarithmic inequality constraints.
result Polynomial time algorithms for escaping saddle points under constraints.
Extends saddle-point method for large-time volatility smiles.
problem Analyzing large-time volatility smiles in financial models.
method Saddle-point approach to derive large-time model-implied volatility smiles.
result Provides theoretical foundation and wide class of arbitrage-free parametrizations.