The mirror descent algorithm (MDA) generalizes gradient descent by using a Bregman divergence to replace squared Euclidean distance. In this paper, we similarly generalize the alternating direction method of multipliers (ADMM) to Bregman ADMM (BADMM), which allows the choice of different Bregman divergences to exploit …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Bregman ADMM”
New algorithm solves maximal monotone inclusion problems.
problem Solving maximal monotone inclusion problems.
method Bregman Douglas-Rachford splitting method and variants.
result Convergence of algorithms under certain assumptions.
The Alternating Direction Method of Multipliers (ADMM) has been studied for years. The traditional ADMM algorithm needs to compute, at each iteration, an (empirical) expected loss function on all training examples, resulting in a computational complexity proportional to the number of training examples. To reduce the ti…
Bayesian models provide a framework for probabilistic modelling of complex datasets. However, many of such models are computationally demanding especially in the presence of large datasets. On the other hand, in sensor network applications, statistical (Bayesian) parameter estimation usually needs distributed algorithm…
The split Bregman (SB) method [T. Goldstein and S. Osher, SIAM J. Imaging Sci., 2 (2009), pp. 323-43] is a fast splitting-based algorithm that solves image reconstruction problems with general l1, e.g., total-variation (TV) and compressed sensing (CS), regularizations by introducing a single variable split to decouple …
Faster algorithms solve convex function learning problems.
problem Approximating arbitrary convex functions in various learning tasks.
method 2-block ADMM method with closed-form block computations.
result Converges with for convex Lipschitz regression.
New geometry for optimal transport cost based on Bregman divergences.
problem Optimal transport cost calculation with Bregman divergences.
method Established properties, defined interpolations, constructed dualistic geometry.
result Derived generalized Pythagorean inequality and Bregman-Wasserstein barycenters.
This work proposes the Bregman-Tweedie classification model and analyzes the domain structure of the extended exponential function, an extension of the classic generalized exponential function with additional scaling parameter, and related high-level mathematical structures, such as the Bregman-Tweedie loss function an…
The Bregman divergence (Bregman distance, Bregman measure of distance) is a certain useful substitute for a distance, obtained from a well-chosen function (the "Bregman function"). Bregman functions and divergences have been extensively investigated during the last decades and have found applications in optimization, o…
Bregman divergences play a central role in the design and analysis of a range of machine learning algorithms. This paper explores the use of Bregman divergences to establish reductions between such algorithms and their analyses. We present a new scaled isodistortion theorem involving Bregman divergences (scaled Bregman…
The alternating direction method of multipliers (ADMM) is a powerful optimization solver in machine learning. Recently, stochastic ADMM has been integrated with variance reduction methods for stochastic gradient, leading to SAG-ADMM and SDCA-ADMM that have fast convergence rates and low iteration complexities. However,…
New Langevin Monte Carlo algorithms for sampling from nonsmooth distributions.
problem Sampling from distributions with nonsmooth convex composite potentials.
method Leveraging Bregman--Moreau envelopes and proximal operators in mirror descent.
result Efficiency in sampling from nonsmooth distributions, extending existing methods.
Recently, many variance reduced stochastic alternating direction method of multipliers (ADMM) methods (e.g.\ SAG-ADMM, SDCA-ADMM and SVRG-ADMM) have made exciting progress such as linear convergence rates for strongly convex problems. However, the best known convergence rate for general convex problems is O(1/T) as opp…
In this work, we extend some quantities introduced in "Optimization of conditional value-at-risk" of R.T Rockafellar and S. Uryasev to the case where the proximity between real numbers is measured by using a Bregman divergence. This leads to the definition of the Bregman superquantile. Axioms of a coherent measure of r…
Unified view connects CoCoA and ADMM for distributed ERM.
problem Connection between CoCoA and ADMM for distributed ERM.
method Unified primal-dual perspective reformulation.
result Unified ADMM variants perform at least as good as CoCoA in ridge-regularized ERM.
A faster ADMM method for nonconvex optimization with improved complexity.
problem Nonconvex optimization problems in machine learning.
method SPIDER-ADMM, a stochastic ADMM method using a new differential estimator.
result Achieves optimal IFO complexity of for finding an -approximate stationary point.
We consider the problem of maximum a posteriori (MAP) inference in discrete graphical models. We present a parallel MAP inference algorithm called Bethe-ADMM based on two ideas: tree-decomposition of the graph and the alternating direction method of multipliers (ADMM). However, unlike the standard ADMM, we use an inexa…
Distances are fundamental primitives whose choice significantly impacts the performances of algorithms in machine learning and signal processing. However selecting the most appropriate distance for a given task is an endeavor. Instead of testing one by one the entries of an ever-expanding dictionary of {\em ad hoc} dis…
Paper introduces a new method for learning Bregman divergence from data.
problem Suboptimal performance of classic distance metrics in deep metric learning.
method Learning empirical Bregman divergence from data using deep learning.
result Empirical Bregman divergence method outperforms other methods on public datasets.
This manuscript develops the theory of agglomerative clustering with Bregman divergences. Geometric smoothing techniques are developed to deal with degenerate clusters. To allow for cluster models based on exponential families with overcomplete representations, Bregman divergences are developed for nondifferentiable co…
New findings show Bregman proximal algorithms can get stuck near non-stationary points.
problem Bregman proximal algorithms can get stuck near non-stationary points, misleadingly suggesting convergence.
method Analysis of Bregman proximal algorithms and their behavior near non-stationary points.
result Bregman proximal algorithms can get stuck near spurious stationary points, even in convex problems.
Alternating Direction Method of Multipliers (ADMM) has become a widely used optimization method for convex problems, particularly in the context of data mining in which large optimization problems are often encountered. ADMM has several desirable properties, including the ability to decompose large problems into smalle…
In this paper, we introduce new classes of divergences by extending the definitions of the Bregman divergence and the skew Jensen divergence. These new divergence classes (g-Bregman divergence and skew g-Jensen divergence) satisfy some properties similar to the Bregman or skew Jensen divergence. We show these g-diverge…
In the paper, we study the stochastic alternating direction method of multipliers (ADMM) for the nonconvex optimizations, and propose three classes of the nonconvex stochastic ADMM with variance reduction, based on different reduced variance stochastic gradients. Specifically, the first class called the nonconvex stoch…
Novel PP-ADMM and IPP-ADMM algorithms improve differential privacy in distributed machine learning.
problem Privacy concerns in ADMM-based distributed machine learning.
method Proposes PP-ADMM and IPP-ADMM algorithms to provide differential privacy while improving model accuracy and convergence.
result The proposed algorithms achieve better model accuracy and convergence under the same privacy guarantee.
Unified analysis of stochastic ADMM variants via SME.
problem Analyzing and optimizing stochastic ADMM variants for machine learning.
method Unified mathematical framework of SME for continuous-time analysis.
result Dynamics of stochastic ADMM approximated by SDEs with small noise.
New method improves structure learning on sparse graphs.
problem Structure learning on sparse directed acyclic graphs (DAGs).
method Bregman proximal gradient method to address non-convex, high-curvature problem.
result Significantly improved convergence and efficiency.
Separable Bregman divergences induce Riemannian metric spaces that are isometric to the Euclidean space after monotone embeddings. We investigate fixed rate quantization and its codebook Voronoi diagrams, and report on experimental performances of partition-based, hierarchical, and soft clustering algorithms with respe…
Bayesian approach generalizes ADMM for federated learning.
problem Improving federated learning efficiency and accuracy.
method Integrates Bayesian duality with ADMM for optimization.
result New extensions of ADMM for various distributions.
Combines ADMM and VB for federated learning.
problem Improving federated learning performance.
method Derives ADMM variants from VB with flexible covariances and functional regularisation.
result Improves federated learning performance through new ADMM variants.
ADMM solves constrained CASH problems by breaking them into smaller, manageable pieces.
problem Handling black-box constraints in CASH problems.
method Leverages ADMM optimization framework to decompose CASH problems.
result ADMM facilitates incorporation of black-box constraints.
Alternating Direction Method of Multipliers (ADMM) is a widely used tool for machine learning in distributed settings, where a machine learning model is trained over distributed data sources through an interactive process of local computation and message passing. Such an iterative process could cause privacy concerns o…
We present ADMM-Softmax, an alternating direction method of multipliers (ADMM) for solving multinomial logistic regression (MLR) problems. Our method is geared toward supervised classification tasks with many examples and features. It decouples the nonlinear optimization problem in MLR into three steps that can be solv…
The alternating direction method of multipliers (ADMM) has been successfully applied to solve structured convex optimization problems due to its superior practical performance. The convergence properties of the 2-block ADMM have been studied extensively in the literature. Specifically, it has been proven that the 2-blo…
Due to massive amounts of data distributed across multiple locations, distributed machine learning has attracted a lot of research interests. Alternating Direction Method of Multipliers (ADMM) is a powerful method of designing distributed machine learning algorithm, whereby each agent computes over local datasets and e…
Proposes BMME for optimizing nonsmooth nonconvex problems with block structure.
problem Optimizing nonsmooth nonconvex problems with block structure.
method Block Alternating Bregman Majorization Minimization with Extrapolation (BMME).
result Subsequential convergence to a first-order stationary point under mild assumptions, global convergence under stronger conditions.
Generalizes bias-variance decomposition for Bregman divergences.
problem No specific problem stated; generalization of bias-variance for Bregman divergences.
method Provided a generalization of the bias-variance decomposition for Bregman divergences.
result A clear, standalone derivation of the bias-variance decomposition for Bregman divergences.
We consider the stochastic composition optimization problem proposed in \cite{wang2017stochastic}, which has applications ranging from estimation to statistical and machine learning. We propose the first ADMM-based algorithm named com-SVR-ADMM, and show that com-SVR-ADMM converges linearly for strongly convex and Lipsc…
Alternating direction method of multipliers (ADMM) is a popular optimization tool for the composite and constrained problems in machine learning. However, in many machine learning problems such as black-box attacks and bandit feedback, ADMM could fail because the explicit gradients of these problems are difficult or in…
Bregman perspective on CART provides a unified framework for impurity measures.
problem Unifying impurity measures in CART
method Bregman divergence approach
result Unified framework for impurity measures
Divergence functions play a key role as to measure the discrepancy between two points in the field of machine learning, statistics and signal processing. Well-known divergences are the Bregman divergences, the Jensen divergences and the f-divergences. In this paper, we show that the symmetric Bregman divergence can be …
Optimal payoff choice constrained by Bregman-Wasserstein divergence.
problem Maximizing utility under a deviation constraint from a benchmark.
method Solving the problem using Bregman-Wasserstein divergence with a convex function φ.
result Provided the optimal payoff choice in this setting.
New analysis of annealing paths in sampling and estimation.
problem Sampling from complex distributions and estimating normalization constants.
method Extending known results on Bregman divergence to quasi-arithmetic means under monotonic embedding.
result Analogous result for quasi-arithmetic means, highlighting the interplay between means, parametric families, and divergence functionals.
Develops clustering methods based on likelihood and convergence proved.
problem Hard clustering based on likelihood.
method k-MLE, k-Bregman, k-VARs approaches.
result Convergence proved for clustering methods.
Unified deep metric learning approach using neural networks.
problem Learning embeddings of data and extending Euclidean distances.
method Deep Bregman divergences based on neural networks.
result Superior performance on benchmark datasets compared to existing methods.
Bregman divergences generalize measures such as the squared Euclidean distance and the KL divergence, and arise throughout many areas of machine learning. In this paper, we focus on the problem of approximating an arbitrary Bregman divergence from supervision, and we provide a well-principled approach to analyzing such…
The paper analyzes the bias-variance tradeoff for Bregman divergences.
problem Understanding the bias-variance tradeoff for Bregman divergences.
method Analyzes the bias-variance tradeoff through operations in dual space.
result Derives several results including a generalized law of total variance and ensembling operations.
Zeroth-order (a.k.a, derivative-free) methods are a class of effective optimization methods for solving complex machine learning problems, where gradients of the objective functions are not available or computationally prohibitive. Recently, although many zeroth-order methods have been developed, these approaches still…