Global Convergence of Block Coordinate Descent in Deep Learning

1. Introduction

• BCD can remain effective where vanilla SGD fails on a ten-hidden-layer MLP, achieving moderate accuracy within a few epochs on MNIST.The comparison is attributed to SGD’s vanishing-gradient issue in this deep-network setting.Source: §1 · p. 1, Figure 1 · p. 2
• Global convergence theory for DNN BCD is limited, motivating a general methodology that covers common two- and three-splitting training models.The gap arises because DNN training is highly nonconvex, while earlier analyses rely on block multiconvexity or differentiability assumptions that may fail for common activations.Source: §1 · p. 2
• Under assumptions covering common losses, activations, and regularizers, BCD converges globally to a critical point at O(1/k) from any finite initialization.The stated examples include squared, logistic, hinge, exponential, and cross-entropy losses; ReLU, leaky ReLU, sigmoid, tanh, linear, polynomial, and softplus activations; and several standard regularizers.Source: §1 · p. 2
• The analysis extends to prox-linear strategies for general smooth losses and to residual networks, while retaining the stated convergence framework.The paper also presents the BCD algorithms and discusses the organization of the convergence and extension results.Source: §1 · pp. 2–3
• The KŁ framework is combined with proximal updates, activation Lipschitz continuity, and lower semicontinuity to establish sufficient descent, relative error, and continuity conditions.This avoids requiring block multiconvexity and differentiability of the unregularized objective component.Source: §1 · p. 2

2.1. DNN training with variable splitting

• Variable splitting transforms highly nonlinear coupling in DNN training into a formulation with more loosely coupled variables, improving computational tractability.The approach introduces auxiliary variables to separate interactions induced by the deep architecture.Source: §2.1 · p. 3, §2 · p. 3

2.1.1. TWO-SPLITTING FORMULATION.

• The two-splitting formulation couples state variables directly through Vi = σi(WiVi−1) and accommodates broad losses, activations, regularizers, and constraints.Its scope includes common activations such as ReLU, leaky ReLU, sigmoid, linear, polynomial, and softplus, along with standard regularization and convex-set constraints.Source: §2.1.1 · p. 3

2.1.2. THREE-SPLITTING FORMULATION.

• The three-splitting formulation introduces Ui through Ui = WiVi−1 and Vi = σi(Ui), loosening the coupling between Wi and Vi−1 at the cost of additional auxiliary variables.This structure can benefit efficient method design, although it requires extra storage.Source: §2.1.2 · p. 4, §2.2 · p. 4

2.2. Description of BCD algorithms

• BCD updates variables cyclically in backward layer order, using {Vi, Wi} for two-splitting and {Vi, Ui, Wi} for three-splitting models.The output layer receives special treatment because σN is the identity.Source: §2.2 · p. 4
• Proximal updates are used for most blocks to stabilize training and obtain the sufficient-descent property required for theoretical justification.Many three-splitting subproblems reduce to proximal updates or least-squares problems with closed-form solutions, while the formulation requires more memory.Source: §2.2 · p. 4
• The algorithms cover practical cases with closed-form or efficiently solvable subproblems, including common regularizers, simple convex constraints, losses, and activation functions.The paper specifically identifies squared and hinge losses, ReLU, leaky ReLU, and linear link functions among cases with simple updates.Source: §2.1.1 · p. 3, §2.2 · pp. 4–5

3. Global convergence analysis of BCD

• The global-convergence analysis covers both two-splitting and three-splitting BCD formulations for DNN training.The paper presents separate algorithms for the corresponding formulations before proving their convergence and extensions.Source: §3 · p. 5, §3.3 · p. 6

3.1. Main assumptions

• The analysis assumes lower semicontinuity, bounded-set Lipschitz continuity of activations, nonnegative regularizers, and real-analytic or semialgebraic continuous model components.The paper states that most commonly used DNN training models satisfy these assumptions.Source: Definition 2 (Semialgebraic) · p. 5

