Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning

• URL: http://arxiv.org/abs/2603.16042v1
• Date: Tue, 17 Mar 2026 01:00:40 GMT
• Title: Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning
• Abstract summary: We introduce the dual kernel conditioning (DK) to regulate the local relative kernel functions.<n>We establish the first random bounds as well as the first reshuffling mirror convergence for constrained non complexity relative smooth problems.
• Score: 13.169947576695456
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The global Lipschitz smoothness condition underlies most convergence and complexity analyses via two key consequences: the descent lemma and the gradient Lipschitz continuity. How to study the performance of optimization algorithms in the absence of Lipschitz smoothness remains an active area. The relative smoothness framework from Bauschke-Bolte-Teboulle (2017) and Lu-Freund-Nesterov (2018) provides an extended descent lemma, ensuring convergence of Bregman-based proximal gradient methods and their vanilla stochastic counterparts. However, many widely used techniques (e.g., momentum schemes, random reshuffling, and variance reduction) additionally require the Lipschitz-type bound for gradient deviations, leaving their analysis under relative smoothness an open area. To resolve this issue, we introduce the dual kernel conditioning (DKC) regularity condition to regulate the local relative curvature of the kernel functions. Combined with the relative smoothness, DKC provides a dual Lipschitz continuity for gradients: even though the gradient mapping is not Lipschitz in the primal space, it preserves Lipschitz continuity in the dual space induced by a mirror map. We verify that DKC is widely satisfied by popular kernels and is closed under affine composition and conic combination. With these novel tools, we establish the first complexity bounds as well as the iterate convergence of random reshuffling mirror descent for constrained nonconvex relative smooth problems.

Related papers

• Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization [20.87701856262044]
  We analyze Bregman ADMM for non linearly constrained problems under two-sided relative smoothness.<n>We extend the analysis to multiblock star consensus formulation for distributed optimization.
  arXiv  Detail & Related papers  (2026-06-26T17:52:39Z)
• Lipschitz bounds for integral kernels [6.116995698762512]
  We study the regularity of feature maps associated with integral kernels under differentiability assumptions.<n>We show that the Lipschitz constant of the associated kernel can be expressed as the supremum of a two-dimensional integral.<n>We also raise an open question concerning the behavior of the convergence of the Lipschitz constant in finite width neural networks.
  arXiv  Detail & Related papers  (2026-04-03T08:52:36Z)
• Near-optimal delta-convex estimation of Lipschitz functions [0.913755431537592]
  This paper presents a tractable algorithm for estimating an unknown Lipschitz function from noisy observations.<n>The framework is also straightforward to adapt to shape-restricted regression.
  arXiv  Detail & Related papers  (2025-11-19T17:02:30Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness [50.78508362183774]
  Shuffling-type gradient methods are favored in practice for their simplicity and rapid empirical performance.<n>Most require the Lipschitz condition, which is often not met in common machine learning schemes.
  arXiv  Detail & Related papers  (2025-07-11T15:36:48Z)
• A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions [7.972544890243396]
  This paper presents a unified analysis for the proximal subgradient method (Prox-SubGrad) type approach. We are able to relate error-bound conditions, the growth conditions of the subgradients of the objective, and the behavior of the proximal subgradient iterates on some remarkably broad classes of objective functions.
  arXiv  Detail & Related papers  (2023-08-30T23:34:11Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  An analysis of convex and non- optimization methods often requires the Lipsitzness gradient, which limits the analysis by this trajectorys. Recent work generalizes the gradient setting via the non-uniform smoothness condition.
  arXiv  Detail & Related papers  (2023-06-02T04:21:59Z)
• Beyond Uniform Lipschitz Condition in Differentially Private Optimization [28.04430869054056]
  Most prior results on differentially private gradient descent (DP-SGD) are derived under the simplistic assumption of uniform Lipschitzness, i.e., the per-sample gradient is uniformly uniform. We provide principled guidance choosing the norm over-dependent in our general version of Lipschitzness when the per-sample Lipschitz constants are bounded.
  arXiv  Detail & Related papers  (2022-06-21T20:11:30Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum Optimization [7.014966911550542]
  We consider the problem of training a deep neural network with nonsmooth regularization to retrieve a sparse sub-structure. We derive a new solver, called SR2, whose convergence and worst-case complexity are established without knowledge or approximation of the gradient's Lipschitz constant. Experiments on network instances trained on CIFAR-10 and CIFAR-100 show that SR2 consistently achieves higher sparsity and accuracy than related methods such as ProxGEN and ProxSGD.
  arXiv  Detail & Related papers  (2022-06-14T00:28:44Z)
• Beyond the Edge of Stability via Two-step Gradient Updates [49.03389279816152]
  Gradient Descent (GD) is a powerful workhorse of modern machine learning. GD's ability to find local minimisers is only guaranteed for losses with Lipschitz gradients. This work focuses on simple, yet representative, learning problems via analysis of two-step gradient updates.
  arXiv  Detail & Related papers  (2022-06-08T21:32:50Z)
• Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration [30.369542816161378]
  We show that standard extragradient methods (i.e. mirror prox and dual extrapolation) recover optimal accelerated rates for first-order minimization of smooth convex functions. We generalize this framework to handle local and randomized notions of relative Lipschitzness.
  arXiv  Detail & Related papers  (2020-11-12T18:43:40Z)
• Tight Second-Order Certificates for Randomized Smoothing [106.06908242424481]
  We show that there also exists a universal curvature-like bound for Gaussian random smoothing. In addition to proving the correctness of this novel certificate, we show that SoS certificates are realizable and therefore tight.
  arXiv  Detail & Related papers  (2020-10-20T18:03:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.