Randomized subspace correction methods for convex optimization

Boou Jiang; Jinchao Xu; Jongho Park

arxiv: 2507.01415 · v4 · submitted 2025-07-02 · 🧮 math.OC · cs.NA· math.NA

Randomized subspace correction methods for convex optimization

Boou Jiang , Jongho Park , Jinchao Xu This is my paper

Pith reviewed 2026-05-19 06:54 UTC · model grok-4.3

classification 🧮 math.OC cs.NAmath.NA

keywords randomized subspace correctionconvex optimizationdomain decompositionmultigridblock coordinate descentconvergence analysisspace decomposition

0 comments

The pith

An abstract framework unifies randomized subspace correction methods for convex optimization.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper presents an abstract framework for randomized subspace correction methods applied to convex optimization problems. It unifies various existing algorithms such as domain decomposition, multigrid, and block coordinate descent into a single structure. The framework delivers convergence rate analysis that starts with minimal assumptions and extends to practical cases involving sharpness and strong convexity. A sympathetic reader would care because the results apply to general space decompositions and inexact local solvers, making it relevant for solving problems in nonlinear partial differential equations, imaging, and data science.

Core claim

The central claim is that an abstract framework for randomized subspace correction methods unifies and generalizes a broad class of algorithms for convex optimization, including domain decomposition, multigrid, and block coordinate descent. The framework provides convergence rate analysis ranging from minimal assumptions to settings with sharpness and strong convexity, while extending to arbitrary space decompositions, inexact local solvers, and weaker smoothness or convexity assumptions.

What carries the argument

The abstract framework for randomized subspace correction methods, which unifies convergence analysis across general space decompositions in convex optimization.

If this is right

Convergence rates apply to block coordinate descent with both overlapping and non-overlapping blocks.
Inexact local solvers are permitted while preserving global convergence guarantees.
Rates hold for convex problems satisfying a sharpness condition even without strong convexity.
The same analysis covers applications to nonlinear PDEs and imaging with arbitrary decompositions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The framework may allow reduction of new algorithm variants to the abstract setting for quicker convergence proofs.
Randomization probabilities could be tuned using the subspace properties identified in the analysis.
Similar unification might extend the approach to deterministic or distributed optimization methods.

Load-bearing premise

The analysis requires that the space admits a decomposition into subspaces selected with positive probability and that local corrections achieve sufficient reduction in the objective function.

What would settle it

A concrete convex optimization problem with a given space decomposition where the randomized subspace correction method fails to achieve the predicted convergence rate under the stated minimal assumptions.

read the original abstract

This paper introduces an abstract framework for randomized subspace correction methods for convex optimization, which unifies and generalizes a broad class of existing algorithms, including domain decomposition, multigrid, and block coordinate descent methods. We provide a convergence rate analysis ranging from minimal assumptions to more practical settings, such as sharpness and strong convexity. While most existing studies on block coordinate descent methods focus on nonoverlapping decompositions and smooth or strongly convex problems, our framework extends to more general settings involving arbitrary space decompositions, inexact local solvers, and problems with weaker smoothness or convexity assumptions. The proposed framework is broadly applicable to convex optimization problems arising in areas such as nonlinear partial differential equations, imaging, and data science.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper sets up a unifying abstract framework for randomized subspace correction methods that extends to arbitrary decompositions and inexact solvers while recovering standard rates for block coordinate descent and multigrid without hiding constants.

read the letter

After going through the paper, the main takeaway is that it sets up an abstract framework for randomized subspace correction methods applied to convex optimization problems. This framework unifies methods from domain decomposition, multigrid, and block coordinate descent, while allowing for arbitrary decompositions, inexact local solvers, and problems that are not necessarily smooth or strongly convex. The work does a solid job with the convergence analysis. It starts with minimal assumptions and builds up to cases with sharpness and strong convexity. The proofs appear to handle the dependence on the decomposition constant in a transparent way, and specializing the general results gives back the expected rates from earlier literature on block coordinate descent and similar methods. This is a good sign that the analysis is consistent. What the paper handles well is the extension beyond the usual nonoverlapping smooth cases that dominate much of the block coordinate descent literature. It opens the door to more flexible setups that could be relevant for applications in nonlinear PDEs, imaging, and data science. There are a couple of minor points worth noting. The practical utility will hinge on being able to control or estimate that decomposition constant in specific problems, and while the theory is general, additional examples or bounds for common decompositions might help readers see the advantages more concretely. Still, this is not a central weakness given the theoretical focus. Overall, this is the sort of paper that researchers working on optimization algorithms or numerical methods for PDEs would find useful. It engages honestly with the existing body of work and provides a structured way to think about these methods. I think it merits sending out for peer review, as the claims are backed by careful reductions to known results.

