Learning to optimize with convergence guarantees using nonlinear system theory

• URL: http://arxiv.org/abs/2403.09389v2
• Date: Mon, 3 Jun 2024 09:10:27 GMT
• Title: Learning to optimize with convergence guarantees using nonlinear system theory
• Authors: Andrea Martin, Luca Furieri,
• Abstract summary: We propose an unconstrained parametrization of algorithms for smooth objective functions. Notably, our framework is directly compatible with automatic differentiation tools.
• Score: 0.4143603294943439
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The increasing reliance on numerical methods for controlling dynamical systems and training machine learning models underscores the need to devise algorithms that dependably and efficiently navigate complex optimization landscapes. Classical gradient descent methods offer strong theoretical guarantees for convex problems; however, they demand meticulous hyperparameter tuning for non-convex ones. The emerging paradigm of learning to optimize (L2O) automates the discovery of algorithms with optimized performance leveraging learning models and data - yet, it lacks a theoretical framework to analyze convergence of the learned algorithms. In this paper, we fill this gap by harnessing nonlinear system theory. Specifically, we propose an unconstrained parametrization of all convergent algorithms for smooth non-convex objective functions. Notably, our framework is directly compatible with automatic differentiation tools, ensuring convergence by design while learning to optimize.

Related papers

• Nonconvex Federated Learning on Compact Smooth Submanifolds With Heterogeneous Data [23.661713049508375]
  We propose an algorithm that learns over a submanifold in the setting of a client. We show that our proposed algorithm converges sub-ly to a neighborhood of a first-order optimal solution by using a novel analysis.
  arXiv  Detail & Related papers  (2024-06-12T17:53:28Z)
• End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty [55.04219793298687]
  The Predict-Then-Forecast (PtO) paradigm in machine learning aims to maximize downstream decision quality. This paper extends the PtO methodology to optimization problems with nondifferentiable Ordered Weighted Averaging (OWA) objectives. It shows how optimization of OWA functions can be effectively integrated with parametric prediction for fair and robust optimization under uncertainty.
  arXiv  Detail & Related papers  (2024-02-12T16:33:35Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information [37.70729542263343]
  We present a novel adaptive optimization algorithm for large-scale machine learning problems. Our method dynamically adapts the direction and step-size. Our methodology does not require a tedious tuning rate tuning.
  arXiv  Detail & Related papers  (2021-09-11T06:39:50Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems. Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
  arXiv  Detail & Related papers  (2021-07-23T13:43:34Z)
• SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients [99.13839450032408]
  It is desired to design a universal framework for adaptive algorithms to solve general problems. In particular, our novel framework provides adaptive methods under non convergence support for setting.
  arXiv  Detail & Related papers  (2021-06-15T15:16:28Z)
• Learning to be Global Optimizer [28.88646928299302]
  We learn an optimal network and escaping capability algorithm for some benchmark functions. We show that the learned algorithm significantly outperforms some well-known classical optimization algorithms.
  arXiv  Detail & Related papers  (2020-03-10T03:46:25Z)
• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks [20.44438519046223]
  We show that wide neural networks satisfy the PL$*$ condition, which explains the (S)GD convergence to a global minimum. We show that wide neural networks satisfy the PL$*$ condition, which explains the (S)GD convergence to a global minimum.
  arXiv  Detail & Related papers  (2020-02-29T17:18:28Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  Adaptivity is an important yet under-studied property in modern optimization theory. Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
  arXiv  Detail & Related papers  (2020-02-13T05:42: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.