Variable Bregman Majorization-Minimization Algorithm and its Application to Dirichlet Maximum Likelihood Estimation

• URL: http://arxiv.org/abs/2501.07306v2
• Date: Wed, 05 Feb 2025 10:54:19 GMT
• Title: Variable Bregman Majorization-Minimization Algorithm and its Application to Dirichlet Maximum Likelihood Estimation
• Authors: Ségolène Martin, Jean-Christophe Pesquet, Gabriele Steidl, Ismail Ben Ayed,
• Abstract summary: We propose a novel Bregman descent algorithm for minimizing a convex function that is expressed as the sum of a differentiable part and a possibly nonsmooth term. The approach, referred to as the Variable Bregman Majorization-Minimization (VBMM) algorithm, extends the Bregman Proximal Gradient method. Numerical experiments confirm that the VBMM algorithm outperforms existing approaches in terms of convergence speed.
• Score: 26.384330822086863
• License:
• Abstract: We propose a novel Bregman descent algorithm for minimizing a convex function that is expressed as the sum of a differentiable part (defined over an open set) and a possibly nonsmooth term. The approach, referred to as the Variable Bregman Majorization-Minimization (VBMM) algorithm, extends the Bregman Proximal Gradient method by allowing the Bregman function used in the divergence to adaptively vary at each iteration, provided it satisfies a majorizing condition on the objective function. This adaptive framework enables the algorithm to approximate the objective more precisely at each iteration, thereby allowing for accelerated convergence compared to the traditional Bregman Proximal Gradient descent. We establish the convergence of the VBMM algorithm to a minimizer under mild assumptions on the family of metrics used. Furthermore, we introduce a novel application of both the Bregman Proximal Gradient method and the VBMM algorithm to the estimation of the multidimensional parameters of a Dirichlet distribution through the maximization of its log-likelihood. Numerical experiments confirm that the VBMM algorithm outperforms existing approaches in terms of convergence speed.

Related papers

• Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
  This research presents a method to meet requirements through the minimization objective function of the RPM algorithm. A branch-and-bound (BnB) algorithm is devised, which solely branches over the parameters, thereby boosting convergence rate. Empirical evaluations demonstrate better robustness of the proposed methodology against non-rigid deformation, positional noise, and outliers, when compared with prevailing state-of-the-art transformations.
  arXiv  Detail & Related papers  (2024-05-14T13:28:57Z)
• Regularized Q-Learning with Linear Function Approximation [2.765106384328772]
  We consider a bi-level optimization formulation of regularized Q-learning with linear functional approximation. We show that, under certain assumptions, the proposed algorithm converges to a stationary point in the presence of Markovian noise.
  arXiv  Detail & Related papers  (2024-01-26T20:45: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)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness [0.0]
  We consider the average of a very large number of smooth possibly non-size functions, and we use two widely minibatch frameworks to tackle this problem. We define ease-controlled modifications of IG/RR schemes, which require a light additional computational effort. We prove our implementation with both a full batch gradient (i.e. L-BFGS) and an implementation of IG/RR methods, proving that algorithms require a similar computational effort.
  arXiv  Detail & Related papers  (2022-12-04T15:26:36Z)
• An Algebraically Converging Stochastic Gradient Descent Algorithm for Global Optimization [14.121491356732188]
  A key component in the algorithm is the randomness based on the value of the objective function. We prove the convergence of the algorithm with an algebra and tuning in the parameter space. We present several numerical examples to demonstrate the efficiency and robustness of the algorithm.
  arXiv  Detail & Related papers  (2022-04-12T16:27:49Z)
• Bregman Gradient Policy Optimization [97.73041344738117]
  We design a Bregman gradient policy optimization for reinforcement learning based on Bregman divergences and momentum techniques. VR-BGPO reaches the best complexity $tilde(epsilon-3)$ for finding an $epsilon$stationary point only requiring one trajectory at each iteration.
  arXiv  Detail & Related papers  (2021-06-23T01:08:54Z)
• AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods [7.486132958737807]
  We present an adaptive variance reduced method with an implicit approach for adaptivity. We provide convergence guarantees for finite-sum minimization problems and show a faster convergence than SARAH can be achieved if local geometry permits. This algorithm implicitly computes step-size and efficiently estimates local Lipschitz smoothness of functions.
  arXiv  Detail & Related papers  (2021-02-19T01:17:15Z)
• 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)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

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.