Referee Report

0 major / 2 minor

Summary. The paper introduces an abstract framework for randomized subspace correction methods for convex optimization. It unifies and generalizes a broad class of existing algorithms including domain decomposition, multigrid, and block coordinate descent. The framework supplies convergence rate analysis ranging from minimal assumptions on convexity and smoothness to stronger settings such as sharpness and strong convexity, while accommodating arbitrary space decompositions, inexact local solvers, and weaker problem assumptions.

Significance. If the stated convergence results hold, the work supplies a unified theoretical lens for a wide family of subspace correction schemes. Explicit tracking of the finite decomposition constant in the proofs, together with correct reduction to known rates for block coordinate descent, domain decomposition, and multigrid under appropriate specialization, constitutes a clear strength. The extension to inexact solvers and arbitrary decompositions broadens applicability to nonlinear PDEs, imaging, and data science.

minor comments (2)

The abstract asserts convergence under 'minimal assumptions'; the introduction or the statement of the main theorems should list the precise conditions (e.g., on the decomposition constant and local solver accuracy) so that readers can immediately verify the scope.
A dedicated subsection or corollary that recovers the classical block-coordinate-descent rate as a special case would strengthen the unification claim and make the dependence on the decomposition constant fully transparent.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation for minor revision. The summary accurately captures the contributions of the abstract framework for randomized subspace correction methods.

Circularity Check

0 steps flagged

No significant circularity in abstract framework or convergence analysis

full rationale

The paper develops an abstract framework for randomized subspace correction methods in convex optimization, deriving convergence rates from minimal assumptions on convexity, smoothness, and space decompositions. Central theorems explicitly track the finite decomposition constant and recover known rates for block coordinate descent, domain decomposition, and multigrid upon specialization, without any reduction of results to fitted parameters, self-definitions, or unverified self-citations by construction. The analysis is self-contained against standard convex optimization benchmarks and does not rely on load-bearing self-referential steps.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the framework appears to rest on standard domain assumptions for convex optimization and subspace decompositions without introducing new free parameters or invented entities.

axioms (1)

domain assumption Standard assumptions on convex optimization problems and space decompositions allow convergence analysis
Invoked to support the claimed analysis ranging from minimal assumptions to sharpness and strong convexity.

pith-pipeline@v0.9.0 · 5643 in / 1162 out tokens · 54289 ms · 2026-05-19T06:54:06.435199+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

abstract framework for randomized subspace correction methods for convex optimization, which unifies ... domain decomposition, multigrid, and block coordinate descent methods
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

convergence theorems ... under various conditions on the energy functional E ... sharpness and strong convexity

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

62 extracted references · 62 canonical work pages

[1]

Badea, Convergence rate of a Schwarz multilevel method for the constrained minimization of nonquadratic functionals , SIAM J

L. Badea, Convergence rate of a Schwarz multilevel method for the constrained minimization of nonquadratic functionals , SIAM J. Numer. Anal., 44 (2006), pp. 449–477

work page 2006
[2]

Badea and R

L. Badea and R. Krause , One-and two-level Schwarz methods for variational inequalities of the second kind and their application to frictional contact , Numer. Math., 120 (2012), pp. 573–599

work page 2012
[3]

Badea, X.-C

L. Badea, X.-C. Tai, and J. Wang , Convergence rate analysis of a multiplicative Schwarz method for variational inequalities , SIAM J. Numer. Anal., 41 (2003), pp. 1052–1073

work page 2003
[4]

H. H. Bauschke and P. L. Combettes , Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, New York, 2011

work page 2011
[5]

Beck, On the convergence of alternating minimization for convex programming with appli- cations to iteratively reweighted least squares and decomposition schemes, SIAM J

A. Beck, On the convergence of alternating minimization for convex programming with appli- cations to iteratively reweighted least squares and decomposition schemes, SIAM J. Optim., 25 (2015), pp. 185–209

work page 2015
[6]

Beck and L

A. Beck and L. Tetruashvili , On the convergence of block coordinate descent type methods , SIAM J. Optim., 23 (2013), pp. 2037–2060

work page 2013
[7]

D. P. Bertsekas , Incremental proximal methods for large scale convex optimization , Math. Program., 129 (2011), pp. 163–195

