Convergence of Some Convex Message Passing Algorithms to a Fixed Point

• URL: http://arxiv.org/abs/2403.07004v2
• Date: Wed, 5 Jun 2024 12:20:29 GMT
• Title: Convergence of Some Convex Message Passing Algorithms to a Fixed Point
• Authors: Vaclav Voracek, Tomas Werner,
• Abstract summary: A popular approach to the MAP inference problem in graphical models is to minimize an upper bound obtained from a dual linear programming or Lagrangian relaxation by (block-coordinate) descent. This is also known as convex/convergent message passing; examples are max-sum diffusion and sequential tree-reweighted message passing (TRW-S) We show that the algorithm terminates within $mathcalO (1/varepsilon)$ iterations.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A popular approach to the MAP inference problem in graphical models is to minimize an upper bound obtained from a dual linear programming or Lagrangian relaxation by (block-)coordinate descent. This is also known as convex/convergent message passing; examples are max-sum diffusion and sequential tree-reweighted message passing (TRW-S). Convergence properties of these methods are currently not fully understood. They have been proved to converge to the set characterized by local consistency of active constraints, with unknown convergence rate; however, it was not clear if the iterates converge at all (to any point). We prove a stronger result (conjectured before but never proved): the iterates converge to a fixed point of the method. Moreover, we show that the algorithm terminates within $\mathcal{O}(1/\varepsilon)$ iterations. We first prove this for a version of coordinate descent applied to a general piecewise-affine convex objective. Then we show that several convex message passing methods are special cases of this method. Finally, we show that a slightly different version of coordinate descent can cycle.

Related papers

• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
  Subgradient method is one of the most fundamental algorithmic schemes for nonsmooth optimization. In this work, we first extend the typical iteration complexity results for the subgradient method to cover non-Lipschitz convex and weakly convex minimization.
  arXiv  Detail & Related papers  (2023-05-23T15:26:36Z)
• Convex optimization over a probability simplex [0.0]
  We propose a new iteration scheme, the Cauchy-Simplex, to optimize convex problems over the probability simplex. Each iteration of the Cauchy-Simplex consists of simple operations, making it well-suited for high-dimensional problems.
  arXiv  Detail & Related papers  (2023-05-15T22:14:22Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
  The optimistic method has seen increasing popularity for solving convex-concave saddle point problems. We develop a backtracking line search scheme to select the step sizes without knowledge of coefficients.
  arXiv  Detail & Related papers  (2022-02-19T20:31:05Z)
• Coordinate Descent Methods for Fractional Minimization [7.716156977428555]
  We consider a class of structured fractional convex problems in which the numerator part objective is the sum of a differentiable convex non-linear function. This problem is difficult since it is non-smooth convergence. We propose two methods for solving this problem.
  arXiv  Detail & Related papers  (2022-01-30T00:47:04Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  We consider the problem of finding a saddle point for the convex-concave objective $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, where $f$ is a convex function with locally Lipschitz gradient and $g$ is convex and possibly non-smooth. We propose an adaptive version of the Condat-Vu algorithm, which alternates between primal gradient steps and dual steps.
  arXiv  Detail & Related papers  (2021-10-28T14:19:30Z)
• Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
  Non-uniform refinement of objective functions leads to emphNon-uniform Smoothness (NS) and emphNon-uniform Lojasiewicz inequality (NL) New definitions inspire new geometry-aware first-order methods that converge to global optimality faster than the classical $Omega (1/t2)$ lower bounds.
  arXiv  Detail & Related papers  (2021-05-13T04:23:07Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Random extrapolation for primal-dual coordinate descent [61.55967255151027]
  We introduce a randomly extrapolated primal-dual coordinate descent method that adapts to sparsity of the data matrix and the favorable structures of the objective function. We show almost sure convergence of the sequence and optimal sublinear convergence rates for the primal-dual gap and objective values, in the general convex-concave case.
  arXiv  Detail & Related papers  (2020-07-13T17:39:35Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)
• Explicit Regularization of Stochastic Gradient Methods through Duality [9.131027490864938]
  We propose randomized Dykstra-style algorithms based on randomized dual coordinate ascent. For accelerated coordinate descent, we obtain a new algorithm that has better convergence properties than existing gradient methods in the interpolating regime.
  arXiv  Detail & Related papers  (2020-03-30T20:44:56Z)

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.