Efficient proximal gradient algorithms for joint graphical lasso

• URL: http://arxiv.org/abs/2107.07799v1
• Date: Fri, 16 Jul 2021 09:59:13 GMT
• Title: Efficient proximal gradient algorithms for joint graphical lasso
• Authors: Jie Chen, Ryosuke Shimmura and Joe Suzuki
• Abstract summary: We consider learning an undirected graphical model from sparse data. We propose proximal gradient procedures with and without a backtracking option for the joint graphical lasso (JGL) The proposed algorithms can achieve high accuracy and precision, and their efficiency is competitive with state-of-the-art algorithms.
• Score: 9.752101654013053
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider learning an undirected graphical model from sparse data. While several efficient algorithms have been proposed for graphical lasso (GL), the alternating direction method of multipliers (ADMM) is the main approach taken concerning for joint graphical lasso (JGL). We propose proximal gradient procedures with and without a backtracking option for the JGL. These procedures are first-order and relatively simple, and the subproblems are solved efficiently in closed form. We further show the boundedness for the solution of the JGL problem and the iterations in the algorithms. The numerical results indicate that the proposed algorithms can achieve high accuracy and precision, and their efficiency is competitive with state-of-the-art algorithms.

Related papers

• Learning the hub graphical Lasso model with the structured sparsity via an efficient algorithm [1.0923877073891446]
  We introduce a two-phase algorithm to estimate hub graphical models. The proposed algorithm first generates a good initial point via a dual alternating direction method of multipliers. It then warms a semismooth Newton (SSN) based augmented Lagrangian method (ALM) to compute a solution that is accurate enough for practical tasks.
  arXiv  Detail & Related papers  (2023-08-17T08:24:28Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning Problems [0.7614628596146599]
  We propose a novel algorithm for adaptive step length selection in the classical SGD framework. Under reasonable conditions, the algorithm produces step lengths in line with well-established theoretical requirements. We show that the algorithm can generate step lengths comparable to the best step length obtained from manual tuning.
  arXiv  Detail & Related papers  (2023-05-17T06:22:11Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  We propose a novel doubly accelerated gradient descent (ADSGD) method for sparsity regularized loss minimization problems. We first prove that ADSGD can achieve a linear convergence rate and lower overall computational complexity.
  arXiv  Detail & Related papers  (2022-08-11T22:27:22Z)
• Learning Sparse Graphs via Majorization-Minimization for Smooth Node Signals [8.140698535149042]
  We propose an algorithm for learning a sparse weighted graph by estimating its adjacency matrix. We show that the proposed algorithm converges faster, in terms of the average number of iterations, than several existing methods in the literature.
  arXiv  Detail & Related papers  (2022-02-06T17:06:13Z)
• Graph Matching via Optimal Transport [11.93151370164898]
  Solving the graph matching problem is increasingly important due to it's applications in operations research, computer vision, neuroscience, and more. Current state-of-the-art algorithms are inefficient in matching very large graphs, though they produce good accuracy. We present GOAT, a modification to the state-of-the-art graph matching approximation algorithm "FAQ" (Vogelstein, 2015), replacing its linear sum assignment step with the "Lightspeed Optimal Transport" method of Cuturi (2013).
  arXiv  Detail & Related papers  (2021-11-09T19:18:18Z)
• Individually Fair Gradient Boosting [86.1984206610373]
  We consider the task of enforcing individual fairness in gradient boosting. We show that our algorithm converges globally and generalizes. We also demonstrate the efficacy of our algorithm on three ML problems susceptible to algorithmic bias.
  arXiv  Detail & Related papers  (2021-03-31T03:06:57Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  We consider the task of decentralized minimization of the sum of smooth strongly convex functions stored across the nodes of a network. We propose two new algorithms for this decentralized optimization problem and equip them with complexity guarantees.
  arXiv  Detail & Related papers  (2020-06-21T11:23:20Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)

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.