work page 2011
[8]

Bolte, A

J. Bolte, A. Daniilidis, and A. Lewis, The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems , SIAM J. Optim., 17 (2007), pp. 1205–1223

work page 2007
[9]

S. C. Brenner , An additive analysis of multiplicative Schwarz methods , Numer. Math., 123 (2013), pp. 1–19

work page 2013
[10]

Bueler and P

E. Bueler and P. E. Farrell , A full approximation scheme multilevel method for nonlinear variational inequalities, SIAM J. Sci. Comput., 46 (2024), pp. A2421–A2444

work page 2024
[11]

Carstensen, Domain decomposition for a non-smooth convex minimization problem and its application to plasticity , Numer

C. Carstensen, Domain decomposition for a non-smooth convex minimization problem and its application to plasticity , Numer. Linear Algebra Appl., 4 (1997), pp. 177–190

work page 1997
[12]

Chambolle and T

A. Chambolle and T. Pock , An introduction to continuous optimization for imaging , Acta Numer., 25 (2016), pp. 161–319

work page 2016
[13]

Chang, X.-C

H. Chang, X.-C. Tai, L.-L. Wang, and D. Yang , Convergence rate of overlapping domain decomposition methods for the Rudin–Osher–Fatemi model based on a dual formulation , SIAM J. Imaging Sci., 8 (2015), pp. 564–591

work page 2015
[14]

L. Chen, X. Hu, and S. Wise , Convergence analysis of the fast subspace descent method for convex optimization problems, Math. Comp., 89 (2020), pp. 2249–2282

work page 2020
[15]

Chorobura and I

F. Chorobura and I. Necoara , Random coordinate descent methods for nonseparable com- posite optimization, SIAM J. Optim., 33 (2023), pp. 2160–2190. 20 BOOU JIANG, JONGHO PARK, AND JINCHAO XU

work page 2023
[16]

C. D. Dang and G. Lan, Stochastic block mirror descent methods for nonsmooth and stochastic optimization, SIAM J. Optim., 25 (2015), pp. 856–881

work page 2015
[17]

Fercoq and P

O. Fercoq and P. Richt ´arik, Accelerated, parallel, and proximal coordinate descent, SIAM J. Optim., 25 (2015), pp. 1997–2023

work page 2015
[18]

T. Gao, S. Lu, J. Liu, and C. Chu , Randomized Bregman coordinate descent methods for non-Lipschitz optimization, arXiv preprint arXiv:2001.05202, (2020)

work page arXiv 2001
[19]

Griebel and P

M. Griebel and P. Oswald , Greedy and randomized versions of the multiplicative Schwarz method, Linear Algebra Appl., 437 (2012), pp. 1596–1610

work page 2012
[20]

Hinterm¨uller and A

M. Hinterm¨uller and A. Langer , Non-overlapping domain decomposition methods for dual total variation based image denoising , J. Sci. Comput., 62 (2015), pp. 456–481

work page 2015
[21]

M. Hong, X. Wang, M. Razaviyayn, and Z.-Q. Luo , Iteration complexity analysis of block coordinate descent methods, Math. Program., 163 (2017), pp. 85–114

work page 2017
[22]

X. Hu, J. Xu, and L. T. Zikatanov , Randomized and fault-tolerant method of subspace cor- rections, Res. Math. Sci., 6 (2019), pp. 1–15

work page 2019
[23]

Hua and N

X. Hua and N. Yamashita, Block coordinate proximal gradient methods with variable Bregman functions for nonsmooth separable optimization , Math. Program., 160 (2016), pp. 1–32

work page 2016
[24]

Jiang, J

B. Jiang, J. Park, and J. Xu , Connections between convex optimization algorithms and subspace correction methods, arXiv preprint arXiv:2505.09765, (2025)

work page arXiv 2025
[25]

Kunisch and M

K. Kunisch and M. Hinterm ¨uller, Total bounded variation regularization as a bilaterally constrained optimization problem, SIAM J. Appl. Math., 64 (2004), pp. 1311–1333

work page 2004
[26]

Lee and C

C.-O. Lee and C. Nam , Primal domain decomposition methods for the total variation mini- mization, based on dual decomposition, SIAM J. Sci. Comput., 39 (2017), pp. B403–B423

work page 2017
[27]

Lee, E.-H

C.-O. Lee, E.-H. Park, and J. Park , A finite element approach for the dual Rudin–Osher– Fatemi model and its nonoverlapping domain decomposition methods , SIAM J. Sci. Com- put., 41 (2019), pp. B205–B228

