Open Research Index

An error bound-based convergence analysis framework for a class of randomized algorithms

Zhichun Yang, Li Jiang, Tianxiang Liu, Man-Chung Yue

arXivarxiv/2603.17438Mar 18, 2026math.OCscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2603.17438
curl -X POST /api/v1/records/arxiv/2603.17438/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.17438/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'