A New Kernel Regularity Condition for Distributed Mirror Descent: Broader Coverage and Simpler Analysis
Junwen Qiu, Ziyang Zeng, Leilei Mei, Junyu Zhang · 2026
Read A New Kernel Regularity Condition for Distributed Mirror Descent: Broader Coverage and Simpler Analysis by Junwen Qiu, Ziyang Zeng, Leilei Mei, Junyu Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-12838.txt.
Introduction
Junwen Qiu and co-authors widen the theory for distributed mirror descent in non-Euclidean geometry. Standard proofs need kernel traits that nearly all kernels in practice fail to meet. That gap left theory far behind practice. Their new condition, Hessian relative uniform continuity, holds for nearly all standard kernels. It also survives scaling, composition, and kernel mixes. With it, they prove convergence for gradient tracking with no harsh assumptions, and the tools extend to other decentralized methods.
Catalog record
| CREATOR | Junwen Qiu, Ziyang Zeng, Leilei Mei, Junyu Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85253 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.12838
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A New Kernel Regularity Condition for Distributed Mirror Descent: Broader Coverage and Simpler Analysis Junwen Qiu, Ziyang Zeng, Leilei Mei, Junyu Zhang 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. Keywords: Distributed mirror descent, kernel regularity, relative uniform continuity, gradient tracking, dual mixing 1 Introduction In this paper, we consider the mirror descent based algorithms for the nonconvex distributed optimization problem: \mathop{\rm minimize}_{x_{1},\cdots,x_{m}\in\,\mathcal{Z}}\;\;\frac{1}{m}\sum_{i=1}^{m}f_{i}(x_{i})\quad\mbox{s.t.}\quad x_{1}=\cdots=x_{m}. (1) Each local objective function f_{i} is continuously differentiable and possibly nonconvex, and we denote f=\frac{1}{m}\sum_{i}f_{i} the global objective function. The set \mathcal{Z}\subseteq\mathbb{R}^{d} is closed, convex, and is associated with a Legendre-type Bregman distance generating kernel h . For problem ( 1 ), the consensus mixing-based first order methods such as distributed gradient descent ( DGD ) [ 33 , 21 , 19 , 37 ] , gradient tracking ( GT ) [ 25 ] , and their numerous variants [ 30 , 20 , 28 , 38 ] form a major class of algorithms. Due to the potential to adapt to a problem’s local geometry and the ability to handle general relative smooth (non-Lipschitz smooth) problems [ 3 , 4 , 17 ] , the mirror descent technique [ 22 ] has also been naturally introduced to this area. Unfortunately, despite being broadly studied, existing trials to introduce mirror descent to consensus mixing type algorithms typically require two restrictive conditions on kernel h : (C.1) Lipschitz Smoothness: the mirror map \nabla h is Lipschitz continuous. (C.2) Bi-Convexity: the Bregman divergence \mathcal{D}_{h}(u,v) is convex in v . Table 1: Summary of common kernels, their domains, and which condition they satisfy. Here, we denote x=[x_{(1)},\ldots,x_{(d)}]^{\top}\in\mathbb{R}^{d} to avoid confusion with the agent index subscripts. Although most kernels violate conditions (C.1) – (C.2) , they all satisfy the HRUC regularity condition ( Definition 3.1 ) with the associated function \zeta(\cdot) . Detailed proofs are provided in Section 4 . † † nicematrix-placeholder: NiceTabular (nicematrix) Here, the Bregman divergence is given by \mathcal{D}_{h}(u,v):=h(u)-h(v)-\langle\nabla h(v),u-v\rangle . In particular, we call (C.2) bi-convexity because \mathcal{D}_{h}(u,v) is already convex in u as the kernel h is always convex in the context of mirror methods. The two conditions (C.1) – (C.2) are often imposed jointly, see [ 8 , 9 , 15 , 18 , 29 , 31 , 34 , 35 , 36 , 39 , 42 ] and references therein. However, as summarized in Table 1 , most of the kernels violate at least one of these two conditions, except for the classic (Euclidean) quadratic kernel h(x)=\tfrac{1}{2}\|x\|^{2}_{A},A\succ 0 , which essentially limits the corresponding analysis to standard distributed algorithms with preconditioning. This raises a central question: can we provide a theoretically sound approach to introduce the mirror descent techniques to the consensus mixing based distributed first order algorithms? Observe that most existing works commonly adopt a primal consensus mixing step in the algorithm design, see [ 15 , 8 , 9 , 18 , 29 , 31 , 34 , 35 , 36 , 39 , 42 , etc.] . In these works, given a mixing matrix W , an update direction y_{i}^{t} , and a step size \eta_{t} , the update for each local agent i takes the form: \nabla h(x_{i}^{t+1})=\nabla h\Big({\sum}_{j=1}^{m}W_{(i,j)}\,x_{j}^{t}\Big)-\eta_{t}y_{i}^{t}, (2) which follows a mix-and-mirror (primal mixing) scheme. The bi-convexity assumption (C.2) is essentially introduced to address the non-commutative issue between the nonlinear mirror map \nabla h(\cdot) and the mixing operator \sum_{j}W_{(i,j)}(\cdot) , which, together with the Lipschitz smoothness assumption (C.1) , serve as the technical artifacts for decreasing objective value and consensus error. To resolve these issues, we propose the following approaches, which also consist the major contributions of this paper. New regularity condition. First, we introduce a new Hessian relative uniform continuity (HRUC, Definition 3.1 ) regularity condition, which, instead of assuming the upper boundedness of \nabla^{2}h , requires the kernel Hessian not to explode too rapidly. Informally, HRUC assumes that the kernel Hessians are close in a relative sense: \mathcal{R}_{h}(x,y):=\left\|I-\nabla^{2}h(x)\left[\nabla^{2}h(y)\right]^{-1}\right\|\leq\zeta(\delta) (3) for any x,y that are close in the dual space \|\nabla h(x)-\nabla h(y)\|\leq\delta , for any \delta>0 . The \zeta(\cdot) function controls the variation of \nabla^{2}h , and it satisfies \zeta(\delta)\to 0 as \delta\to 0 . This essentially implies that the kernel Hessian \nabla^{2}h is uniformly continuous with respect to the relative difference and the dual space distance . In sharp contrast to conditions (C.1) – (C.2) , HRUC holds for nearly all kernels, as demonstrated in Table 1 . Therefore, HRUC is more of an intrinsic structural property of the mirror methods, rather than a pure technical artifact. Moreover, we show that the HRUC is closed under concatenation, composition, and conic combination, allowing us to synthesize problem-specific kernels by manipulating standard basic building blocks. In addition, we would like to emphasize that the significance of HRUC regularity is beyond the application to distributed optimization in this paper. One can observe that the vanilla (centralized) mirror descent is approximately a preconditioned gradient descent with a time-varying preconditioner: x^{t+1}=\nabla h^{*}(\nabla h(x^{t})-\eta_{t}g^{t})=x^{t}-\eta_{t}[\nabla^{2}h(x^{t})]^{-1}g^{t}+o(\eta_{t}\|g^{t}\|). A guaranteed smooth variation of kernel Hessian (the preconditioner) potentially enables the transformation of many well-developed analysis techniques of gradient methods to mirror descent by viewing the inverse Hessian as variable metrics, which we plan to explore in future works. Dual consensus mixing. Second, we develop a dual consensus mixing scheme: \nabla h(x_{i}^{t+1})={\sum}_{j=1}^{m}W_{(i,j)}\big(\nabla h(x_{j}^{t})-\eta_{t}y_{j}^{t}\big), (4) which, in contrast to the mix-and-mirror update in ( 2 ), follows a reverse mirror-and-mix update order. Interestingly, consider the average iterates in the dual space \bar{z}^{t}=\frac{1}{m}\sum_{i}\nabla h(x_{i}^{t}) and \bar{x}^{t}=\nabla h^{*}(\bar{z}^{t}) , ( 4 ) can be viewed as approximately executing the mirror descent on the dual average point: \nabla h(\bar{x}^{t+1})=\nabla h(\bar{x}^{t})-\eta_{t}\nabla f(\bar{x}^{t})+\mathcal{E}_{t} , while the error term \mathcal{E}_{t} diminishes upon consensus. By directly exchange the order of mirror and mixing operators in ( 2 ), we avoid the the bi-convexity assumption (C.2) . As an illustration, we adopt the GT scheme for y_{i}^{t} to track the gradient and design a Dual Mixing Gradient Tracking ( DMGT ) method. Broader convergence guarantees. To broaden the coverage of our theory, we adopt a general relative smoothness assumption [ 3 , 17 , 4 ] on the objective function, which relaxes the global Lipschitz smoothness and enables analyses of mirror descent for non-Lipschitz smooth objectives [ 3 , 17 , 4 , 14 , 10 , 40 ] . Then leveraging the geometric structure induced by HRUC and dual mixing, we derive an \mathcal{O}(1/T) convergence for DMGT in terms of the Bregman residual and consensus error. By avoiding (C.1) –