Clipping in the Mirror: Heavy-Tailed High-Probability Guarantees for Mirror Descent, Measured Seed by Seed

Mirror descent is a version of gradient descent that measures distance with a geometry suited to the problem. A common example is the entropy-based distance (the Kullback–Leibler divergence) on the probability simplex, which keeps iterates valid probability vectors. This geometry is behind many methods for distributionally robust learning, entropic risk, and sparse high-dimensional models. Its theory now promises more than good average behavior. High Probability Convergence for Accelerated Stochastic Mirror Descent proves that a single run succeeds with probability $1-\delta$, at a cost growing only like $\ln(1/\delta)$. Two caveats limit that result. It assumes light-tailed (sub-Gaussian) gradient noise, and it was never run: that paper states that no datasets were used. The objectives where mirror geometry matters most, such as exponentially weighted losses in robust optimization, produce stochastic gradients whose tails are heavy. Nobody has checked whether the promised $\ln(1/\delta)$ tail survives there.

This note proposes a clipped stochastic mirror descent with a specific design rule: clip the gradient in the dual norm that the mirror map induces, not in the Euclidean norm. We would prove a high-probability rate for this method under heavy-tailed noise that depends on the initial Bregman distance. We would also introduce an evaluation protocol that tests probabilistic guarantees directly. The protocol runs each method over a thousand seeds and plots the empirical $(1-\delta)$-quantile of the final error against $\ln(1/\delta)$. A guarantee of the form "error grows like $\ln(1/\delta)$" predicts a straight line on that plot, so the line's shape and slope are what we check.

Core Claim

Clipping is the standard fix for heavy-tailed noise. High-Probability Complexity Bounds for Non-smooth Stochastic Convex Optimization with Heavy-Tailed Noise proves $\ln(1/\delta)$ bounds under heavy tails for clipped Euclidean methods. That paper supplies our technique, but its analysis lives in Euclidean geometry.

Simply bolting Euclidean clipping onto mirror descent creates a mismatch. On the $d$-dimensional simplex with the entropy mirror map, the convergence analysis controls gradients in the $\ell_\infty$ norm, the dual of the $\ell_1$ norm in which entropy is strongly convex. A Euclidean threshold therefore scales like $\sqrt d$ relative to the quantity that matters. It either clips almost nothing, so outliers pass through, or it clips nearly every gradient, which adds bias. Clipping in the dual norm removes this mismatch.

We claim three things for clipping in the dual norm $\|\cdot\|_*$ of the mirror map $\psi$, combined with the weighted-martingale argument of Ene and Nguyen. First, it gives a high-probability rate for convex non-smooth problems whose noise has only a bounded moment of order $\alpha \in (1,2]$. Second, that rate depends on $D_\psi(x^*,x_1)$, the Bregman distance from the starting point to the optimum, rather than on the domain diameter, and is multiplied by $\ln(1/\delta)$. Third, the dimension dependence is the mirror-descent one, $\log d$ on the simplex, rather than the polynomial dimension dependence that Euclidean clipping inherits. The expected $T$-dependence is the analogue of the Euclidean clipped rate. The new parts are where $D_\psi$ enters the bound and the dimension factor.

The empirical claim is falsifiable. On problems with naturally heavy-tailed gradients, the quantile curve of dual-clipped mirror descent should be close to linear in $\ln(1/\delta)$ with a small slope. Unclipped mirror descent should show a curve that bends upward in the tail. Euclidean-clipped mirror descent's slope should worsen as $d$ grows.

Research Program

The theory work has three parts. The first is the algorithm. At each step it takes a stochastic gradient $g_t$ and rescales it to $\tilde g_t = \min(1, \lambda_t/\|g_t\|_*)\, g_t$, where $\lambda_t$ is the clipping level. It then performs the usual mirror step $x_{t+1} = \arg\min_y \{\eta_t\langle \tilde g_t, y\rangle + D_\psi(y,x_t)\}$, where $\eta_t$ is the step size.

The second part is the analysis. Clipping splits the error into a bounded martingale part and a bias part. Ene and Nguyen's non-increasing weights $w_t$ handle the martingale part without a diameter bound. Gorbunov et al.'s choice of $\lambda_t$ trades bias against variance. The technical obstacle is that the bias must be bounded in the dual norm, and on an unbounded domain we must keep $D_\psi(x^*,x_t)$ controlled with high probability along the whole trajectory. We expect this step to require an induction on the event that the iterates stay within a $D_\psi$-ball.

The third part is scope. We deliberately exclude non-convex objectives and relatively smooth problems whose mirror map lacks a fixed dual norm, such as Burg entropy for Poisson problems. Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence handles the non-convex case only under sub-Gaussian noise, which motivates a follow-up but is out of scope here. For Poisson problems we report empirical results without claiming theory.

The empirical work is the tail-profiling protocol. Every configuration runs with 1,000 independent seeds. The headline output is the error quantile at $\delta \in \{0.5, 0.1, 0.01, 0.001\}$, together with the fitted slope of quantile versus $\ln(1/\delta)$ and a curvature test for departures from linearity. Mean error alone hides exactly the failures a high-probability guarantee is meant to rule out.

