Acceleration and Implicit Regularization in Gaussian Phase Retrieval

• URL: http://arxiv.org/abs/2311.12888v1
• Date: Tue, 21 Nov 2023 04:10:03 GMT
• Title: Acceleration and Implicit Regularization in Gaussian Phase Retrieval
• Authors: Tyler Maunu, Martin Molina-Fructuoso
• Abstract summary: In this setting, we prove that methods with Polyak or Nesterov momentum implicit regularization ensures a nice convex descent. Experimental evidence shows that these methods converge faster than gradient descent in practice.
• Score: 5.484345596034159
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study accelerated optimization methods in the Gaussian phase retrieval problem. In this setting, we prove that gradient methods with Polyak or Nesterov momentum have similar implicit regularization to gradient descent. This implicit regularization ensures that the algorithms remain in a nice region, where the cost function is strongly convex and smooth despite being nonconvex in general. This ensures that these accelerated methods achieve faster rates of convergence than gradient descent. Experimental evidence demonstrates that the accelerated methods converge faster than gradient descent in practice.

Related papers

• Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
  We prove new convergence rates for a generalized version of Nesterov acceleration underrho conditions. Our analysis reduces the dependence on the strong growth constant from $$ to $sqrt$ as compared to prior work.
  arXiv  Detail & Related papers  (2024-04-03T00:41:19Z)
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  We consider the finite-sum optimization problem, where each component function is strongly convex and has Lipschitz continuous gradient and Hessian. The recently proposed incremental quasi-Newton method is based on BFGS update and achieves a local superlinear convergence rate. This paper proposes a more efficient quasi-Newton method by incorporating the symmetric rank-1 update into the incremental framework.
  arXiv  Detail & Related papers  (2024-02-04T05:54:51Z)
• Accelerated gradient methods for nonconvex optimization: Escape trajectories from strict saddle points and convergence to local minima [9.66353475649122]
  This paper considers the problem. of understanding convex behavior of a general general of accelerated gradient methods on. non-aptotic functions. It shows that Nesterov's accelerated method (NAG) with variable momentum avoids strict saddle points almost surely.
  arXiv  Detail & Related papers  (2023-07-13T19:11:07Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  An analysis of convex and non- optimization methods often requires the Lipsitzness gradient, which limits the analysis by this trajectorys. Recent work generalizes the gradient setting via the non-uniform smoothness condition.
  arXiv  Detail & Related papers  (2023-06-02T04:21:59Z)
• Proximal Subgradient Norm Minimization of ISTA and FISTA [8.261388753972234]
  We show that the squared proximal subgradient norm for the class of iterative shrinkage-thresholding algorithms converges at an inverse square rate. We also show that the squared proximal subgradient norm for the class of faster iterative shrinkage-thresholding algorithms (FISTA) is accelerated to convergence at an inverse cubic rate.
  arXiv  Detail & Related papers  (2022-11-03T06:50:19Z)
• Riemannian accelerated gradient methods via extrapolation [40.23168342389821]
  We show when the iterates are generated from the gradient descent method, the accelerated scheme achieves the optimal convergence rateally. Our experiments verify the practical benefit of the novel acceleration strategy.
  arXiv  Detail & Related papers  (2022-08-13T10:31:09Z)
• Acceleration Methods [57.202881673406324]
  We first use quadratic optimization problems to introduce two key families of acceleration methods. We discuss momentum methods in detail, starting with the seminal work of Nesterov. We conclude by discussing restart schemes, a set of simple techniques for reaching nearly optimal convergence rates.
  arXiv  Detail & Related papers  (2021-01-23T17:58:25Z)
• Anderson acceleration of coordinate descent [5.794599007795348]
  On multiple Machine Learning problems, coordinate descent achieves performance significantly superior to full-gradient methods. We propose an accelerated version of coordinate descent using extrapolation, showing considerable speed up in practice.
  arXiv  Detail & Related papers  (2020-11-19T19:01:48Z)
• Complexity Guarantees for Polyak Steps with Momentum [76.97851351276165]
  We study a class of methods, based on Polyak steps, where this knowledge is substituted by that of the optimal value, $f_*$. We first show slightly improved convergence bounds than previously known for the classical case of simple gradient descent with Polyak steps, we then derive an accelerated gradient method with Polyak steps and momentum, along with convergence guarantees.
  arXiv  Detail & Related papers  (2020-02-03T17:50:28Z)
• A frequency-domain analysis of inexact gradient methods [0.0]
  We study robustness properties of some iterative gradient-based methods for strongly convex functions. We derive improved analytic bounds for the convergence rate of Nesterov's accelerated method on strongly convex functions.
  arXiv  Detail & Related papers  (2019-12-31T18:47:30Z)
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization [80.03647903934723]
  We prove adaptive gradient methods in expectation of gradient convergence methods. Our analyses shed light on better adaptive gradient methods in optimizing non understanding gradient bounds.
  arXiv  Detail & Related papers  (2018-08-16T20:25:28Z)

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.