work page 2019
[28]

Lee and J

C.-O. Lee and J. Park, Fast nonoverlapping block Jacobi method for the dual Rudin–Osher– Fatemi model, SIAM J. Imaging Sci., 12 (2019), pp. 2009–2034

work page 2019
[29]

Lee and J

Y.-J. Lee and J. Park , On the linear convergence of additive Schwarz methods for the p- Laplacian, IMA J. Numer. Anal., (2024), p. drae068, https://doi.org/10.1093/imanum/ drae068

work page doi:10.1093/imanum/ 2024
[30]

Lee and J

Y.-J. Lee and J. Park, Subspace correction methods for semicoercive and nearly semicoercive convex optimization with applications to nonlinear PDEs, arXiv preprint arXiv:2412.17318, (2024)

work page arXiv 2024
[31]

Q. Lin, Z. Lu, and L. Xiao , An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization , SIAM J. Optim., 25 (2015), pp. 2244–2273

work page 2015
[32]

Lu and L

Z. Lu and L. Xiao, On the complexity analysis of randomized block-coordinate descent methods, Math. Program., 152 (2015), pp. 615–642

work page 2015
[33]

Necoara and D

I. Necoara and D. Clipici , Parallel random coordinate descent method for composite mini- mization: Convergence analysis and error bounds, SIAM J. Optim., 26 (2016), pp. 197–226

work page 2016
[34]

Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems , SIAM J

Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems , SIAM J. Optim., 22 (2012), pp. 341–362

work page 2012
[35]

Nesterov, Gradient methods for minimizing composite functions , Math

Y. Nesterov, Gradient methods for minimizing composite functions , Math. Program., 140 (2013), pp. 125–161

work page 2013
[36]

Nesterov, Universal gradient methods for convex optimization problems , Math

Y. Nesterov, Universal gradient methods for convex optimization problems , Math. Program., 152 (2015), pp. 381–404

work page 2015
[37]

Park, Additive Schwarz methods for convex optimization as gradient methods , SIAM J

J. Park, Additive Schwarz methods for convex optimization as gradient methods , SIAM J. Numer. Anal., 58 (2020), pp. 1495–1530

work page 2020
[38]

Park, Pseudo-linear convergence of an additive Schwarz method for dual total variation minimization, Electron

J. Park, Pseudo-linear convergence of an additive Schwarz method for dual total variation minimization, Electron. Trans. Numer. Anal., 54 (2021), pp. 176–197

work page 2021
[39]

Park, Fast gradient methods for uniformly convex and weakly smooth problems , Adv

J. Park, Fast gradient methods for uniformly convex and weakly smooth problems , Adv. Com- put. Math., 48 (2022), p. Paper No. 34

work page 2022
[40]

Park, Additive Schwarz methods for fourth-order variational inequalities , J

J. Park, Additive Schwarz methods for fourth-order variational inequalities , J. Sci. Comput., 101 (2024), p. Paper No. 74

work page 2024
[41]

Park, Additive Schwarz methods for semilinear elliptic problems with convex energy func- tionals: Convergence rate independent of nonlinearity , SIAM J

J. Park, Additive Schwarz methods for semilinear elliptic problems with convex energy func- tionals: Convergence rate independent of nonlinearity , SIAM J. Sci. Comput., 46 (2024), pp. A1373–A1396

work page 2024
[42]

Park, Two-level overlapping Schwarz preconditioners with universal coarse spaces for 2mth- order elliptic problems , SIAM J

J. Park, Two-level overlapping Schwarz preconditioners with universal coarse spaces for 2mth- order elliptic problems , SIAM J. Sci. Comput., 46 (2024), pp. A3681–A3702

work page 2024
[43]

Park and J

J. Park and J. Xu , Theory of parallel subspace correction methods for smooth convex op- timization. Submitted to Domain Decomposition Methods in Science and Engineering XXVIII. RANDOMIZED SUBSPACE CORRECTION METHODS 21

work page
[44]

Qu and P

Z. Qu and P. Richt ´arik, Coordinate descent with arbitrary sampling I: Algorithms and com- plexity, Optim. Methods Softw., 31 (2014), pp. 829–857

work page 2014
[45]

Razaviyayn, M

M. Razaviyayn, M. Hong, and Z.-Q. Luo, A unified convergence analysis of block successive minimization methods for nonsmooth optimization , SIAM J. Optim., 23 (2013), pp. 1126– 1153