We will also check whether the constants in the theorem predict the observed slope to within an order of magnitude. Whether a theorem's constants survive contact with data is the question raised by the gap between theory and practice for methods like Linear Convergence with Condition Number Independent Access of Full Gradients, whose high-probability claims were never benchmarked.

Baselines

The naive reference point is unclipped stochastic mirror descent, using the weighted step sizes of High Probability Convergence for Accelerated Stochastic Mirror Descent. It is the method whose guarantee we are stress-testing, and we know of no published run of it. We will run it with the same mirror map, data, and step-size grid as our method. Beating it means a smaller error quantile at $\delta = 0.01$ and $0.001$ with no loss in the median.

The strongest heavy-tail competitor is Euclidean clipped SGD with projection onto the feasible set, following High-Probability Complexity Bounds for Non-smooth Stochastic Convex Optimization with Heavy-Tailed Noise. It already enjoys a $\ln(1/\delta)$ guarantee, so it is the method that must lose for the geometry to matter.

For the robust-optimization tasks we add SCENT from A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimization. SCENT is the strongest existing mirror-type method for these objectives, with expected-value guarantees and overflow-safe updates. We also add the Safe-KL relaxation of Improved Stochastic Optimization of LogSumExp, which caps density ratios and so implicitly limits tails. For both, Lacuna lists no reported numeric result on California Housing, Abalone, or ACS PUMS, so we will reproduce them.

The closest reported number in the file is from Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction. On RCV1, Bregman-SAGA reaches suboptimality $10^{-13}$ in about 80 epochs while Bregman SGD plateaus at $10^{-2}$. That result concerns variance reduction on a finite sum, not tail behavior. We include Bregman-SAGA on RCV1 as a reference and report its quantiles too.

The key ablation isolates the clipping norm. We run mirror descent with Euclidean-norm clipping, with coordinate-wise clipping, and with dual-norm clipping, holding everything else fixed.

Every method gets the same gradient-evaluation budget and the same 30-configuration tuning grid for step size and clipping level. Tuning is done on held-out seeds, separate from the 1,000 evaluation seeds.

Why not just…?

Why not just run Euclidean clipped SGD with projection? It already has the right $\ln(1/\delta)$ dependence, and it is the real threat. The evidence against it is indirect. Mirror geometry pays off in high dimension: Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence reports a $\sqrt{d/\log d}$ utility gain over a Euclidean proximal method in private learning. Our dimension sweep settles the question. If the slope gap between the two methods does not grow with $d$, the geometric argument fails and we will report that.

Why not just boost confidence by running several independent copies and keeping the best on validation? This generic trick turns any in-expectation method into a $\ln(1/\delta)$ one at roughly $\ln(1/\delta)$ times the compute, so it is a serious competitor. We compare against it at equal total gradient evaluations: $k$ unclipped runs of length $T/k$ with validation selection, for $k \in \{3, 7, 15\}$. The selection step itself needs a validation estimate, which is unreliable under heavy-tailed losses. Whether that unreliability matters in practice is exactly what the experiment measures.

Why not just use larger minibatches? Averaging reduces variance, but under an infinite-variance noise model the average of heavy-tailed gradients converges slowly and still produces rare large deviations. We include minibatch sizes up to 16× at matched total samples to test whether batching alone flattens the quantile curve.

Why not just use SCENT or Safe-KL, which already stabilize these objectives? Both target overflow and bias, and their guarantees hold in expectation. Safe-KL's cap $\rho$ does bound density ratios, and if tuned well it may already control tails. Combining dual clipping with SCENT's update is a natural variant, and we test it. If tuned Safe-KL matches our tail profile, the contribution narrows to the theory and the protocol.

Proposed Experiments

The first setting has naturally heavy-tailed noise: KL-regularized robust optimization on California Housing, Abalone, and ACS PUMS 2018. Small batches ($|D| = 10$, as in the Safe-KL study) and a small temperature make the exponential sample weights heavy-tailed. We will report a tail-index estimate of the observed gradient norms so that "heavy-tailed" is measured rather than assumed.

The second setting is entropic simplex-constrained regression on the LIBSVM bodyfat, mpg, and housing datasets used by Linesearch-free adaptive Bregman proximal gradient for convex minimization without relative smoothness. We inject Student-t gradient noise with $\alpha \in \{1.5, 2.5, \infty\}$ and sweep the dimension by adding random features, giving $d$ from $10^2$ to $10^5$.

The third setting is high-dimensional sparse logistic regression on RCV1 over an $\ell_1$-ball. A tomography problem on the Shepp-Logan phantom with heavy-tailed count noise is an exploratory case outside the theory.

Metrics are the per-seed final suboptimality, its quantiles, the fitted slope and curvature against $\ln(1/\delta)$, the fraction of runs that diverge or produce NaN values, and wall-clock time.

Three decisive checks determine the outcome. First, at $\alpha = \infty$ (light tails), dual clipping should match unclipped mirror descent, so clipping costs nothing when it is unnecessary. Second, at $\alpha = 1.5$, the unclipped quantile curve should bend upward while ours stays linear. Third, the slope ratio between Euclidean-clipped and dual-clipped mirror descent should grow with $d$. If the third check fails, the proposal's central geometric claim is wrong.