We propose a version of least-mean-square (LMS) algorithm for sparse system identification. Our algorithm called online linearized Bregman iteration (OLBI) is derived from minimizing the cumulative prediction error squared along with an l1-l2 norm regularizer. By systematically treating the non-differentiable regulariz…
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.
169,051 papers · 148 categories
Trend · papers per month
48 results for “Linearized Bregman Iterations”
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.
Analysis of Generalized Bregman Surrogate Algorithms for Nonsmooth Nonconvex Statistical Learningmath.OC
Paper develops algorithms for nonsmooth, nonconvex statistical learning problems.
problem Nonsmooth and nonconvex objectives in statistical learning.
method Bregman-surrogate algorithm framework, including local linear approximation, mirror descent, iterative thresholding, DC programming.
result Global convergence rates for nonconvex and nonsmooth objectives in high dimensions.
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 …
New method reduces PDE model parameters by 30% with sparsity.
problem Redundant parameters in neural network projections.
method Bregman iterations for sparsity, POD compression, bias propagation.
result 30% fewer parameters with similar accuracy.
Proposes batch version of Greenkhorn for multimarginal OT, proving convergence.
problem Optimal transport problems with multiple marginals.
method Batch Greenkhorn algorithm, iterative Bregman projections, greedy control.
result Global linear rate of convergence and explicit iteration complexity bounds.
Unified dynamic approach for sparse model selection improves efficiency and accuracy.
problem Sparse model selection challenges in various fields.
method Iterative regularization path using Mirror Descent or Linearized Bregman Iterations.
result Path consistency theory with no false positives and minimax optimal error rate.
Paper introduces -LBI for efficient deep learning with structural sparsity.
problem Efficiently train deep networks with structural sparsity.
method Stochastic Split Linearized Bregman Iteration (-LBI) algorithm.
result Enables enlarging or simplifying networks while maintaining high accuracy.
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.
Proposes a new classification model using extended exponential functions.
problem Improving classification accuracy in binary linear classification problems.
method Developed a Bregman-Tweedie classification model based on extended exponential functions.
result The H-Bregman and L-Bregman sub-models outperform traditional methods in ranking and classification accuracy.
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…
New algorithm solves saddle point problems in Banach spaces.
problem Solving saddle point problems in real reflexive Banach spaces.
method Stochastic Bregman Primal-Dual Splitting Algorithm with relative smoothness and strong convexity assumptions.
result Almost sure convergence to saddle points under various conditions.
In this paper, we recover sparse signals from their noisy linear measurements by solving nonlinear differential inclusions, which is based on the notion of inverse scale space (ISS) developed in applied mathematics. Our goal here is to bring this idea to address a challenging problem in statistics, \emph{i.e.} finding …
Proposes a new approach to generate sparse models from deep networks.
problem Training small networks can get stuck in local optima; over-parameterized models are preferred.
method Differential inclusion paths to generate a family of models from simple to complex.
result Algorithm converges to a critical point of empirical risks from any initializations.
The paper focuses on the sparse approximation of signals using overcomplete representations, such that it preserves the (prior) structure of multi-dimensional signals. The underlying optimization problem is tackled using a multi-dimensional split Bregman optimization approach. An extensive empirical evaluation shows ho…
The paper develops a method to approximate arbitrary Bregman divergences from supervision.
problem Approximating an arbitrary Bregman divergence from supervision.
method Develops a formulation and algorithm for learning arbitrary Bregman divergences by approximating their convex generating function via a piecewise linear function.
result The method achieves a generalization error of for metric learning, matching known bounds.
DFSOS improves sparse discriminant analysis for high-dimensional data.
problem Sparse discriminant analysis in high-dimensional settings with feature selection.
method Deflation-Free Sparse Optimal Scoring (DFSOS) using Bregman iteration and orthogonality-constrained optimization.
result DFSOS achieves comparable or better classification accuracy than deflation-based methods.
Paper relaxes optimal transport using convex functions for data science.
problem Optimal transport problem on finite spaces.
method Relaxation via strictly convex functions (Kullback-Leibler divergence, Bregman divergences). Gradient descent iterative process.
result Mathematical foundations and iterative process for the relaxed optimal transport problem.
Split Bregman Method for Sparse Inverse Covariance Estimation with Matrix Iteration Accelerationstat.ML
We consider the problem of estimating the inverse covariance matrix by maximizing the likelihood function with a penalty added to encourage the sparsity of the resulting matrix. We propose a new approach based on the split Bregman method to solve the regularized maximum likelihood estimation problem. We show that our m…
Paper develops robust Bayesian models for linear regression under adversarial perturbations.
problem Ensuring reliable machine learning models under data perturbations.
method Formulates adversarial Bregman divergence loss, computes adversarial perturbation, introduces adversarially robust posteriors, derives generalization certificates.
result Derives first rigorous generalization certificates for adversarially robust Bayesian linear regression.
A new algorithm reconstructs population dynamics from coarse samples.
problem Reconstructing population dynamics from unlabeled samples at coarse time intervals.
method Deep Momentum Multi-Marginal Schrödinger Bridge (DMSB) framework.
result Significantly outperforms baselines in synthetic and real-world datasets.
Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysismath.ST
New inequalities help optimize first-order algorithms for statistical risk analysis.
problem Optimizing first-order iterative algorithms for statistical risk analysis.
method Introducing basic inequalities that connect implicit and explicit regularization.
result The basic inequalities translate the number of iterations into an effective regularization coefficient.
Boosting as gradient descent algorithms is one popular method in machine learning. In this paper a novel Boosting-type algorithm is proposed based on restricted gradient descent with structural sparsity control whose underlying dynamics are governed by differential inclusions. In particular, we present an iterative reg…
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.
Study calibrates high-dimensional binary classifiers using angle between estimator and true weights.
problem Calibrating high-dimensional binary classifiers with provable properties.
method Interpolates with a chance classifier to construct well-calibrated predictor based on angle between estimator and true weights.
result Angular calibration approach is provably well-calibrated in high dimensions, minimizing Bregman divergence.
New method explores structural sparsity in deep networks efficiently.
problem Learning structural sparsity in over-parameterized deep networks.
method Differential inclusions of inverse scale spaces, coupled with Deep structure splitting Linearized Bregman Iteration (DessiLBI).
result Achieves comparable and better performance in sparse structure exploration than competitive optimizers.
Paper tackles robust optimal transport with improved computational complexity and barycenter approximation.
problem Computing robust optimal transport and its barycenter efficiently.
method Sinkhorn-based algorithms for robust optimal transport and iterative Bregman projections for barycenter approximation.
result Improved computational complexity for robust optimal transport and barycenter approximation.
New methods solve non-Lipschitz smooth problems with guaranteed convergence.
problem Non-Lipschitz smooth problems in machine learning and signal processing.
method Bregman-divergence based algorithms for relatively smooth problems.
result Guaranteed convergence to second-order stationary points for any relatively smooth problem.
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.
A generalized optimistic method for saddle point problems with improved complexity.
problem Solving convex-concave saddle point problems efficiently.
method Proposes a generalized optimistic method that includes the optimistic gradient method as a special case, handling constrained saddle point problems with composite objective functions and arbitrary norms.
result Best-known global iteration complexity bounds for first-, second-, and higher-order methods.
Gradient-based clustering method for various cost functions.
problem Distance-based clustering for various cost functions.
method Iterative alternating update procedure for cluster assignments and centers.
result Converges to fixed points under mild assumptions.
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 paper explores clustering methods using Bregman divergences.
problem Developing efficient clustering algorithms for complex data.
method Investigates fixed rate quantization and Voronoi diagrams in Riemannian metric spaces induced by separable Bregman divergences.
result Experimental results show improved performance of clustering algorithms using these metrics.
EGMU optimizes portfolios using KL divergence, ensuring positive solutions.
problem Constructing multi-factor target-exposure portfolios efficiently and accurately.
method Convex optimization framework minimizing KL divergence, with explicit solvers.
result Established feasibility and uniqueness of strictly positive solutions under convex-hull conditions.
New Bregman chord divergences simplify distance selection in machine learning.
problem Selecting appropriate distances for machine learning tasks.
method Extend Bregman divergences with two scalar parameters.
result Simplified distance selection with asymptotic generalization of Bregman divergences.
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.
Paper establishes universal lower bounds and optimal rates for clustering sub-exponential mixture models.
problem Achieving optimal error rates in clustering sub-exponential mixture models.
method Establishes universal lower bounds and demonstrates iterative algorithms' optimality in sub-exponential mixture models.
result Iterative algorithms achieve the universal lower bound in sub-exponential mixture models.
Unified framework for estimating density ratios in causal inference.
problem Estimating density ratios for causal inference is challenging due to instability and curse of dimensionality.
method Bregman-Riesz regression unifies three methods: Bregman divergences, probabilistic classification, and Riesz loss.
result Unified framework improves density ratio estimation in causal inference.
Time dependent loss reweighting for flow matching and diffusion models is theoretically justifiedstat.ML
The paper justifies time-dependent loss reweighting schemes for flow matching and diffusion models.
problem Theoretical justification for time-dependent loss reweighting schemes in flow matching and diffusion models.
method Clarifies that the loss can depend on both time and state, and shows theoretical justification for time-dependent loss weighting schemes.
result Time-dependent loss weighting schemes are theoretically justified for Generator Matching and Edit Flows.
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…
This paper introduces a novel approach for learning to rank (LETOR) based on the notion of monotone retargeting. It involves minimizing a divergence between all monotonic increasing transformations of the training scores and a parameterized prediction function. The minimization is both over the transformations as well …
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 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…
Paper studies fully implicit online learning algorithms for improved numerical stability.
problem Improving numerical stability and solution structure in online learning.
method Develops fully implicit online learning (FIOL) algorithms without linearizing loss or regularizer.
result FIOL achieves optimal regret bounds for convex and strongly convex settings.
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…
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…