work page 2013
[46]

Richt ´arik and M

P. Richt ´arik and M. Tak ´aˇc, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function , Math. Program., 144 (2014), pp. 1–38

work page 2014
[47]

Richt´arik and M

P. Richt´arik and M. Tak ´aˇc, Parallel coordinate descent methods for big data optimization , Math. Program., 156 (2016), pp. 433–484

work page 2016
[48]

Roulet and A

V. Roulet and A. d’Aspremont , Sharpness, restart, and acceleration , SIAM J. Optim., 30 (2020), pp. 262–289

work page 2020
[49]

Sun and M

R. Sun and M. Hong , Improved iteration complexity bounds of cyclic block coordinate de- scent for convex problems, in Advances in Neural Information Processing Systems, vol. 28, Curran Associates, Inc., 2015

work page 2015
[50]

Sun and Y

R. Sun and Y. Ye , Worst-case complexity of cyclic coordinate descent: O(n2) gap with ran- domized version, Math. Program., 185 (2021), pp. 487–520

work page 2021
[51]

Tai, Rate of convergence for some constraint decomposition methods for nonlinear vari- ational inequalities, Numer

X.-C. Tai, Rate of convergence for some constraint decomposition methods for nonlinear vari- ational inequalities, Numer. Math., 93 (2003), pp. 755–786

work page 2003
[52]

Tai and M

X.-C. Tai and M. Espedal , Rate of convergence of some space decomposition methods for linear and nonlinear problems , SIAM J. Numer. Anal., 35 (1998), pp. 1558–1570

work page 1998
[53]

Tai and J

X.-C. Tai and J. Xu, Global and uniform convergence of subspace correction methods for some convex optimization problems, Math. Comp., 71 (2002), pp. 105–124

work page 2002
[54]

Toselli and O

A. Toselli and O. Widlund , Domain Decomposition Methods-Algorithms and Theory , Springer, Berlin, 2005

work page 2005
[55]

Tseng, Convergence of a block coordinate descent method for nondifferentiable minimiza- tion, J

P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimiza- tion, J. Optim. Theory Appl., 109 (2001), pp. 475–494

work page 2001
[56]

S. J. Wright, Coordinate descent algorithms, Math. Program., 151 (2015), pp. 3–34

work page 2015
[57]

Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev., 34 (1992), pp

J. Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev., 34 (1992), pp. 581–613

work page 1992
[58]

Xu and L

J. Xu and L. Zikatanov , The method of alternating projections and the method of subspace corrections in Hilbert space, J. Amer. Math. Soc., 15 (2002), pp. 573–597

work page 2002
[59]

Xu and L

J. Xu and L. Zikatanov, Algebraic multigrid methods, Acta Numer., 26 (2017), pp. 591–721

work page 2017
[60]

Xu and W

Y. Xu and W. Yin, A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion , SIAM J. Imaging Sci., 6 (2013), pp. 1758–1789

work page 2013
[61]

J. Zeng, T. T.-K. Lau, S. Lin, and Y. Yao, Global convergence of block coordinate descent in deep learning, in Proceedings of the 36th International Conference on Machine Learning, vol. 97, PMLR, 2019, pp. 7313–7323

work page 2019
[62]

Zhang and M

Z. Zhang and M. Brand , Convergent block coordinate descent for training Tikhonov regular- ized deep neural networks, in Advances in Neural Information Processing Systems, vol. 30, Curran Associates, Inc., 2017

work page 2017

[1] [1]

Badea, Convergence rate of a Schwarz multilevel method for the constrained minimization of nonquadratic functionals , SIAM J

L. Badea, Convergence rate of a Schwarz multilevel method for the constrained minimization of nonquadratic functionals , SIAM J. Numer. Anal., 44 (2006), pp. 449–477

work page 2006

[2] [2]

Badea and R

L. Badea and R. Krause , One-and two-level Schwarz methods for variational inequalities of the second kind and their application to frictional contact , Numer. Math., 120 (2012), pp. 573–599

work page 2012

[3] [3]

Badea, X.-C

L. Badea, X.-C. Tai, and J. Wang , Convergence rate analysis of a multiplicative Schwarz method for variational inequalities , SIAM J. Numer. Anal., 41 (2003), pp. 1052–1073

work page 2003

[4] [4]

H. H. Bauschke and P. L. Combettes , Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, New York, 2011

work page 2011

[5] [5]

