Id: arxiv/2603.17438 Url: https://arxiv.org/abs/2603.17438 Tags: math.OC Score: 0 Title: An error bound-based convergence analysis framework for a class of randomized algorithms Domain: math.OC Source: arxiv Authors: Zhichun Yang, Li Jiang, Tianxiang Liu, Man-Chung Yue Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-18 Page: https://delphi.science/r/arxiv/2603.17438 Classical analyses show that randomized coordinate descent (RCD) and gradient descent (GD) share the same convergence rates in terms of objective gap under convexity and specific global EB-type assumptions. However, this rate preservation phenomenon does not extend to iterate rates, almost-sure rates, or general local error bound conditions. In this paper, we study this phenomenon systematically, not only for RCD but also for a much broader class of algorithms that share the same structures. Specifically, we introduce an abstract class of algorithms, called monotone randomized algorithms…