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 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.
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.
Two adaptive algorithms improve tracking regret in dynamic expert advice problems.
problem Prediction with expert advice in dynamic environments.
method Developed two adaptive and efficient algorithms using online mirror descent framework.
result Achieved data-dependent tracking regret bounds for both algorithms.
OMD and DA perform similarly in static settings but OMD is inferior under dynamic learning rates.
problem Proving and understanding the performance difference between OMD and DA under dynamic learning rates.
method Introducing stabilization to OMD and modifying its convergence analysis.
result OMD with stabilization and DA have the same performance guarantees under dynamic learning rates.
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.
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.
This work addresses decentralized online optimization in non-stationary environments. A network of agents aim to track the minimizer of a global time-varying convex function. The minimizer evolves according to a known dynamics corrupted by an unknown, unstructured noise. At each time, the global function can be cast as…
Paper connects DP and optimization for RL, suggesting new algorithms.
problem Optimizing scalar objectives in RL.
method Drawing connections between DP and optimization algorithms.
result Links between DP schemes and optimization algorithms.
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.
Continuous-time Sinkhorn flow generalizes and unifies existing dynamics.
problem Entropy-regularized optimal transport problems.
method Continuous-time mirror descent framework.
result Unified perspective on various dynamics in ML and math.
Method identifies mixed Nash equilibria in high dimensions for training mixtures of GANs.
problem Finding Nash equilibria in two-player zero-sum continuous games, especially in high dimensions.
method Parametrizing mixed strategies as mixtures of particles, updating their positions and weights using gradient descent-ascent.
result Global convergence to an approximate equilibrium for the related Langevin gradient-ascent dynamic.
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.
We formulate and study a general family of (continuous-time) stochastic dynamics for accelerated first-order minimization of smooth convex functions. Building on an averaging formulation of accelerated mirror descent, we propose a stochastic variant in which the gradient is contaminated by noise, and study the resultin…
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 k k k -sparse vectors with minimum non-zero entry order of ∥ x ⋆ ∥ 2 / k \| \mathbf{x}^\star \|_2/\sqrt{k} ∥ x ⋆ ∥ 2 / k from k 2 k^2 k 2 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.
We accelerate PMD algorithms for reinforcement learning using functional methods.
problem Improving reinforcement learning algorithms for large-scale optimization.
method Proposed a momentum-based update for PMD algorithms leveraging duality.
result The proposed method accelerates reinforcement learning algorithms.
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 k k k -sparse signals. Extends Langevin dynamics for constrained domains.
problem Optimization of constrained probability measures.
method Mirror mean-field Langevin dynamics (MMFLD).
result Linear convergence guarantees and propagation of chaos results.
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…
Study mirrors descent's early stopping for linear and kernel models, improving risk guarantees.
problem Understanding the statistical performance of early-stopped mirror descent algorithms.
method Characterized convexity of squared loss, identified link between offset Rademacher complexities and mirror descent convergence.
result Excess risk guarantees for mirror descent iterates traced by the path, expressed in terms of offset complexities.
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.
New perspective on Sinkhorn algorithm using stochastic mirror descent.
problem Optimal transport with unbounded domain and non-smooth objective.
method Stochastic mirror descent applied to relative smoothness.
result Sinkhorn algorithm as a special case of stochastic 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.
VRMPO improves reinforcement learning efficiency with stochastic mirror descent.
problem Improving sample efficiency in reinforcement learning.
method VRMPO algorithm with a variance-reduced policy gradient estimator and stochastic mirror descent.
result VRMPO achieves an ε-approximate first-order stationary point with only O(ε^(-3)) sample trajectories.
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.
Optimistic Mirror Descent framework improves bidding strategies in non-stationary first-price auctions.
problem Optimizing bidding strategies in non-stationary first-price auctions.
method Introducing Optimistic Mirror Descent (OMD) framework with novel optimism configuration.
result Minimax-optimal dynamic regret rates achieved for non-stationary first-price auctions.
Proposes a new algorithm for robust learning in Schrödinger bridge problems.
problem Uncertainty in estimated learning signals in Schrödinger bridge problems.
method Variational Online Mirror Descent (OMD) framework for Schrödinger bridge problems.
result Formally proves convergence and a regret bound for the OMD formulation of Schrödinger bridge acquisition.
Novel algorithms for entropic optimal transport from an optimisation perspective.
problem Solving the entropic-regularised optimal transport problem.
method Developed novel methods inspired by mirror descent, solving semi-dual problems or non-convex constrained problems over joint distributions.
result Non-asymptotic rates of convergence for the proposed methods under minimal assumptions.
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…
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.
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.
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.
Mirror Descent framework for efficient neural network quantization.
problem Efficiently quantize large neural networks for resource-limited devices.
method Introduce Mirror Descent framework for constrained optimization of quantized neural networks.
result Mirror Descent framework achieves state-of-the-art performance in quantized neural networks.
The paper connects mirror descent, Thompson sampling, and information ratio in online learning.
problem Analyzing and improving regret guarantees in online learning algorithms.
method Combining information-theoretic analysis with minimax duality and mirror descent techniques.
result An efficient algorithm with matching regret guarantees for adversarial bandits and improved guarantees for other settings.
Improved reinforcement learning algorithm with linear approximation for unknown dynamics.
problem Reinforcement learning with adversarial changing cost functions and bandit feedback.
method Combines mirror-descent and least squares policy evaluation in an auxiliary MDP.
result Obtains an O ~ ( K 6 / 7 ) \widetilde O(K^{6/7}) O ( K 6/7 ) regret bound, significantly improving over previous methods. 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.
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.
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.
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…