Scholarlink

<p>We prove new complexity bounds for the <i>primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD)</i>, which has been shown to obtain promising practical performance for solving convex-concave min-max problems with bilinear coupling and dual separability. Such problems arise in many machine learning contexts, including empirical risk minimization, matrix games, and image processing. Our results either match or improve the best-known complexities of first-order algorithms for dense and sparse (strongly)-convex-(strongly)-concave problems with bilinear coupling.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On the complexity of a simple primal-dual coordinate method

  • 期刊论文

  • 发表日期：

    2025年9月22日

查看全文
  • Ahmet Alacaoglu,
  • Volkan Cevher,
  • Stephen J. Wright

摘要

We prove new complexity bounds for the primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD), which has been shown to obtain promising practical performance for solving convex-concave min-max problems with bilinear coupling and dual separability. Such problems arise in many machine learning contexts, including empirical risk minimization, matrix games, and image processing. Our results either match or improve the best-known complexities of first-order algorithms for dense and sparse (strongly)-convex-(strongly)-concave problems with bilinear coupling.