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.
New methods help escape strict saddle points in nonsmooth optimization.
problem Escaping strict saddle points in nonsmooth optimization.
method An inexact stochastically perturbed gradient method applied to the Moreau envelope.
result A variety of algorithms for nonsmooth optimization can efficiently escape strict saddle points of the Moreau envelope.
Defines a calculus for integrating Moreau envelopes in differentiable programming.
problem Lack of a mathematical framework for applying Moreau envelopes to deep networks and machine learning systems.
method Develops a compositional calculus adapted to Moreau envelopes and integrates it into differentiable programming.
result Integrates Moreau envelopes into differentiable programming, enabling new gradient back-propagation methods.
pFedMe uses Moreau envelopes to improve personalized FL performance.
problem Statistical diversity among clients limits FL performance.
method pFedMe employs Moreau envelopes as clients' regularized loss functions in a bi-level optimization problem.
result pFedMe achieves state-of-the-art convergence rates and superior empirical performance.
Regularizes f-divergences with MMD to analyze Wasserstein flows.
problem Limitations of f-divergences in measures' support. method Rewriting MMD regularization as Moreau envelope in RKHS, analyzing gradients.
result Analysis of Wasserstein flows of MMD-regularized f-divergences. We prove a new generalization bound that shows for any class of linear predictors in Gaussian space, the Rademacher complexity of the class and the training error under any continuous loss ℓ can control the test error under all Moreau envelopes of the loss ℓ. We use our finite-sample bound to directly recover…
New algorithm stabilizes bi-level hyperparameter optimization.
problem Stability issues in bi-level hyperparameter optimization.
method Uses Moreau-Yosida regularization to stabilize convergence.
result Significant improvement in loss values with fixed computation budget.
This work uses Lasry-Lions envelopes to solve nonconvex optimization problems.
problem Nonconvex and nonsmooth terms in optimization problems.
method Develops a homotopy approach using Lasry-Lions envelopes to approximate and solve the original problem.
result The method can solve composite minimization problems and is more effective than classical alternatives in certain domains.
MoreauGrad interprets neural nets robustly and sparsely.
problem Lack of robustness and sparsity in gradient-based interpretation methods.
method Moreau envelope for smooth and robust interpretation, combined with L1 regularization for sparsity.
result MoreauGrad provides a smooth, robust, and sparse explanation of neural nets.
Adaptive algorithm AMSGrad converges for weakly convex constrained optimization problems.
problem Solving constrained stochastic optimization problems with weakly convex objectives.
method Analysis of AMSGrad algorithm for a specific class of problems.
result AMSGrad achieves a convergence rate of ildeO(t−1/4) for the norm of the gradient of the Moreau envelope. New algorithm solves complex non-convex problems efficiently.
problem Non-smooth non-convex problems with weakly convex and strongly concave components.
method Stochastic Moreau envelope approximate gradient method (SMAG).
result First single-loop algorithm with state-of-the-art convergence rate.
The paper analyzes convergence rates for stochastic approximation and reinforcement learning.
problem Establishing almost sure convergence rates for stochastic approximation and reinforcement learning under Markovian noise.
method A novel Lyapunov drift construction that applies a Poisson-equation based correction for Markovian noise to the Moreau-envelope smoothing for contractive mappings.
result Almost sure convergence rates for specific learning rates are derived, with rates arbitrarily close to o(n1−2η) and o(n−1). The paper analyzes PPM for nonconvex-nonconcave problems, identifying three regions with varying convergence guarantees.
problem Challenges in nonconvex-nonconcave minimax optimization.
method Classic proximal point method with insights from the Moreau envelope.
result Identification of three regions with varying convergence guarantees for PPM.
New convergence rates found for PnP methods using MMSE denoisers.
problem Asymptotic convergence of PnP methods with MMSE denoisers.
method Explicitly represented MMSE denoiser as an upper Moreau envelope, derived sublinear convergence rates.
result First sublinear convergence guarantee for PnP proximal gradient descent with MMSE denoiser.
In this paper we develop proximal methods for statistical learning. Proximal point algorithms are useful in statistics and machine learning for obtaining optimization solutions for composite functions. Our approach exploits closed-form solutions of proximal operators and envelope representations based on the Moreau, Fo…
A distributed subgradient method tackles non-convex optimization problems in networks.
problem Solving non-convex optimization problems in distributed networks.
method Proposes a distributed stochastic subgradient method (stoDPSM) with theoretical guarantees.
result Global convergence of stoDPSM using Moreau envelope stationarity measure, and linear convergence under sharpness condition.
Unified proof for scalable personalized federated learning.
problem Personalized federated learning under asynchronous updates.
method Unified proof for asynchronous federated learning with bounded staleness applied to MAML and ME personalization frameworks.
result Unified proof for convergence to first-order stationary point for smooth and non-convex functions.
Stochastic Approximation (SA) is a popular approach for solving fixed-point equations where the information is corrupted by noise. In this paper, we consider an SA involving a contraction mapping with respect to an arbitrary norm, and show its finite-sample error bounds while using different stepsizes. The idea is to c…
We consider a class of nonconvex nonsmooth optimization problems whose objective is the sum of a smooth function and a finite number of nonnegative proper closed possibly nonsmooth functions (whose proximal mappings are easy to compute), some of which are further composed with linear maps. This kind of problems arises …
Optimizes partial AUC across various FPRs for machine learning models.
problem Lack of scalable algorithms for optimizing partial AUC in a range of FPRs.
method Formulated as a non-smooth DC program, developed an efficient approximated gradient descent method using Moreau envelope smoothing.
result Achieved a complexity of O(1/ε6) for finding nearly ε-critical solutions. Paper extends KPCA using dualization for faster, more robust algorithms.
problem Efficiently perform KPCA with robustness and sparsity.
method Dualization of convex functions for multiple objective functions, promoting sparsity and robustness.
result Significant speedup in KPCA training time and improved robustness and sparsity.
The paper tackles finding stationary points in stochastic convex optimization problems.
problem Finding stationary points for stochastic convex optimization problems.
method The approach relies on dimension theory to decompose the graph of the subdifferential of a convex function, showing how stochastic sampling preserves 'pieces' of these graphs, and allowing effective application of proximal-point-like methods.
result The paper provides convergence guarantees for finding stationary points in stochastic convex optimization problems.
DE-PSGLD samples from constrained distributions in a decentralized manner.
problem Sampling from log-concave distributions with constraints.
method Decentralized Proximal Stochastic Gradient Langevin Dynamics with proximal regularization.
result DE-PSGLD converges to a regularized Gibbs distribution and maintains posterior concentration.
New Langevin algorithm works well even for rough distributions.
problem Sampling from non-smooth distributions.
method Simple Langevin algorithm without smoothness assumptions.
result Algorithm performs well even with discontinuous gradients.
Proves convergence of PSGLA for sampling non-convex potentials.
problem Sampling from non-convex potentials with stability.
method Combines ULA and proximal optimization with stability analysis.
result First proof of convergence for PSGLA on non-convex potentials.
New Frank-Wolfe algorithm speeds up SVM-type multi-category learning.
problem Improving pattern recognition performance in multi-category SVM learning.
method Developed a new optimization algorithm based on Frank-Wolfe framework for MC-SVM variants.
result Closed-form solutions for direction finding and line search in the Frank-Wolfe framework for MC-SVM.
Unified analysis of stochastic iterative algorithms using Lyapunov functions.
problem Analyzing convergence of stochastic iterative algorithms for fixed-point equations.
method Lyapunov-based techniques for finite-time analysis of stochastic approximation algorithms.
result Unified mean-square convergence guarantees for various algorithms.
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…
We establish numerical methods for solving the martingale optimal transport problem (MOT) - a version of the classical optimal transport with an additional martingale constraint on transport's dynamics. We prove that the MOT value can be approximated using linear programming (LP) problems which result from a discretisa…
Improved convergence for nonconvex optimization with dependent data.
problem Constrained smooth nonconvex optimization with dependent data.
method Stochastic projected gradient methods under a general dependent data sampling scheme.
result Achieved worst-case rate of convergence ildeO(t−1/4) and complexity ildeO(ε−4). 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…
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.
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.
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…
We introduce a new approximation of f-divergences for machine learning.
problem Variational representations of f-divergences for machine learning. method Definition and analysis of Moreau-Yosida approximation of f-divergences with the Wasserstein-1 metric. result Generalization and relaxation of hard Lipschitz constraints in f-divergences. Correct method found for drawing precise envelope of straight lines.
problem Widespread method fails to represent the precise shape of envelope.
method Recently discovered correct method for straight line families in the plane.
result Correct method precisely represents the envelope of straight lines.
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…
New bounds for SA with arbitrary norm contractions and Markovian noise.
problem Finite-time analysis of two-time-scale stochastic approximation with arbitrary norm contractions and Markovian noise.
method Use of generalized Moreau envelope for arbitrary norm contractions and solutions of Poisson equation for Markovian noise.
result Mean square error decays at rates of O(1/n2/3) and O(1/n) under different conditions. Study three discrete envelope types of polygon bisection lines.
problem Understanding different envelope types of polygon bisection lines.
method Examined three distinct notions of discrete envelopes.
result Connected three different notions of discrete envelopes.
Paper solves four problems of pseudo-circle envelopes in Minkowski plane.
problem Four problems of pseudo-circle envelopes in Minkowski plane.
method Solutions to four basic problems.
result Solved four problems of pseudo-circle envelopes in Minkowski plane.
Describes envelopes of Thurston metric on Teichmüller space.
problem Characterizing the shape and properties of envelopes in Teichmüller space.
method Using harmonic stretch lines and topological invariants, the shape and properties of envelopes are described.
result Envelopes are contractible and vary continuously with endpoints.