Beck, On the convergence of alternating minimization for convex programming with appli- cations to iteratively reweighted least squares and decomposition schemes, SIAM J

A. Beck, On the convergence of alternating minimization for convex programming with appli- cations to iteratively reweighted least squares and decomposition schemes, SIAM J. Optim., 25 (2015), pp. 185–209

work page 2015

[6] [6]

Beck and L

A. Beck and L. Tetruashvili , On the convergence of block coordinate descent type methods , SIAM J. Optim., 23 (2013), pp. 2037–2060

work page 2013

[7] [7]

D. P. Bertsekas , Incremental proximal methods for large scale convex optimization , Math. Program., 129 (2011), pp. 163–195

work page 2011

[8] [8]

Bolte, A

J. Bolte, A. Daniilidis, and A. Lewis, The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems , SIAM J. Optim., 17 (2007), pp. 1205–1223

work page 2007

[9] [9]

S. C. Brenner , An additive analysis of multiplicative Schwarz methods , Numer. Math., 123 (2013), pp. 1–19

work page 2013

[10] [10]

Bueler and P

E. Bueler and P. E. Farrell , A full approximation scheme multilevel method for nonlinear variational inequalities, SIAM J. Sci. Comput., 46 (2024), pp. A2421–A2444

work page 2024

[11] [11]

Carstensen, Domain decomposition for a non-smooth convex minimization problem and its application to plasticity , Numer

C. Carstensen, Domain decomposition for a non-smooth convex minimization problem and its application to plasticity , Numer. Linear Algebra Appl., 4 (1997), pp. 177–190

work page 1997

[12] [12]

Chambolle and T

A. Chambolle and T. Pock , An introduction to continuous optimization for imaging , Acta Numer., 25 (2016), pp. 161–319

work page 2016

[13] [13]

Chang, X.-C

H. Chang, X.-C. Tai, L.-L. Wang, and D. Yang , Convergence rate of overlapping domain decomposition methods for the Rudin–Osher–Fatemi model based on a dual formulation , SIAM J. Imaging Sci., 8 (2015), pp. 564–591

work page 2015

[14] [14]

L. Chen, X. Hu, and S. Wise , Convergence analysis of the fast subspace descent method for convex optimization problems, Math. Comp., 89 (2020), pp. 2249–2282

work page 2020

[15] [15]

Chorobura and I

F. Chorobura and I. Necoara , Random coordinate descent methods for nonseparable com- posite optimization, SIAM J. Optim., 33 (2023), pp. 2160–2190. 20 BOOU JIANG, JONGHO PARK, AND JINCHAO XU

work page 2023

[16] [16]

C. D. Dang and G. Lan, Stochastic block mirror descent methods for nonsmooth and stochastic optimization, SIAM J. Optim., 25 (2015), pp. 856–881

work page 2015

[17] [17]

Fercoq and P

O. Fercoq and P. Richt ´arik, Accelerated, parallel, and proximal coordinate descent, SIAM J. Optim., 25 (2015), pp. 1997–2023

work page 2015

[18] [18]

T. Gao, S. Lu, J. Liu, and C. Chu , Randomized Bregman coordinate descent methods for non-Lipschitz optimization, arXiv preprint arXiv:2001.05202, (2020)

work page arXiv 2001

[19] [19]

Griebel and P

M. Griebel and P. Oswald , Greedy and randomized versions of the multiplicative Schwarz method, Linear Algebra Appl., 437 (2012), pp. 1596–1610

work page 2012

[20] [20]

Hinterm¨uller and A

M. Hinterm¨uller and A. Langer , Non-overlapping domain decomposition methods for dual total variation based image denoising , J. Sci. Comput., 62 (2015), pp. 456–481

work page 2015

[21] [21]

M. Hong, X. Wang, M. Razaviyayn, and Z.-Q. Luo , Iteration complexity analysis of block coordinate descent methods, Math. Program., 163 (2017), pp. 85–114

work page 2017

[22] [22]

X. Hu, J. Xu, and L. T. Zikatanov , Randomized and fault-tolerant method of subspace cor- rections, Res. Math. Sci., 6 (2019), pp. 1–15

work page 2019

[23] [23]

Hua and N

X. Hua and N. Yamashita, Block coordinate proximal gradient methods with variable Bregman functions for nonsmooth separable optimization , Math. Program., 160 (2016), pp. 1–32

work page 2016

[24] [24]

Jiang, J

B. Jiang, J. Park, and J. Xu , Connections between convex optimization algorithms and subspace correction methods, arXiv preprint arXiv:2505.09765, (2025)

