Block Alternating Bregman Majorization Minimization with Extrapolation
- URL: http://arxiv.org/abs/2107.04395v1
- Date: Fri, 9 Jul 2021 12:47:00 GMT
- Title: Block Alternating Bregman Majorization Minimization with Extrapolation
- Authors: Le Thi Khanh Hien, Duy Nhat Phan, Nicolas Gillis, Masoud Ahookhosh,
Panagiotis Patrinos
- Abstract summary: We consider a class of nonsmooth non optimization problems whose objective is the sum of a block relative smooth function and a proper separable function.
We propose a block alternating Bregman Majorization-Minimization framework with Extrapolation (BMME)
We prove the effectiveness of BMME on the penalized nonnegative matrix under stronger conditions.
- Score: 16.04690575393738
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider a class of nonsmooth nonconvex optimization
problems whose objective is the sum of a block relative smooth function and a
proper and lower semicontinuous block separable function. Although the analysis
of block proximal gradient (BPG) methods for the class of block $L$-smooth
functions have been successfully extended to Bregman BPG methods that deal with
the class of block relative smooth functions, accelerated Bregman BPG methods
are scarce and challenging to design. Taking our inspiration from Nesterov-type
acceleration and the majorization-minimization scheme, we propose a block
alternating Bregman Majorization-Minimization framework with Extrapolation
(BMME). We prove subsequential convergence of BMME to a first-order stationary
point under mild assumptions, and study its global convergence under stronger
conditions. We illustrate the effectiveness of BMME on the penalized orthogonal
nonnegative matrix factorization problem.
Related papers
- Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimization [2.7998963147546148]
We develop a framework for developing Lagrangian-based methods.
We show that our framework can be extended to solve constrained problems with expectation constraints.
arXiv Detail & Related papers (2024-04-15T03:50:47Z) - Block Majorization Minimization with Extrapolation and Application to
$\beta$-NMF [17.97403029273243]
We propose a Block Majorization Minimization method with Extrapolation (BMMe) for solving a class of multi- optimization problems.
We show that block majorization parameters of BMMe can be reformulated as a block mirror method with the Bregman divergence adaptively updated.
We empirically illustrate the significant acceleration BM for $beta$NMF through extensive experiments.
arXiv Detail & Related papers (2024-01-12T15:52:02Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
Many real-world problems have complicated non functional constraints and use a large number of data points.
Our proposed method outperforms an existing method with the previously best-known result.
arXiv Detail & Related papers (2022-12-19T14:48:54Z) - Meta-Learning Adversarial Bandits [49.094361442409785]
We study online learning with bandit feedback across multiple tasks, with the goal of improving average performance across tasks if they are similar according to some natural task-similarity measure.
As the first to target the adversarial setting, we design a meta-algorithm that setting-specific guarantees for two important cases: multi-armed bandits (MAB) and bandit optimization (BLO)
Our guarantees rely on proving that unregularized follow-the-leader combined with multiplicative weights is enough to online learn a non-smooth and non-B sequence.
arXiv Detail & Related papers (2022-05-27T17:40:32Z) - Multiblock ADMM for nonsmooth nonconvex optimization with nonlinear
coupling constraints [3.2815423235774634]
We propose a method of multipliers for solving a class of multiblock nonsmooth alternating optimization problem with nonlinear constraints.
We employ a major sequenceization procedure in update of each block of the primal variables.
arXiv Detail & Related papers (2022-01-19T15:31:30Z) - Value-Function-based Sequential Minimization for Bi-level Optimization [52.39882976848064]
gradient-based Bi-Level Optimization (BLO) methods have been widely applied to handle modern learning tasks.
There are almost no gradient-based methods able to solve BLO in challenging scenarios, such as BLO with functional constraints and pessimistic BLO.
We provide Bi-level Value-Function-based Sequential Minimization (BVFSM) to address the above issues.
arXiv Detail & Related papers (2021-10-11T03:13:39Z) - 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) - Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
The softmax policy gradient (PG) method is arguably one of the de facto implementations of policy optimization in modern reinforcement learning.
We demonstrate that softmax PG methods can take exponential time -- in terms of $mathcalS|$ and $frac11-gamma$ -- to converge.
arXiv Detail & Related papers (2021-02-22T18:56:26Z) - Global Convergence of Model Function Based Bregman Proximal Minimization
Algorithms [17.740376367999705]
Lipschitz mapping of a continuously differentiable function plays a crucial role in various optimization algorithms.
We propose a globally convergent algorithm called Model $$L$mad property.
arXiv Detail & Related papers (2020-12-24T08:09:22Z) - An Inertial Block Majorization Minimization Framework for Nonsmooth
Nonconvex Optimization [17.49766938060264]
We introduce TITAN, a novel inerTIal block majorizaTion minimizAtioN for non-smooth non-coordinate problems.
We illustrate the effectiveness of TITAN on two important machine learning problems.
arXiv Detail & Related papers (2020-10-23T02:25:20Z) - 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)
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.