Adaptive Coordinate-Wise Step Sizes for Quasi-Newton Methods: A Learning-to-Optimize Approach

• URL: http://arxiv.org/abs/2412.00059v1
• Date: Mon, 25 Nov 2024 07:13:59 GMT
• Title: Adaptive Coordinate-Wise Step Sizes for Quasi-Newton Methods: A Learning-to-Optimize Approach
• Authors: Wei Lin, Qingyu Song, Hong Xu,
• Abstract summary: We introduce a novel Learning-to-(L2O) model within the Broyden-Fletcher-Goldfarb-Shanno framework, which leverages neural networks to predict optimal coordinate-wise step sizes. Our approach achieves substantial improvements over traditional backtracking line search and hypergradient descent-based methods.
• Score: 9.82454981262489
• License:
• Abstract: Tuning effective step sizes is crucial for the stability and efficiency of optimization algorithms. While adaptive coordinate-wise step sizes tuning methods have been explored in first-order methods, second-order methods still lack efficient techniques. Current approaches, including hypergradient descent and cutting plane methods, offer limited improvements or encounter difficulties in second-order contexts. To address these challenges, we introduce a novel Learning-to-Optimize (L2O) model within the Broyden-Fletcher-Goldfarb-Shanno (BFGS) framework, which leverages neural networks to predict optimal coordinate-wise step sizes. Our model integrates a theoretical foundation that establishes conditions for the stability and convergence of these step sizes. Extensive experiments demonstrate that our approach achieves substantial improvements over traditional backtracking line search and hypergradient descent-based methods, offering up to 7$\times$ faster and stable performance across diverse optimization tasks.

Related papers

• Training Deep Learning Models with Norm-Constrained LMOs [56.00317694850397]
  We study optimization methods that leverage the linear minimization oracle (LMO) over a norm-ball. We propose a new family of algorithms that uses the LMO to adapt to the geometry of the problem and, perhaps surprisingly, show that they can be applied to unconstrained problems.
  arXiv  Detail & Related papers  (2025-02-11T13:10:34Z)
• Aligning Few-Step Diffusion Models with Dense Reward Difference Learning [81.85515625591884]
  Stepwise Diffusion Policy Optimization (SDPO) is an alignment method tailored for few-step diffusion models. SDPO incorporates dense reward feedback at every intermediate step to ensure consistent alignment across all denoising steps. SDPO consistently outperforms prior methods in reward-based alignment across diverse step configurations.
  arXiv  Detail & Related papers  (2024-11-18T16:57:41Z)
• An Adaptive Dimension Reduction Estimation Method for High-dimensional Bayesian Optimization [6.79843988450982]
  We propose a two-step optimization framework to extend BO to high-dimensional settings. Our algorithm offers the flexibility to operate these steps either concurrently or in sequence. Numerical experiments validate the efficacy of our method in challenging scenarios.
  arXiv  Detail & Related papers  (2024-03-08T16:21:08Z)
• SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithms [1.21748738176366]
  Techniques such as Adam, AdaGrad, and AdaHessian utilize a preconditioner that the search impacts by incorporating the curvature of the objective function. This paper proposes SANIA to tackle these challenges.
  arXiv  Detail & Related papers  (2023-12-28T21:28:08Z)
• Locally Optimal Descent for Dynamic Stepsize Scheduling [45.6809308002043]
  We introduce a novel dynamic learning scheduling scheme grounded in theory with the goal of simplifying the manual and time-consuming tuning of schedules in phases. Our approach is based on estimating a locally-optimal practice tuning-rate in the direction of a smooth gradient. Our findings indicate that our method needs minimal tuning when compared to existing approaches.
  arXiv  Detail & Related papers  (2023-11-23T09:57:35Z)
• Adaptive Learning Rates for Faster Stochastic Gradient Methods [6.935471115003109]
  We propose new adaptive step size strategies that improve several quadratic convex gradient methods. Our first method is based on the classical Polyak step size (Polyak, 1987) and is an extension of the recent development of this method. Our second method, denoted GraDS, rescales step size by "diversity of gradients"
  arXiv  Detail & Related papers  (2022-08-10T11:36:00Z)
• Local Quadratic Convergence of Stochastic Gradient Descent with Adaptive Step Size [29.15132344744801]
  We establish local convergence for gradient descent with adaptive step size for problems such as matrix inversion. We show that these first order optimization methods can achieve sub-linear or linear convergence.
  arXiv  Detail & Related papers  (2021-12-30T00:50:30Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  We introduce a class of first-order methods for smooth constrained optimization. Two distinctive features of our approach are that projections or optimizations over the entire feasible set are avoided. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear.
  arXiv  Detail & Related papers  (2021-07-17T11:45:13Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  We show that an increasing large momentum parameter for the first-order moment is sufficient for adaptive scaling. We also give insights for increasing the momentum in a stagewise manner in accordance with stagewise decreasing step size.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• 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)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)

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.