Research map / Optimization / Nonconvex and smooth optimization
Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows mirror descent can amplify initialization perturbations exponentially in ηT even with convex smooth objectives and well-conditioned or linear-objective KL settings, and proposes two Bregman-anchored MD variants to restore stability.
Problem
Initialization sensitivity of mirror descent dynamics: how much a small perturbation of the starting point (often a pretrained or aligned model) can be amplified over T steps, compared with gradient descent and quadratic regularization.
Approach
Constructs convex smooth examples in R^3 with a strongly convex, smooth, nonquadratic regularizer where transverse perturbations grow exponentially along a rotating frame, and shows entropic MD on the simplex amplifies perturbations exponentially even for linear objectives; then adds Bregman anchoring (to initialization or to a fixed point) to stabilize the dynamics.
Key results
- In R^3 with well-conditioned regularizer (kappa O(1)), MD initialization stability is Omega(min{polylog^{-1}(1/eps), eps e^{c eta T}}) while GD-type quadratic MD stays O(eps).
- For negative-entropy MD on the simplex with linear objectives, delta >= (1/5) min{1, e^{eta T} eps, eps/w0_min}, uniform over initializations when d >= 1/eps.
- Initialization-anchored MD achieves stability O(eps*beta + 1/sqrt(T log T)) in well-conditioned settings; fixed-anchor MD achieves O(1/T) stability even for ill-conditioned regularizers, with optimization error O(log T / T).
Surprising findings
- Entropic MD can be exponentially unstable even for fixed linear objectives and initializations near the simplex center.
- Anchoring at the initialization only partially mitigates instability in ill-conditioned settings, while anchoring at a fixed point yields stability.
Limitations
- Results are worst-case adversarial lower bounds; average-case behavior is not analyzed.
- Fixed-anchor stability bound does not depend explicitly on perturbation size epsilon.
- No experiments on LLM or RL settings; the connection to practice is theoretical.
Experimental setup
Metrics: initialization stability optimization error
Baselines: gradient descent quadratic-regularized mirror descent vanilla mirror descent
Builds on: mirror descent gradient descent relative smoothness KL-regularized policy optimization
Closest papers by meaning
- Learning mirror maps in policy mirror descent (ICLR 2025 · similarity 0.89)
- Convergence of Policy Mirror Descent Beyond Compatible Function Approximation (ICML 2025 · similarity 0.88)
- Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs (NeurIPS 2026 · similarity 0.88)
- Operator World Models for Reinforcement Learning (NeurIPS 2024 · similarity 0.87)
- Local and Adaptive Mirror Descents in Extensive-Form Games (NeurIPS 2024 · similarity 0.87)
- Mirror and Preconditioned Gradient Descent in Wasserstein Space (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.