We establish that first-order methods avoid saddle points for almost all initializations. Our results apply to a wide variety of first-order methods, including gradient descent, block coordinate descent, mirror descent and variants thereof. The connecting thread is that such algorithms can be studied from a dynamical s…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “Saddle point avoidance”
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.
Nonconvex optimization algorithms with random initialization have attracted increasing attention recently. It has been showed that many first-order methods always avoid saddle points with random starting points. In this paper, we answer a question: can the nonconvex heavy-ball algorithms with random initialization avoi…
Loss functions with a large number of saddle points are one of the major obstacles for training modern machine learning models efficiently. First-order methods such as gradient descent are usually the methods of choice for training machine learning models. However, these methods converge to saddle points for certain ch…
We provide larger step-size restrictions for which gradient descent based algorithms (almost surely) avoid strict saddle points. In particular, consider a twice differentiable (non-convex) objective function whose gradient has Lipschitz constant L and whose Hessian is well-behaved. We prove that the probability of init…
We consider the case of derivative-free algorithms for non-convex optimization, also known as zero order algorithms, that use only function evaluations rather than gradients. For a wide variety of gradient approximators based on finite differences, we establish asymptotic convergence to second order stationary points u…
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.
In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization, with a focus on addressing constrained optimization, high-dimensional setting and saddle-point avoiding. To handle constrained optimization, we first propose generalizations of the conditional g…
Optimizes bond portfolios to avoid worst-case losses.
problem Finding the worst-case value of a bond portfolio over a range of yield curves and spreads.
method Solves a convex-concave saddle point optimization problem to find the worst-case value and construct a robust portfolio.
result Constructs a bond portfolio that includes the worst-case value, ensuring robustness against market uncertainties.
GenFlow optimizes faster, avoiding saddle points in fixed time.
problem Designing efficient optimization algorithms for convex and non-convex functions.
method Introduces GenFlow and momentum variants with fixed-time convergence guarantees.
result GenFlow and momentum variants converge to optimal solutions in fixed time for PL functions and evade saddle points uniformly.
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.
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.
A new method avoids saddle points in Newton's method.
problem Avoiding saddle points in optimization problems.
method New Q-Newton's method with specific update rule.
result The method guarantees convergence to a critical point that is not a saddle point.
Two new algorithms improve reinforcement learning by avoiding saddle points.
problem Control in reinforcement learning without model information.
method Cubic-regularized Policy Newton algorithms using likelihood ratio method.
result Convergence to a second-order stationary point with improved sample complexity.
New method for causal effect estimation with hidden confounders.
problem Estimating causal effects in the presence of hidden confounders.
method Singular value decomposition of a conditional expectation operator followed by saddle-point optimization.
result Our method outperforms existing methods on common benchmarks.
New Q-Newton's method avoids saddle points and converges quadratically.
problem Optimizing functions with saddle points and ensuring convergence guarantees.
method Modified New Q-Newton's method with Backtracking line search.
result Theorem for Morse functions: quadratic convergence to local minima.
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.
Gradient descent (GD) and stochastic gradient descent (SGD) are the workhorses of large-scale machine learning. While classical theory focused on analyzing the performance of these methods in convex optimization problems, the most notable successes in machine learning have involved nonconvex optimization, and a gap has…
A distributed optimization method solves saddle point problems with strong concavity and convexity.
problem Solving saddle point problems with distributed and heterogeneous data.
method GT-GDA, a distributed first-order method using gradient tracking and consensus over coupling matrices.
result GT-GDA converges linearly to the unique saddle point solution under specific conditions.
Oracle-efficient algorithm for offline RL with partial data coverage.
problem Offline reinforcement learning with partial data coverage and constraints.
method PDOCRL, a primal-dual algorithm with decomposed linear-programming formulation.
result Near-optimal, near-feasible policy with \(\widetilde{\mathcal O}(ε^{-2})\) sample guarantee.
New algorithm provably converges to second-order stationary points in NMF.
problem Understanding convergence to local minima in NMF.
method Multiplicative weight update dynamics, concurrent updates, and simplex reduction.
result Provable convergence to second-order stationary points.
The paper studies quadratic neural networks, proving existence of spurious minima and saddle points.
problem Understanding the loss landscape of neural networks with quadratic activations.
method Theoretical analysis of mean squared error loss for neural networks with quadratic activations.
result Proves existence of spurious local minima and saddle points in the training landscape of deep overparameterized quadratic neural networks.
Paper analyzes Transformer learning dynamics, proving benign landscape for in-context learning.
problem Understanding how Transformers learn in context with nonlinear features.
method Mean-field and two-timescale analysis of Transformer dynamics, proving nonconvex but benign landscape.
result Proves mean-field dynamics avoid saddle points, leading to improved optimization.
Flexible algorithms for maximizing rewards in structured bandits.
problem Reward maximization in structured stochastic multi-armed bandit problems.
method Asymptotically optimal algorithms using iterative saddle-point solvers.
result Achieves optimal performance with minimal computational burden.
Proposes a new method for GNNs that avoids iterative node state convergence.
problem Iterative computation of node states in GNNs is inefficient and requires many epochs.
method Constrained optimization in the Lagrangian framework to learn transition function and node states simultaneously.
result The proposed method compares favorably with existing models on various benchmarks.
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.
Paper studies stochastic optimization methods with momentum, proving convergence and avoiding traps.
problem Optimizing non-convex functions with momentum.
method Unified analysis of stochastic gradient descent variants, including S-NAG and Adam.
result Convergence to critical points and avoidance of undesired critical points like local maxima or saddle points.
Saddle-point optimization problems are an important class of optimization problems with applications to game theory, multi-agent reinforcement learning and machine learning. A majority of the rich literature available for saddle-point optimization has focused on the offline setting. In this paper, we study nonstationar…
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.
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 .
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.
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.
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.
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.
Gradient-based optimization methods are the most popular choice for finding local optima for classical minimization and saddle point problems. Here, we highlight a systemic issue of gradient dynamics that arise for saddle point problems, namely the presence of undesired stable stationary points that are no local optima…
Complex-valued neural networks avoid spurious local minima.
problem Finding spurious local minima in neural networks.
method Proved no spurious local minima for shallow complex neural networks with quadratic activations.
result Complex-valued weights eliminate spurious local minima in neural networks.
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.
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
Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equationsmath.OC
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.
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.
L2R learns to denoise images without needing noise distribution knowledge.
problem Traditional denoising methods require noise distribution knowledge, limiting their applicability.
method L2R uses a learnable monotonic neural network to learn recorruption without distribution knowledge.
result L2R achieves state-of-the-art performance across various noise distributions.
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 larger than any other singular value.
Malware is constantly adapting in order to avoid detection. Model based malware detectors, such as SVM and neural networks, are vulnerable to so-called adversarial examples which are modest changes to detectable malware that allows the resulting malware to evade detection. Continuous-valued methods that are robust to a…
Paper defines saddle points in asymmetric Dynkin games using martingale theory.
problem Tackles saddle point conditions in asymmetric Dynkin games with partial information.
method Uses martingale theory to identify super and submartingales related to equilibrium payoffs.
result Characterizes saddle point strategies in terms of equilibrium payoffs' dynamics and Doob-Meyer decompositions.
Algorithm classifies saddle-focus singularities in Hamiltonian systems.
problem Classifying nondegenerate saddle-focus singularities in integrable Hamiltonian systems.
method Developed an algorithm based on semi-local equivalence to represent singularities as almost direct products.
result Obtained complete lists of saddle-focus singularities of complexities 1, 2, and 3.