A General Continuous-Time Formulation of Stochastic ADMM and Its Variants

• URL: http://arxiv.org/abs/2404.14358v1
• Date: Mon, 22 Apr 2024 17:12:58 GMT
• Title: A General Continuous-Time Formulation of Stochastic ADMM and Its Variants
• Authors: Chris Junchi Li,
• Abstract summary: We introduce a unified algorithmic framework called generalized ADMM. Our continuous-time analysis provides us with new insights into ADMM and variants. We prove that under some proper scaling, the trajectory of ADMM weakly converges to the solution of a differential equation with small noise.
• Score: 5.269633789700637
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic versions of the alternating direction method of multiplier (ADMM) and its variants play a key role in many modern large-scale machine learning problems. In this work, we introduce a unified algorithmic framework called generalized stochastic ADMM and investigate their continuous-time analysis. The generalized framework widely includes many stochastic ADMM variants such as standard, linearized and gradient-based ADMM. Our continuous-time analysis provides us with new insights into stochastic ADMM and variants, and we rigorously prove that under some proper scaling, the trajectory of stochastic ADMM weakly converges to the solution of a stochastic differential equation with small noise. Our analysis also provides a theoretical explanation of why the relaxation parameter should be chosen between 0 and 2.

Related papers

• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  We tackle the general differentiable meta learning problem that is ubiquitous in modern deep learning. These problems are often formalized as Bi-Level optimizations (BLO) We introduce a novel perspective by turning a given BLO problem into a ii optimization, where the inner loss function becomes a smooth distribution, and the outer loss becomes an expected loss over the inner distribution.
  arXiv  Detail & Related papers  (2024-10-14T12:10:06Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• Optimizing ADMM and Over-Relaxed ADMM Parameters for Linear Quadratic Problems [32.04687753889809]
  Alternating Direction Method of Multipliers (ADMM) has gained significant attention across a broad spectrum of machine learning applications. We propose a general approach to optimize the value of penalty parameter, followed by a novel closed-form formula to compute the optimal relaxation parameter. We then experimentally validate our parameter selection methods through random instantiations and diverse imaging applications.
  arXiv  Detail & Related papers  (2024-01-01T04:01:40Z)
• Moreau Envelope ADMM for Decentralized Weakly Convex Optimization [55.2289666758254]
  This paper proposes a proximal variant of the alternating direction method of multipliers (ADMM) for distributed optimization. The results of our numerical experiments indicate that our method is faster and more robust than widely-used approaches.
  arXiv  Detail & Related papers  (2023-08-31T14:16:30Z)
• Markov Chain Monte Carlo for Continuous-Time Switching Dynamical Systems [26.744964200606784]
  We propose a novel inference algorithm utilizing a Markov Chain Monte Carlo approach. The presented Gibbs sampler allows to efficiently obtain samples from the exact continuous-time posterior processes.
  arXiv  Detail & Related papers  (2022-05-18T09:03:00Z)
• A Distributed Algorithm for Measure-valued Optimization with Additive Objective [1.0965065178451106]
  We propose a distributed nonvalued algorithm for solving measure-parametric optimization problems with additive objectives. The proposed algorithm comprises a two-layer alternating direction multipliers (ADMM) The overall algorithm realizes operator splitting gradient for flows in the manifold of probability measures.
  arXiv  Detail & Related papers  (2022-02-17T23:09:41Z)
• Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods [73.35353358543507]
  Gradient Descent-Ascent (SGDA) is one of the most prominent algorithms for solving min-max optimization and variational inequalities problems (VIP) In this paper, we propose a unified convergence analysis that covers a large variety of descent-ascent methods. We develop several new variants of SGDA such as a new variance-reduced method (L-SVRGDA), new distributed methods with compression (QSGDA, DIANA-SGDA, VR-DIANA-SGDA), and a new method with coordinate randomization (SEGA-SGDA)
  arXiv  Detail & Related papers  (2022-02-15T09:17:39Z)
• A Framework of Inertial Alternating Direction Method of Multipliers for Non-Convex Non-Smooth Optimization [17.553531291690025]
  We propose an algorithmic framework dubbed alternating methods of multipliers (iADMM) for solving a class of non nonsmooth multiblock composite problems. Our framework employs the general-major surrogateization (MM) principle to update each block of variables to unify the convergence analysis of previous ADMM schemes.
  arXiv  Detail & Related papers  (2021-02-10T13:55:28Z)
• The Variational Method of Moments [65.91730154730905]
  conditional moment problem is a powerful formulation for describing structural causal parameters in terms of observables. Motivated by a variational minimax reformulation of OWGMM, we define a very general class of estimators for the conditional moment problem. We provide algorithms for valid statistical inference based on the same kind of variational reformulations.
  arXiv  Detail & Related papers  (2020-12-17T07:21:06Z)
• A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces [53.47210316424326]
  KeRNS is an algorithm for episodic reinforcement learning in non-stationary Markov Decision Processes. We prove a regret bound that scales with the covering dimension of the state-action space and the total variation of the MDP with time.
  arXiv  Detail & Related papers  (2020-07-09T21:37:13Z)
• Stochastic Modified Equations for Continuous Limit of Stochastic ADMM [13.694172299830315]
  We put different variants of ADMM into a unified form, which includes standard, linearized and gradient-based ADMM with relaxation, and study their dynamics via a continuous-time model approach. We show that the dynamics of ADMM is approximated by a class of differential equations with small noise parameters in the sense of weak approximation.
  arXiv  Detail & Related papers  (2020-03-07T08:01:50Z)

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.