A New Kernel Regularity Condition for Distributed Mirror Descent: Broader Coverage and Simpler Analysis
This work addresses a foundational problem in distributed optimization for researchers and practitioners by providing a unified analytical tool that broadens coverage to practical kernels, though it is incremental in improving theoretical analysis.
The paper tackled the gap between theory and practice in distributed optimization by introducing Hessian relative uniform continuity (HRUC), a mild regularity condition satisfied by nearly all standard kernels, and derived convergence guarantees for mirror descent-based gradient tracking without restrictive assumptions.
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.