A New Kernel Regularity Condition for Distributed Mirror Descent: Broader Coverage and Simpler Analysis

• URL: http://arxiv.org/abs/2603.12838v1
• Date: Fri, 13 Mar 2026 09:40:15 GMT
• Title: A New Kernel Regularity Condition for Distributed Mirror Descent: Broader Coverage and Simpler Analysis
• Abstract summary: Hessian relative uniform continuity guarantees convergence under mild conditions.<n>We derive convergence guarantees for mirror descent-based gradient tracking without imposing any restrictive assumptions.
• Score: 12.17232701440245
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Existing convergence of distributed optimization methods in non-Euclidean geometries typically rely on kernel assumptions: (i) global Lipschitz smoothness and (ii) bi-convexity of the associated Bregman divergence function. Unfortunately, these conditions are violated by nearly all kernels used in practice, leaving a huge theory-practice gap. This work closes this gap by developing a unified analytical tool that guarantees convergence under mild conditions. Specifically, we introduce Hessian relative uniform continuity (HRUC), a regularity satisfied by nearly all standard kernels. Importantly, HRUC is closed under concatenation, positive scaling, composition, and various kernel combinations. Leveraging the geometric structure induced by HRUC, we derive convergence guarantees for mirror descent-based gradient tracking without imposing any restrictive assumptions. More broadly, our analysis techniques extend seamlessly to other decentralized optimization methods in genuinely non-Euclidean and non-Lipschitz settings.

Related papers

• Sharper Analysis of Single-Loop Methods for Bilevel Optimization [81.36947969465848]
  We establish sharper convergence results for single-loop approximate implicit differentiation (AID) and iterative differentiation (ITD) methods.<n>We prove that the error is $mathcalO(2)$, exactly matching the known lower bound and improving upon the previous $mathcalO(3)$ guarantee.
  arXiv  Detail & Related papers  (2026-07-11T11:41:42Z)
• Consequences of Kernel Regularity for Bandit Optimization [4.655159257282135]
  We show that kernel-based and locally adaptive algorithms can be analyzed within a unified framework.<n>This allows us to derive explicit regret bounds for each kernel family, obtaining novel results in several cases and providing improved analysis for others.
  arXiv  Detail & Related papers  (2025-12-05T18:54:09Z)
• 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)
• Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel [55.82768375605861]
  We establish a generalization bound for gradient flow that aligns with the classical Rademacher complexity for kernel methods.<n>Unlike static kernels such as NTK, the LPK captures the entire training trajectory, adapting to both data and optimization dynamics.
  arXiv  Detail & Related papers  (2025-06-12T23:17:09Z)
• Mirror Descent Under Generalized Smoothness [23.5387392871236]
  We introduce a new $ell*$-smoothness concept that measures the norm of Hessians in terms of a general norm and its dual.<n>We establish convergence for mirror-descent-type algorithms, matching the rates under the classic smoothness.
  arXiv  Detail & Related papers  (2025-02-02T11:23:10Z)
• Learning Analysis of Kernel Ridgeless Regression with Asymmetric Kernel Learning [33.34053480377887]
  This paper enhances kernel ridgeless regression with Locally-Adaptive-Bandwidths (LAB) RBF kernels. For the first time, we demonstrate that functions learned from LAB RBF kernels belong to an integral space of Reproducible Kernel Hilbert Spaces (RKHSs)
  arXiv  Detail & Related papers  (2024-06-03T15:28:12Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence [25.717501580080846]
  This paper revisits the convergence of gradient Forward Mirror (SMD) in the contemporary non optimization setting. For the training, we develop provably convergent algorithms for the problem of linear networks.
  arXiv  Detail & Related papers  (2024-02-27T17:56:49Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Decentralized Weakly Convex Optimization Over the Stiefel Manifold [28.427697270742947]
  We focus on the Stiefel manifold in the decentralized setting, where a connected network of agents in $nMn log-1)$ are tested. We propose an method called the decentralized subgradient method (DRSM)$ for forcing a natural station below $nMn log-1)$.
  arXiv  Detail & Related papers  (2023-03-31T02:56:23Z)
• Kernel Ridge Regression Inference [5.981623867626376]
  We construct valid and sharp confidence sets that shrink at nearly the minimax rate, allowing nonstandard regressors.<n>We use the procedure to develop a test for match effects, i.e. whether students benefit more from the schools they rank highly.
  arXiv  Detail & Related papers  (2023-02-13T18:26:36Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  Coordinate-type subgradient methods for addressing nonsmooth problems are relatively underexplored due to the set of properties of the Lipschitz-type assumption.
  arXiv  Detail & Related papers  (2022-06-30T02:17:11Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems. Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
  arXiv  Detail & Related papers  (2021-07-23T13:43:34Z)

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.