New method speeds up optimization over probability measures.
problem High computational overhead in optimizing probability measures.
method Randomized coordinate descent on Wasserstein space.
result Significant speedups over full-gradient methods.
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 “coordinate mirror descent”
We establish that first-order methods avoid saddle points for almost all initializations. Our results apply to a wide variety of first-order methods, including gradient descent, block coordinate descent, mirror descent and variants thereof. The connecting thread is that such algorithms can be studied from a dynamical s…
Derives Mirror Descent from gradient flow on a Riemannian manifold.
problem No specific problem stated; focuses on derivation.
method Derives Mirror Descent from gradient flow on a Riemannian manifold with a natural discretization.
result Generalizes Mirror Descent to non-Hessian metrics.
Reparameterizes mirror descent as gradient descent for efficient sparse learning.
problem Efficiently training small sparse networks with mirror descent.
method Develops a framework to convert mirror descent updates into gradient descent updates on different parameters.
result Mirror descent can be reparameterized as gradient descent on modified parameters, facilitating standard backpropagation.
New analysis shows GMD can converge linearly under PL-like conditions.
problem Establishing linear convergence for generalized mirror descent.
method PL-based analysis for time-dependent mirrors, Taylor-series approach for stochastic GMD.
result Linear convergence of stochastic GMD under PL-like conditions.
This monograph presents the main complexity theorems in convex optimization and their corresponding algorithms. Starting from the fundamental theory of black-box optimization, the material progresses towards recent advances in structural optimization and stochastic optimization. Our presentation of black-box optimizati…
New algorithm reduces optimization complexity in adaptive mirror descent.
problem Optimizing complex, non-smooth, non-convex functions efficiently.
method SVRAMD: Variance Reduced Adaptive Mirror Descent.
result Variance reduction accelerates convergence in adaptive mirror descent.
Mirror descent algorithm recovers low-rank matrices in matrix sensing.
problem Matrix sensing with low-rank matrices under certain conditions.
method Discrete-time mirror descent applied to empirical risk with Bregman divergence analysis.
result Mirror descent converges to a matrix minimizing a specific nuclear norm-related quantity.
Develops parameter-free online mirror descent for optimal dynamic regret.
problem Optimal online linear optimization in unbounded domains.
method Modified online mirror descent framework for parameter-free algorithms.
result First unconstrained online linear optimization achieving optimal dynamic regret.
Continuous-time mirror descent solves sparse phase retrieval efficiently.
problem Recovering sparse signals from magnitude-only measurements.
method Continuous-time mirror descent applied to unconstrained empirical risk minimization problem.
result Mirror descent recovers -sparse vectors with minimum non-zero entry order of from Gaussian measurements.
Mirror descent linked to information ratio via Bayesian regret bounds.
problem Understanding stability in mirror descent and its relation to information ratio.
method Developed a connection between mirror descent and information ratio using Bayesian regret bounds.
result Mirror descent with suitable estimators and distributions achieves bounds similar to information-directed sampling.
The paper connects tempering and entropic mirror descent for sampling.
problem Sampling from a target distribution with known unnormalized density.
method Establishes the connection between tempering SMC and entropic mirror descent, deriving convergence rates and geometric insights.
result Tempering SMC iterates correspond to entropic mirror descent on the reverse KL divergence, providing new optimization perspectives.
Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descenteess.SP
Paper studies early-stopped mirror descent for noisy sparse phase retrieval.
problem Recovering a sparse signal from noisy quadratic measurements.
method Early-stopped mirror descent with hyperbolic entropy mirror map.
result Achieves nearly minimax-optimal rate of convergence for -sparse signals.
Continuous-time distributed mirror descent with integral feedback converges to global optimum.
problem Distributed optimization of a global strongly convex function with local convex components.
method Continuous-time distributed mirror descent with integral feedback.
result Asymptotic convergence to global optimum with constant step-size.
This paper explores a new framework for reinforcement learning based on online convex optimization, in particular mirror descent and related algorithms. Mirror descent can be viewed as an enhanced gradient method, particularly suited to minimization of convex functions in highdimensional spaces. Unlike traditional grad…
This paper extends Mirror Descent to Riemannian manifolds for optimization.
problem Optimization on Riemannian manifolds.
method Developed a Riemannian Mirror Descent (RMD) framework and a stochastic variant.
result Established non-asymptotic convergence guarantees for RMD and stochastic RMD.
Paper uses Mirror Descent for efficient risk budgeting portfolios.
problem Computing optimal risk budgeting weights for various risk measures.
method Employed Mirror Descent algorithms in deterministic and stochastic settings.
result Established convergence and quantitative rate for averaged Mirror Descent algorithm.
Information geometry applies concepts in differential geometry to probability and statistics and is especially useful for parameter estimation in exponential families where parameters are known to lie on a Riemannian manifold. Connections between the geometric properties of the induced manifold and statistical properti…
FedDuA adapts global learning rate for federated learning.
problem Slow convergence in federated learning due to dataset and parameter space heterogeneity.
method FedDuA uses mirror descent to adaptively select global learning rate based on inter-client and coordinate-wise heterogeneity.
result FedDuA achieves minimax optimal convergence for convex objectives and outperforms baselines in various settings.
Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EMmath.OC
The paper analyzes mirror descent in measure spaces and its applications.
problem Optimizing convex functionals over measure spaces.
method Derives convergence of mirror descent for relatively smooth and convex pairs of functionals.
result Shows Sinkhorn's primal iterations and EM as mirror descent.
The paper improves convergence for linear systems using entropic mirror descent with Polyak stepsizes.
problem Convergence analysis for linear systems with unbounded domain.
method Entropic mirror descent with Polyak stepsizes, sublinear and linear convergence results.
result Generalized convergence result for arbitrary convex functions.
Stochastic mirror descent improves performance on ensemble models.
problem Improving performance of ensemble models using stochastic mirror descent.
method Utilizes mirror potential to influence training algorithm's implicit bias, mapping evolution to continuous time process.
result Converges to a nonlinear PDE in asymptotic regime of large networks, with mirror potential affecting gradient flow.
Paper accelerates Bayesian few-shot classification using mirror descent.
problem Non-conjugate inference in Bayesian few-shot classification.
method Integrates mirror descent-based variational inference into Gaussian process-based few-shot classification.
result Accelerated convergence and improved uncertainty quantification.
New algorithm for low-rank optimal transport with improved interpretability and efficiency.
problem Quadratic scaling of optimal transport coupling matrix for massive datasets.
method Factor Relaxation with Latent Coupling (FRLC) algorithm.
result Superior performance on diverse applications including graph clustering and spatial transcriptomics.
New mirror maps improve PMD performance in reinforcement learning.
problem Limited exploration of PMD's full potential due to focus on negative entropy.
method Evolutionary strategies to identify and learn more efficient mirror maps.
result Learned mirror maps outperform negative entropy in various environments.
We provide theoretical complexity analysis for new algorithms to compute the optimal transport (OT) distance between two discrete probability distributions, and demonstrate their favorable practical performance over state-of-art primal-dual algorithms and their capability in solving other problems in large-scale, such …
Matrix SMD converges to unique solution minimizing Bregman divergence.
problem High-dimensional multi-output classification and matrix completion problems.
method Stochastic Mirror Descent with matrix parameters and matrix mirror functions.
result Matrix SMD converges exponentially to the unique solution minimizing Bregman divergence.
Recently there has been a surge of interest in understanding implicit regularization properties of iterative gradient-based optimization algorithms. In this paper, we study the statistical guarantees on the excess risk achieved by early-stopped unconstrained mirror descent algorithms applied to the unregularized empiri…
Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancestat.ML
Study shows Stochastic Mirror Descent optimizes convex problems with infinite noise variance.
problem Optimizing convex problems with infinite noise variance.
method Stochastic Mirror Descent algorithm with uniformly convex mirror maps.
result Demonstrates convergence rate quantified in terms of iterations, dimensionality, and geometric parameters.
We consider the problem of multi-class classification and a stochastic opti- mization approach to it. We derive risk bounds for stochastic mirror descent algorithm and provide examples of set geometries that make the use of the algorithm efficient in terms of error in k.
Paper provides tail bounds for stochastic mirror descent in heavy-tailed noise.
problem Optimizing convex and Lipschitz functions with heavy-tailed noise.
method Develops tail bounds for optimization error of Stochastic Mirror Descent.
result Tail bounds extend to heavier-tailed noise regimes without diameter constraints.
Unified framework for solving MDPs with stochastic mirror descent.
problem Approximately solving infinite-horizon Markov decision processes (MDPs).
method Primal-dual stochastic mirror descent for MDPs with a unified framework.
result Computes ε-optimal policies with expected samples for both average-reward and discounted MDPs.
First-order methods play a central role in large-scale machine learning. Even though many variations exist, each suited to a particular problem, almost all such methods fundamentally rely on two types of algorithmic steps: gradient descent, which yields primal progress, and mirror descent, which yields dual progress. W…
Mirror descent method improved RL algorithms.
problem Improving RL algorithms for better performance.
method Mirror descent method applied to RL, solving trust-region problems.
result MDPO outperforms or matches other RL algorithms in continuous control tasks.
Accelerates coordinate descent methods for machine learning problems.
problem Slowness of coordinate descent methods in machine learning.
method Extrapolation-based accelerated coordinate descent.
result Significant speed-up in practice compared to existing methods.
This paper balances bias and variance in adaptive importance sampling using mirror descent.
problem Large variance in adaptive importance sampling weights.
method Regularization strategy with power raised importance weights connected to mirror descent.
result The regularization parameter balances bias and variance.
EM algorithm converges in KL divergence for exponential families via mirror descent.
problem Lack of understanding of EM's non-asymptotic convergence properties.
method Viewing EM as a mirror descent algorithm, showing convergence rates in KL divergence.
result KL divergence rates for EM in exponential families, invariant to parametrization.
VRSMD improves SMD convergence and has implicit regularization.
problem Efficiently estimating models with large datasets.
method Variance reduction in stochastic mirror descent.
result VRSMD converges to the minimum mirror interpolant.
Uniform sampling of training data has been commonly used in traditional stochastic optimization algorithms such as Proximal Stochastic Gradient Descent (prox-SGD) and Proximal Stochastic Dual Coordinate Ascent (prox-SDCA). Although uniform sampling can guarantee that the sampled stochastic quantity is an unbiased estim…
New method improves convergence and reduces variance in noisy optimization problems.
problem Computing exact minimizers with noisy gradient information.
method Stochastic mirror descent with interacting particles.
result Interaction helps improve convergence and reduce variance.
The paper analyzes EM for Mixtures of Experts and shows its equivalence to projected Mirror Descent.
problem Training Mixtures of Experts (MoE) models.
method Rigorously analyzes Expectation Maximization (EM) for MoE models using a Mirror Descent perspective.
result Derives new convergence results and identifies conditions for local linear convergence.
Develops DP-SCD for stochastic coordinate descent, making it differentially private.
problem Privacy leak in auxiliary information during stochastic coordinate descent training.
method Develops DP-SCD, leveraging independent noise addition and decoupling/parallelizing coordinate updates.
result Demonstrates competitive performance against DP-SGD with less tuning.
Coordinate descent methods usually minimize a cost function by updating a random decision variable (corresponding to one coordinate) at a time. Ideally, we would update the decision variable that yields the largest decrease in the cost function. However, finding this coordinate would require checking all of them, which…
New MD algorithms using Tempesta logarithms for machine learning.
problem Optimization in machine learning with tailored hyperparameters.
method Developed Mirror Descent algorithms using Tempesta multi-parametric logarithms.
result Wide and flexible family of Mirror Descent and mirror-less updates.
Fast algorithm for online optimization on transport polytopes.
problem Optimizing convex objectives on transport polytopes.
method Mirror Sinkhorn algorithm combining Sinkhorn scaling and mirror descent.
result Robust and efficient online optimization for convex objectives.
In this paper we consider online mirror descent (OMD) algorithms, a class of scalable online learning algorithms exploiting data geometric structures through mirror maps. Necessary and sufficient conditions are presented in terms of the step size sequence for the convergence of an OMD algorithm with respe…
New algorithm for reinforcement learning reduces complexity and guarantees convergence.
problem Reinforcement learning problems with convex occupancy measures.
method MD-CURL, inspired by mirror descent, uses non-standard regularization.
result Achieves convergence guarantees and simple closed-form solution.
Paper uses Stochastic Mirror Descent for large-scale sparse recovery problems.
problem Statistical estimation of high-dimensional sparse parameters.
method Non-Euclidean Composite Stochastic Mirror Descent (CSMD) algorithm for solving penalized stochastic optimization problems.
result The proposed algorithm achieves optimal convergence in sparse Generalized Linear Regression problems.