Search papers, labs, and topics across Lattice.
This paper introduces the dual kernel conditioning (DKC) regularity condition to analyze optimization algorithms in the absence of global Lipschitz smoothness, a common requirement for convergence analysis. DKC, combined with relative smoothness, ensures dual Lipschitz continuity for gradients, allowing for the analysis of techniques like random reshuffling. The authors leverage DKC to establish the first complexity bounds and iterate convergence of random reshuffling mirror descent for constrained nonconvex relative smooth problems.
Random reshuffling mirror descent, previously unanalyzable for constrained nonconvex relative smooth problems, now has proven complexity bounds thanks to a novel dual kernel conditioning regularity condition.
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.