Definition 2 (Semialgebraic)

• The paper reports that common losses, activations, and regularizers—including logistic or cross-entropy losses, ReLU or softplus activations, and standard norms—can satisfy the assumptions.Examples include squared and logistic losses, linear or polynomial activations, and elastic-net or convex-set regularizers.Source: Definition 2 (Semialgebraic) · p. 6

3.2. Main theorem

• Under Assumption 1 and a convergent subsequence or coercivity condition, BCD sequences converge to critical points of the training objectives.The result applies for any positive proximal parameters and finite initialization.Source: §3.2 · p. 6
• The main theorem establishes convergence to a critical point with an O(1/k) rate without block multiconvexity or Lipschitz differentiability assumptions.These assumptions are often violated by DNN objectives with nonlinear, especially ReLU, activations.Source: §3.2 · p. 6

3.3.1. EXTENSION TO PROX-LINEAR

• For smooth losses with Lipschitz continuous gradients, prox-linear VN-updates retain all claims of the main theorem when the step parameter satisfies the stated bound.The strategy supports nonlinear losses such as logistic and cross-entropy losses and permits easily implemented updates for large-scale distributed computations.Source: §3.3.1 · p. 6

3.3.2. EXTENSION TO RESNET TRAINING

• The BCD convergence guarantees extend to ResNet training by replacing the objective with Lres, including the prox-linear case under Theorem 2's assumptions.Because ReLU is typically used in ResNets, the paper considers their three-splitting formulation.Source: §3.3.2 · p. 7

4.1. Main ideas of proofs

• Proximal strategies for non-strongly convex subproblems establish sufficient descent without multiconvexity, differentiability, or blockwise Lipschitz differentiability assumptions.The resulting Lagrangian sequence decreases, while iterate discrepancies control the descent.Source: §4.1 · p. 7, §4.2 · p. 8

4.2. Sufficient descent lemma

• The sufficient descent lemma yields boundedness under coercivity, square-summable iterate differences, asymptotic regularity, and an O(1/K) rate for averaged discrepancies.It also ensures convergence of objective values when the Lagrangian is lower bounded.Source: §4.2 · p. 8
• Combining sufficient descent with the KŁ framework establishes global convergence of the whole BCD sequence to a critical point.This is stronger than the subsequence convergence established for SGD in the cited comparison.Source: §4.2 · p. 8, §4.1 · p. 8

4.3. Relative error lemma

• The relative error lemma bounds the Lagrangian subgradient by consecutive-iterate discrepancy, yielding critical-point convergence and an O(1/K) rate.The proof uses Lipschitz continuity of activations on bounded sets and special treatments of BCD updates, rather than differentiability assumptions.Source: §4.3 · p. 8

5. Conclusion

• The theory covers a class of DNN training models encompassing most commonly used BCD methods and several variable-splitting schemes.Its scope includes extensions to residual networks and general losses with Lipschitz continuous gradients.Source: §5 · p. 8
• O(1/k) convergence to a critical point is established under mild assumptions for the covered DNN training models.Here, k denotes the number of iterations.Source: §5 · p. 8
• The results provide a theoretical foundation for applying BCD methods to deep learning within the stated model and assumption scope.Source: §5 · p. 8

A. Implementations on BCD methods

• Weights are typically initialized from small-variance Gaussian distributions, biases from small scaled constants, and auxiliary variables through one forward pass.Source: A. Implementations on BCD methods · p. 12
• Any arbitrary deterministic BCD update order can be used in the proofs, although a backward order is suggested for DNNs' nested structure.Source: A. Implementations on BCD methods · p. 12
• Distributed implementations partition data across servers and split state and auxiliary variables by sample columns.The V_i updates require no communication and can run in parallel, whereas W_i updates are harder to parallelize.Source: A. Implementations on BCD methods · p. 12

B. Proof of Proposition 1

