Optimizing ADMM and Over-Relaxed ADMM Parameters for Linear Quadratic Problems

• URL: http://arxiv.org/abs/2401.00657v1
• Date: Mon, 1 Jan 2024 04:01:40 GMT
• Title: Optimizing ADMM and Over-Relaxed ADMM Parameters for Linear Quadratic Problems
• Authors: Jintao Song, Wenqi Lu, Yunwen Lei, Yuchao Tang, Zhenkuan Pan, Jinming Duan
• Abstract summary: 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.
• Score: 32.04687753889809
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Alternating Direction Method of Multipliers (ADMM) has gained significant attention across a broad spectrum of machine learning applications. Incorporating the over-relaxation technique shows potential for enhancing the convergence rate of ADMM. However, determining optimal algorithmic parameters, including both the associated penalty and relaxation parameters, often relies on empirical approaches tailored to specific problem domains and contextual scenarios. Incorrect parameter selection can significantly hinder ADMM's convergence rate. To address this challenge, in this paper we first propose a general approach to optimize the value of penalty parameter, followed by a novel closed-form formula to compute the optimal relaxation parameter in the context of linear quadratic problems (LQPs). We then experimentally validate our parameter selection methods through random instantiations and diverse imaging applications, encompassing diffeomorphic image registration, image deblurring, and MRI reconstruction.

Related papers

• Accelerating Multi-Block Constrained Optimization Through Learning to Optimize [9.221883233960234]
  Multi-block ADMM-type methods offer substantial reductions in per-it complexity. MPALM shares a similar form with multi-block ADMM and ensures convergence. MPALM's performance is highly sensitive to the choice of penalty parameters. We propose a novel L2O approach that adaptively selects this hyperparameter using supervised learning.
  arXiv  Detail & Related papers  (2024-09-25T19:58:29Z)
• 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)
• Gradient-based bilevel optimization for multi-penalty Ridge regression through matrix differential calculus [0.46040036610482665]
  We introduce a gradient-based approach to the problem of linear regression with l2-regularization. We show that our approach outperforms LASSO, Ridge, and Elastic Net regression. The analytical of the gradient proves to be more efficient in terms of computational time compared to automatic differentiation.
  arXiv  Detail & Related papers  (2023-11-23T20:03:51Z)
• 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)
• Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
  Annealed Importance Sampling (AIS) is a popular algorithm used to estimates the intractable marginal likelihood of deep generative models. We present a parameteric AIS process with flexible intermediary distributions and optimize the bridging distributions to use fewer number of steps for sampling. We assess the performance of our optimized AIS for marginal likelihood estimation of deep generative models and compare it to other estimators.
  arXiv  Detail & Related papers  (2022-09-27T07:58:25Z)
• Sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm [62.997667081978825]
  We propose a computationally efficient and powerful Bayesian approach for sparse high-dimensional linear regression. Minimal prior assumptions on the parameters are used through the use of plug-in empirical Bayes estimates. The proposed approach is implemented in the R package probe.
  arXiv  Detail & Related papers  (2022-09-16T19:15:50Z)
• 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)
• Alternating Direction Method of Multipliers for Quantization [15.62692130672419]
  We study the performance of the Alternating Direction Method of Multipliers for Quantization ($texttADMM-Q$) algorithm. We develop a few variants of $texttADMM-Q$ that can handle inexact update rules. We empirically evaluate the efficacy of our proposed approaches.
  arXiv  Detail & Related papers  (2020-09-08T01:58:02Z)
• Variable selection for Gaussian process regression through a sparse projection [0.802904964931021]
  This paper presents a new variable selection approach integrated with Gaussian process (GP) regression. The choice of tuning parameters and the accuracy of the estimation are evaluated with the simulation some chosen benchmark approaches.
  arXiv  Detail & Related papers  (2020-08-25T01:06:10Z)
• Implicit differentiation of Lasso-type models for hyperparameter optimization [82.73138686390514]
  We introduce an efficient implicit differentiation algorithm, without matrix inversion, tailored for Lasso-type problems. Our approach scales to high-dimensional data by leveraging the sparsity of the solutions.
  arXiv  Detail & Related papers  (2020-02-20T18:43:42Z)
• Multi-Task Multicriteria Hyperparameter Optimization [77.34726150561087]
  The article begins with a mathematical formulation of the problem of choosing optimal hyperparameters. The steps of the MTMC method that solves this problem are described. The proposed method is evaluated on the image classification problem using a convolutional neural network.
  arXiv  Detail & Related papers  (2020-02-15T12:47:53Z)

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.