work page arXiv 2025

[25] [25]

Kunisch and M

K. Kunisch and M. Hinterm ¨uller, Total bounded variation regularization as a bilaterally constrained optimization problem, SIAM J. Appl. Math., 64 (2004), pp. 1311–1333

work page 2004

[26] [26]

Lee and C

C.-O. Lee and C. Nam , Primal domain decomposition methods for the total variation mini- mization, based on dual decomposition, SIAM J. Sci. Comput., 39 (2017), pp. B403–B423

work page 2017

[27] [27]

Lee, E.-H

C.-O. Lee, E.-H. Park, and J. Park , A finite element approach for the dual Rudin–Osher– Fatemi model and its nonoverlapping domain decomposition methods , SIAM J. Sci. Com- put., 41 (2019), pp. B205–B228

work page 2019

[28] [28]

Lee and J

C.-O. Lee and J. Park, Fast nonoverlapping block Jacobi method for the dual Rudin–Osher– Fatemi model, SIAM J. Imaging Sci., 12 (2019), pp. 2009–2034

work page 2019

[29] [29]

Lee and J

Y.-J. Lee and J. Park , On the linear convergence of additive Schwarz methods for the p- Laplacian, IMA J. Numer. Anal., (2024), p. drae068, https://doi.org/10.1093/imanum/ drae068

work page doi:10.1093/imanum/ 2024

[30] [30]

Lee and J

Y.-J. Lee and J. Park, Subspace correction methods for semicoercive and nearly semicoercive convex optimization with applications to nonlinear PDEs, arXiv preprint arXiv:2412.17318, (2024)

work page arXiv 2024

[31] [31]

Q. Lin, Z. Lu, and L. Xiao , An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization , SIAM J. Optim., 25 (2015), pp. 2244–2273

work page 2015

[32] [32]

Lu and L

Z. Lu and L. Xiao, On the complexity analysis of randomized block-coordinate descent methods, Math. Program., 152 (2015), pp. 615–642

work page 2015

[33] [33]

Necoara and D

I. Necoara and D. Clipici , Parallel random coordinate descent method for composite mini- mization: Convergence analysis and error bounds, SIAM J. Optim., 26 (2016), pp. 197–226

work page 2016

[34] [34]

Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems , SIAM J

Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems , SIAM J. Optim., 22 (2012), pp. 341–362

work page 2012

[35] [35]

Nesterov, Gradient methods for minimizing composite functions , Math

Y. Nesterov, Gradient methods for minimizing composite functions , Math. Program., 140 (2013), pp. 125–161

work page 2013

[36] [36]

Nesterov, Universal gradient methods for convex optimization problems , Math

Y. Nesterov, Universal gradient methods for convex optimization problems , Math. Program., 152 (2015), pp. 381–404

work page 2015

[37] [37]

Park, Additive Schwarz methods for convex optimization as gradient methods , SIAM J

J. Park, Additive Schwarz methods for convex optimization as gradient methods , SIAM J. Numer. Anal., 58 (2020), pp. 1495–1530

work page 2020

[38] [38]

Park, Pseudo-linear convergence of an additive Schwarz method for dual total variation minimization, Electron

J. Park, Pseudo-linear convergence of an additive Schwarz method for dual total variation minimization, Electron. Trans. Numer. Anal., 54 (2021), pp. 176–197

work page 2021

[39] [39]

Park, Fast gradient methods for uniformly convex and weakly smooth problems , Adv

J. Park, Fast gradient methods for uniformly convex and weakly smooth problems , Adv. Com- put. Math., 48 (2022), p. Paper No. 34

work page 2022

[40] [40]

Park, Additive Schwarz methods for fourth-order variational inequalities , J

J. Park, Additive Schwarz methods for fourth-order variational inequalities , J. Sci. Comput., 101 (2024), p. Paper No. 74

work page 2024

[41] [41]

Park, Additive Schwarz methods for semilinear elliptic problems with convex energy func- tionals: Convergence rate independent of nonlinearity , SIAM J

J. Park, Additive Schwarz methods for semilinear elliptic problems with convex energy func- tionals: Convergence rate independent of nonlinearity , SIAM J. Sci. Comput., 46 (2024), pp. A1373–A1396

work page 2024

[42] [42]

Park, Two-level overlapping Schwarz preconditioners with universal coarse spaces for 2mth- order elliptic problems , SIAM J