• Squared and exponential losses, logistic loss, cross-entropy, and common analytic activation functions satisfy the real-analytic or semialgebraic requirements used in Proposition 1.The appendix specifically verifies analytic structure for sigmoid, hyperbolic tangent, polynomial functions, and the listed losses.Source: B. Proof of Proposition 1 · p. 12
• ReLU and leaky ReLU are shown to be semialgebraic, allowing these nondifferentiable activations within the KŁ-based analysis.Source: B. Proof of Proposition 1 · p. 13
• The appendix verifies that squared Frobenius norms, elementwise 1-norms, elastic-net regularizers, and polyhedral indicator functions meet the required semialgebraic conditions.Source: B. Proof of Proposition 1 · p. 13

C. Proof of Theorem 1

• The proof of Theorem 1 proceeds from the KŁ property to function-value convergence and then whole-sequence convergence at O(1/k) to a critical point.These ingredients are combined through the cited intermediate propositions and theorems.Source: C. Proof of Theorem 1 · p. 13

• The KŁ framework characterizes functions through a desingularizing reparametrization that restores sharpness near critical points.The paper defines the KŁ inequality using a concave function ϕ(s) = cs^(1−θ), with θ as the KŁ exponent.Source: §C.1 · p. 14
• The KŁ result applies to the deep-learning objectives L in both cited variable-splitting formulations, after vectorizing matrix variables for the standard definitions.The paper notes that the matrix notation is retained for simplicity even though the KŁ, real-analytic, and semialgebraic definitions are applied to vectorized variables.Source: §C.1 · p. 14
• The variable-splitting objectives are KŁ functions on closed sets under the stated assumptions.The proof uses real-analytic and semialgebraic closure properties to show subanalyticity and then applies continuity on the domain.Source: §C.1 · pp. 14–16
• Real-analytic and semialgebraic components remain tractable under the sums, products, compositions, and indicator constructions appearing in the objectives.These closure properties make the network loss, residual terms, and regularizers subanalytic when their constituent functions satisfy the assumptions.Source: §C.1 · pp. 14–15

• The objective sequences generated by both algorithms are nonincreasing and converge to finite limits.The objective is lower bounded because its terms are nonnegative, while the block updates establish descent estimates.Source: §C.2 · pp. 16, 18
• Sufficient descent is established by summing descent contributions from each block update.The updates use proximal strategies or minimization of strongly convex subproblems, with a prox-linear treatment for the final block where applicable.Source: §C.2 · pp. 16–17
• The same value-convergence claims extend across proximal and prox-linear updates for the relevant final block.The proof separately identifies the proximal and prox-linear cases and uses the corresponding strong-convexity or Lipschitz-gradient conditions.Source: §C.2 · pp. 16–18
• The corollary establishes square summability of successive differences, which directly implies ∥Pk −Pk−1∥F →0 as k →∞.Source: §C.2 · p. 18

C.3. Global convergence of BCD

• Under Theorem 5, the BCD sequences converge to critical points of their objectives.The analysis targets global convergence from finite initialization and uses the KŁ framework together with descent and relative-error conditions.Source: §C.3 · pp. 18–19
• If initialized sufficiently close to a global minimum, the generated sequence converges to that global minimum.This is a local initialization condition, not a claim that arbitrary initialization reaches a global minimum.Source: §C.3 · p. 18
• The KŁ exponent determines the rate regime, ranging from finite-step convergence at θ = 0 to linear or sublinear convergence for larger exponents.The supplied theorem statements specify geometric decay for the intermediate regime and a power-law bound for θ in (1/2, 1).Source: §C.3 · p. 18
• The convergence argument requires sufficient decrease, relative error, continuity, and KŁ behavior on a closed bounded set containing the limiting points.Boundedness and coercivity allow the KŁ property to be restricted to such a set rather than the entire real-valued domain.Source: §C.3 · p. 19, §C.3.1 · p. 19

C.3.1. ESTABLISHING RELATIVE ERROR CONDITION

