HOUDINI: Escaping from Moderately Constrained Saddles

• URL: http://arxiv.org/abs/2205.13753v2
• Date: Thu, 20 Apr 2023 04:26:02 GMT
• Title: HOUDINI: Escaping from Moderately Constrained Saddles
• Authors: Dmitrii Avdiukhin, Grigory Yaroslavtsev
• Abstract summary: We show that (noisy) gradient descent methods can escape from saddle points under a logarithmic number of inequality constraints. Our results hold for both regular and gradient descent.
• Score: 14.277428617774875
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give the first polynomial time algorithms for escaping from high-dimensional saddle points under a moderate number of constraints. Given gradient access to a smooth function $f \colon \mathbb R^d \to \mathbb R$ we show that (noisy) gradient descent methods can escape from saddle points under a logarithmic number of inequality constraints. This constitutes the first tangible progress (without reliance on NP-oracles or altering the definitions to only account for certain constraints) on the main open question of the breakthrough work of Ge et al. who showed an analogous result for unconstrained and equality-constrained problems. Our results hold for both regular and stochastic gradient descent.

Related papers

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  We propose a Trust Sequential Quadratic Programming method to find both first and second-order stationary points. To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a approximation of the objective subject. To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature the reduced Hessian matrix.
  arXiv  Detail & Related papers  (2024-09-24T04:39:47Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  We show that policies under study avoid strict saddle points / submanifolds with probability 1. This result provides an important sanity check as it shows that, almost always, the limit state of an algorithm can only be a local minimizer.
  arXiv  Detail & Related papers  (2023-11-04T11:12:24Z)
• Bridging Discrete and Backpropagation: Straight-Through and Beyond [62.46558842476455]
  We propose a novel approach to approximate the gradient of parameters involved in generating discrete latent variables. We propose ReinMax, which achieves second-order accuracy by integrating Heun's method, a second-order numerical method for solving ODEs.
  arXiv  Detail & Related papers  (2023-04-17T20:59:49Z)
• Adaptive Approximate Implicitization of Planar Parametric Curves via Weak Gradient Constraints [11.559302398966468]
  We introduce a new regularization constraint for both and non-polynomial curves. We then propose two adaptive algorithms of approximate implicitization for both and non-polynomial curves. More precisely, the idea is gradually increasing the implicit degree, until there is no obvious improvement in the weak gradient loss of the outputs.
  arXiv  Detail & Related papers  (2023-02-23T04:08:53Z)
• Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity [34.84170466506512]
  We propose a new zeroth-order hard-thresholding (SZOHT) algorithm with a general ZO gradient estimator powered by a novel random sampling. We find that the query complexity of SZOHT is independent or weakly dependent on the dimensionality under different settings.
  arXiv  Detail & Related papers  (2022-10-11T09:23:53Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm [9.69596041242667]
  An understanding of multiple objective functions in a landscape of strict-saddle points is presented. An analysis of the neighborhoods convergence to a local landscape that has a maximum of strict-saddle points is also presented.
  arXiv  Detail & Related papers  (2021-01-07T16:59:15Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points [9.66353475649122]
  This paper puts forth a rigorous geometric analysis of the gradient-descent method around strict-saddle neighborhoods. It provides a key result that can be used to generate an approximate gradient trajectory for any given initial conditions. The analysis leads to a linear exit-time solution for gradient-descent method under certain necessary initial conditions.
  arXiv  Detail & Related papers  (2020-06-01T17:47:00Z)
• Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
  We generalize the approach Gasnikov et. al., 2017, which allows to solve (stochastic) convex optimization problems with an inexact gradient-free oracle. Our approach reduces $fracnlog n$ times the required number of oracle calls. In the second part of the paper, we analyze the case when such an assumption cannot be made, we propose a general approach on how to modernize the method to solve this problem.
  arXiv  Detail & Related papers  (2020-05-12T16:44:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.