J. Park, Two-level overlapping Schwarz preconditioners with universal coarse spaces for 2mth- order elliptic problems , SIAM J. Sci. Comput., 46 (2024), pp. A3681–A3702

work page 2024

[43] [43]

Park and J

J. Park and J. Xu , Theory of parallel subspace correction methods for smooth convex op- timization. Submitted to Domain Decomposition Methods in Science and Engineering XXVIII. RANDOMIZED SUBSPACE CORRECTION METHODS 21

work page

[44] [44]

Qu and P

Z. Qu and P. Richt ´arik, Coordinate descent with arbitrary sampling I: Algorithms and com- plexity, Optim. Methods Softw., 31 (2014), pp. 829–857

work page 2014

[45] [45]

Razaviyayn, M

M. Razaviyayn, M. Hong, and Z.-Q. Luo, A unified convergence analysis of block successive minimization methods for nonsmooth optimization , SIAM J. Optim., 23 (2013), pp. 1126– 1153

work page 2013

[46] [46]

Richt ´arik and M

P. Richt ´arik and M. Tak ´aˇc, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function , Math. Program., 144 (2014), pp. 1–38

work page 2014

[47] [47]

Richt´arik and M

P. Richt´arik and M. Tak ´aˇc, Parallel coordinate descent methods for big data optimization , Math. Program., 156 (2016), pp. 433–484

work page 2016

[48] [48]

Roulet and A

V. Roulet and A. d’Aspremont , Sharpness, restart, and acceleration , SIAM J. Optim., 30 (2020), pp. 262–289

work page 2020

[49] [49]

Sun and M

R. Sun and M. Hong , Improved iteration complexity bounds of cyclic block coordinate de- scent for convex problems, in Advances in Neural Information Processing Systems, vol. 28, Curran Associates, Inc., 2015

work page 2015

[50] [50]

Sun and Y

R. Sun and Y. Ye , Worst-case complexity of cyclic coordinate descent: O(n2) gap with ran- domized version, Math. Program., 185 (2021), pp. 487–520

work page 2021

[51] [51]

Tai, Rate of convergence for some constraint decomposition methods for nonlinear vari- ational inequalities, Numer

X.-C. Tai, Rate of convergence for some constraint decomposition methods for nonlinear vari- ational inequalities, Numer. Math., 93 (2003), pp. 755–786

work page 2003

[52] [52]

Tai and M

X.-C. Tai and M. Espedal , Rate of convergence of some space decomposition methods for linear and nonlinear problems , SIAM J. Numer. Anal., 35 (1998), pp. 1558–1570

work page 1998

[53] [53]

Tai and J

X.-C. Tai and J. Xu, Global and uniform convergence of subspace correction methods for some convex optimization problems, Math. Comp., 71 (2002), pp. 105–124

work page 2002

[54] [54]

Toselli and O

A. Toselli and O. Widlund , Domain Decomposition Methods-Algorithms and Theory , Springer, Berlin, 2005

work page 2005

[55] [55]

Tseng, Convergence of a block coordinate descent method for nondifferentiable minimiza- tion, J

P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimiza- tion, J. Optim. Theory Appl., 109 (2001), pp. 475–494

work page 2001

[56] [56]

S. J. Wright, Coordinate descent algorithms, Math. Program., 151 (2015), pp. 3–34

work page 2015

[57] [57]

Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev., 34 (1992), pp

J. Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev., 34 (1992), pp. 581–613

work page 1992

[58] [58]

Xu and L

J. Xu and L. Zikatanov , The method of alternating projections and the method of subspace corrections in Hilbert space, J. Amer. Math. Soc., 15 (2002), pp. 573–597

work page 2002

[59] [59]

Xu and L

J. Xu and L. Zikatanov, Algebraic multigrid methods, Acta Numer., 26 (2017), pp. 591–721

work page 2017

[60] [60]

Xu and W

Y. Xu and W. Yin, A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion , SIAM J. Imaging Sci., 6 (2013), pp. 1758–1789

work page 2013

[61] [61]

J. Zeng, T. T.-K. Lau, S. Lin, and Y. Yao, Global convergence of block coordinate descent in deep learning, in Proceedings of the 36th International Conference on Machine Learning, vol. 97, PMLR, 2019, pp. 7313–7323

work page 2019

[62] [62]

Zhang and M

Z. Zhang and M. Brand , Convergent block coordinate descent for training Tikhonov regular- ized deep neural networks, in Advances in Neural Information Processing Systems, vol. 30, Curran Associates, Inc., 2017

work page 2017