• The proof’s relative-error condition bounds subgradient size by successive-iterate differences using boundedness and Lipschitz continuity of activations.For the prox-linear case, the bound also incorporates the Lipschitz constant of the loss gradient.Source: §C.3.1 · pp. 19–20

C.3.3. CONDITION (B) OR (C) IMPLIES CONDITION (A)

• Under either local initialization near a reference point or coercivity, the iterate sequence is bounded and therefore has a convergent subsequence.For the local case, the iterates remain in a prescribed neighborhood; for the coercive case, bounded objective values imply bounded iterates.Source: §C.3.2 · p. 20, §C.3.3 · pp. 22–23

C.3.2. PROOF OF THEOREM 5 UNDER CONDITION (A)

• Theorem 5’s proof uses the KŁ inequality with descent and relative-error bounds to keep iterates in a neighborhood and prove whole-sequence convergence.The argument handles both the case where the objective reaches its limiting value and the case where it approaches that value strictly from above.Source: §C.3.2 · p. 22
• Every limit point is critical because successive differences vanish and the relative-error bound controls the limiting subgradient.This connects the value-convergence results to the criticality conclusion in Theorem 5.Source: §C.3.2 · p. 22
• The O(1/k) convergence rate follows directly from the descent and square-summability estimates.The proof states that the rate is obtained from Lemma 8 and Corollary 1(c).Source: §C.3.2 · p. 22

C.3.3. CONDITION (B) OR (C) IMPLIES CONDITION (A)

• The boundedness proof under the local or coercive conditions supplies condition (A), completing the route to global convergence.The argument recursively bounds network variables under condition (b), while condition (c) uses coercivity of the objective.Source: §C.3.3 · pp. 22–23

D. Proof of Theorem 3

• For ResNets, Lemma 7 is retained with L replaced by Lres, while Lemma 8 is revised under Theorem 3’s assumptions.The revised bound uses α, γ, L, and the sequence-bound parameter B.Source: D. Proof of Theorem 3 · pp. 23–24
• Theorem 3 follows from the KŁ property of Lres, Lemmas 11–12, and the Attouch et al. (2013, Theorem 2.9) convergence result.The same argument applies when the prox-linear strategy is used for the VN-update.Source: D. Proof of Theorem 3 · p. 25

E.1. Closed form solution to ReLU-subproblem

• The ReLU subproblem reduces to a one-dimensional minimization whose optimizer is obtained by four sign cases involving a + γb and b.The resulting solution is summarized in Lemma 13.Source: §E.1 · pp. 25–26

E.2. The closed form of the proximal operator of hinge loss

• The hinge-loss proximal operator is solved by partitioning according to the sign of a and comparing b with thresholds involving a^-1 and γ^-1a.Lemma 14 gives the resulting piecewise optimizer.Source: §E.2 · pp. 26–27

F. BCD vs. SGD for training ten-hidden-layer MLPs

• The benchmark uses MNIST with a 784-(600×10)-10 ReLU MLP, squared loss, and ten hidden layers.BCD uses γ = α = 1, with 60,000 training samples and 10,000 test samples.Source: F. BCD vs. SGD for training… · p. 27
• SGD also shows similar training failure at learning rates 0.01 and 0.05, despite the baseline rate of 0.001 being chosen conservatively.Thus, the observed failure is not limited to the conservative learning-rate setting.Source: F. BCD vs. SGD for training… · p. 27
• Both algorithms use mini-batches of 512 and the same initializations for a controlled comparison.Weights use Gaussian initialization, biases are initialized to 0.1, and auxiliary variables use a single forward pass.Source: F. BCD vs. SGD for training… · p. 27
• BCD achieves moderate accuracy within a few epochs, while vanilla SGD usually fails to train the ten-hidden-layer MLP because of vanishing gradients.The comparison uses training and test accuracy curves in Figure 1.Source: F. BCD vs. SGD for training… · p. 27