{"ID":3004758,"CreatedAt":"2026-06-03T03:09:48.883664427Z","UpdatedAt":"2026-06-05T11:43:53.432517148Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.03769","arxiv_id":"2606.03769","title":"Bregman meets Lévy: Stochastic mirror descent with heavy-tailed noise in continuous and discrete time","abstract":"We study the robustness of stochastic mirror descent (SMD) under heavy-tailed noise, focusing on whether the method retains its convergence guarantees when run with infinite-variance stochastic gradient input. To address this question in a principled manner, we begin by introducing a continuous-time model of SMD as a stochastic differential equation (SDE) driven by a centered Lévy noise process with finite $p$-th order moments, $1 \u003c p \\leq 2$. This scheme -- which we call the Lévy mirror flow (LMF) -- arises naturally as the scaling limit of SMD in the presence of heavy-tailed noise. In particular, when $p \u003c 2$ -- the heavy noise regime -- the trajectories of LMF generically exhibit jump discontinuities of arbitrary magnitude which, if frequent enough, lead to infinite variance. Nonetheless, despite this highly singular behavior, we show that LMF attains $ε$-optimality within $\\mathcal{O}(ε^{-p/(p-1)})$ time in the convex case, and within $\\mathcal{\\tilde O}(ε^{-1/(p-1)})$ time for (relatively) strongly convex objectives. These guarantees provide a transparent characterization of the impact of frequent long jumps on the convergence of the process, and percolate to a series of matching discrete-time guarantees for several variants of SMD under heavy-tailed noise.","short_abstract":"We study the robustness of stochastic mirror descent (SMD) under heavy-tailed noise, focusing on whether the method retains its convergence guarantees when run with infinite-variance stochastic gradient input. To address this question in a principled manner, we begin by introducing a continuous-time model of SMD as a s...","url_abs":"https://arxiv.org/abs/2606.03769","url_pdf":"https://arxiv.org/pdf/2606.03769v1","authors":"[\"Pierre-Louis Cauvin\",\"Panayotis Mertikopoulos\"]","published":"2026-06-02T15:23:04Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.LG\",\"math.PR\"]","methods":"[]","has_code":false}