Block Coordinate Descent for Neural Networks Provably Finds Global Minima
Authors: Shunta Akiyama
Venue: NeurIPS 2025 poster ()
Keywords: Deep learning theory
block coordinate descent
global convergence
generalization error analysis
Primary area: theory
TL;DR: This paper proves that a block coordinate descent algorithm can train deep neural networks to global minima under certain activation functions, extending to ReLU via architectural modifications.

Abstract: In this paper, we consider a block coordinate descent (BCD) algorithm for training deep neural networks and provide a new global convergence guarantee under strictly monotonically increasing activation functions. While existing works demonstrate convergence to stationary points for BCD in neural networks, our contribution is the first to prove convergence to global minima, ensuring arbitrarily small loss. We show that the loss with respect to the output layer decreases exponentially while the loss with respect to the hidden layers remains well-controlled. Additionally, we derive generalization bounds using the Rademacher complexity framework, demonstrating that BCD not only achieves strong optimization guarantees but also provides favorable generalization performance. Moreover, we propose a modified BCD algorithm with skip connections and non-negative projection, extending our convergence guarantees to ReLU activation, which are not strictly monotonic. Empirical experiments confirm our theoretical findings, showing that the BCD algorithm achieves a small loss for strictly monotonic and ReLU activations.

Block Coordinate Descent for Neural Networks Provably Finds Global Minima
Shunta Akiyama
CyberAgent yama aklyyma__huutaecylben wwwttaccyoraaeenttcoom co.
Abstract
In this paper, consider block coordinate descent (BCD) algorithm for training deep neural networks and provide new global convergence guarantee under strictly monotonically increasing activation functions. While existing works demonstrate convergence to stationary points for BCD in neural networks, our contribution is the first prove convergence global minima, ensuring arbitrarily small loss. We show that the loss with respect to the output layer decreases exponentially while the loss with respect to the hidden layers remains well-controlled. Additionally, we derive generalization bounds using the Rademacher complexity framework, demonstrating that BCD not only achieves strong optimization guarantees but also provides favorable generalization performance. Moreover, propose modified BCD algorithm with skip connections and non-negative projection, extending our convergence guarantees to ReLU activation, which are not strictly monotonic. Empirical experiments confirm our theoretical findings, showing that the BCD algorithm achieves small loss for strictly monotonic and ReLU activations.
Introduction
Deep learning has driven remarkable progress across wide range of fields, including computer vision, natural language processing, and reinforcement learning. achieving state-of-the-art results on numerous tasks. Despite these empirical successes, the theoretical understanding of the training dynamics and optimization behavior of deep neural networks remains elusive, primarily due to the [20). A central open problem is the establishment of convergence guarantees to global minima for gradient descent algorithms, particularly those implemented through backpropagation in deep architectures comprising multiple layers. The neural tangent kernel (NTK) framework 17 has provided partial theoretical insights by approximating the training dynamics by linearized within reproducing kernel Hilbert space (RKHS). However, this linearized perspective does not fully capture the empirical efficacy of deep learning models. In practice, deep learning often surpasses the performance kernel methods, including those based on NTK, suggesting that the NTK regime captures only limited aspect of optimization capabilities.
highly non-convex structure of their loss landscapes
As alternative to backpropagation- based gradient methods, block coordinate descent (BCD), framework rooted in mathematical optimization (see, e.g., (34)), optimizes partitioned variable blocks iteratively while holding others fixed, offering computational efficiency through partial parameter updates. Its structure also supports parallel and distributed implementations [0 21,. making well-suited for large-scale neural network training.
Given the highly non-convex nature of neural network loss landscapes, BCD-based approaches have emerged promising alternatives conventional gradient-based approaches [ 6
19
43 29 41
24 42 38). widely adopted strategy in this setting is to partition the network parameters by layer, treating the weights of each layer as individual blocks, allowing for sequential or alternating updates, as illustrated in Figure]] I This layer-wise decomposition enables the reformulation of the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

W
22
W3
W1
W
W3
Update by backpropagation
V1,i
V2,5
Auxiliary parameter
Update by block coordinate descent
Figure I: Graphical comparison between backpropagation and block coordinate descent. In contrast, the block coordinate descent approach introduces auxiliary variables Vi which serve as approxima- tions of the hidden layer outputs, enabling layer-wise updates and a decoupled optimization structure (see Section 4 for details).
original global loss into a series of sub-objectives, each localized to a specific layer. These sub- problems typically exhibit more tractable optimization properties compared the full loss function, thereby facilitating more efficient and stable training dynamics.
Building the practical advantages of block coordinate descent (BCD) in neural network training, recent research has increasingly examined its theoretical properties, particularly its convergence has been limited
behavior. However, the current literature BCD for neural networks 43 41 42 38
to establishing convergence to stationary points, that is, points where the gradient vanishes. While such results of theoretical interest, they do not ensure convergence global optima, particularly in light of the highly non-convex loss landscapes intrinsic to deep neural networks [20 32).
Understanding how neural network training can achieve global minima has emerged central problem in the theoretical study of deep learning. Although BCD offers promising alternative to gradient-basee based methods, existing guarantees have not addressed this critical aspect, remaining confined to local convergence results. To address this gap, we aim to establish convergence guarantees global minima for BCD applied to neural network training. Specifically, neural networks and analyze a BCD-type algorithm in which each block update is performed via standard (vanilla) gradient descent. Our main contributions summarized as follows:
consider multi-layer
We establish global convergence guarantee for block coordinate descent (BCD) algorithm applied to the training of deep neural networks with strictly monotonically increasing activation functions. To the best of our knowledge, this is the first theoretical result that ensures convergence to global minima deep neural networks with an arbitrary number of layers, without relying assumptions associated with the neural tangent kernel (NTK) regime.
Under the assumption that the training data are i.i.d., we derive generalization bounds for networks trained via BCD. cornerstone of our analysis the boundedness of the weight matrices at each layer-a property we establish as direct consequence of the convergence proof. Leveraging this boundedness together with the Rademacher complexity framework introduced by [8). we derive upper bounds on the generalization gap.
Since ReLU does not satisfy the monotonicity condition required by our initial analysis. the corresponding convergence results are not directly applicable. To address this issue, we propose a modified BCD algorithm that integrates skip connections (16] and non-negative projection steps. This augmentation enables us extend our global convergence guarantees to networks employing ReLU activations, thereby broadening the practical relevance and applicability of our theoretical contributions.

---

2 Related Work
Convergence Guarantees for Gradient Descent and Stochastic Gradient Descent in Neural Networks The convergence properties of gradient descent (GD) and stochastic gradient descent (SGD) in the context of neural network training have been the subject of extensive theoretical investigation in recent years, A prominent line of research focuses on the neural tangent kernel (NTK) regime [17 13 [4), wherein the training dynamics of highly overparameterized neural networks are approximated by linear models in a reproducing kernel Hilbert space (RKHS). While this framework facilitates global convergence analysis via convexity, fails to capture the feature learning capability of neural networks. In particular. models trained under the NTK regime often exhibit minimal parameter movement from their initialization, thereby behaving more like kernel methods than adaptive learners. In contrast, our analysis operates outside of this kerne--base setting and does not rely on such overparameterizatioo assumptions to ensure global convergence.
An alternative theoretical framework is the mean-field (MF) regime 22
35 30 277, which
interprets training dynamics the evolution of probability measures over the parameter space. This formulation enables the conversion of the original non-convex optimization problem into a convex optimization over probability distributions. While the MF regime avoids the limitations of the NTK approach by preserving feature learning behavior and allowing global convergence analysis, most existing results are restricted shallow architectures, typically two or three layers. In contrast, our work provides global convergence guarantees for neural networks with an arbitrary number of hidden layers.
More recently, introduced the concept of restricted strong convexity (RSC) to analyze neural network training. This framework derives global convergence by assuming correlation between the gradients and outputs of neural networks throughout training. However, the validity and general applicability of this correlation assumption remain be fully established.
Generalization Error Bounds for Multi-Layer Neural Networks The study of generalization
properties in deep neural networks has also seen considerable progress [26] 33 8 25 15
9 5 33)
These works develop upper bounds on generalization error by evaluating the capacity of neural networks using various complexity measures, such VC-dimension, norms of weight matrices, and spectral properties. However, most of these studies focus solely on capacity control and do not address the optimization dynamics during training. While some recent studies have extended generalization analysis to networks with more than two layers with global convergence guarantees, many remain constrained to three-layer architectures [ 2]
3 Preliminaries
3.1 Notations
For E RRd, ||>||| denotes its Euclidean norm. We denote the d-dimensional identity matrix by Ia. For A E R= the Frobenius norm is defined as ||A||r = /E.,, Alj. and the operator norm is defined as || = sup ||Ar|]. For two symmetric matrices A and B, we write A < B (A = B3) if and only |-] s1
the matrix B A is positive (non-negative) definite. For x = (# =a) E Rdd diag(x) e dddd denotes diagonal matrix whose j-th diagonal entry is zj. We denote minfa, b) a A.
3.2 Problem Settings
We consider supervised learning setup where we are given n training examples D {(1i, yi)) 1=1> with input vectors I, di and corresponding labels y: gdout, We define the data matrix as X = (II,..., _x,) ) E nxd.. Throughout this work, we consider a nigh-dimensional regime, where the data points do not exceed the input dimension, i.e., n S dn, To ensure the well-posedness of our theoretical results, we impose the following assumption on the data matrix:
Assumption 3.1 (Full-rank data matrix). The matrix X has full row rank, i.c., rank(X) = n.
This assumption essential for establishing global convergence guarantees. As demonstrated the proof of our main result, the existence of global minima cannot be ensured without Assumption 3.1
3

---

We consider fully connected feedforward neural network with L layers, defined by fNN (a: == W WLo (...a (W2o(Wa where a is an element-wise activation function. The weight matrices are specified as W1 E grxds W3 E ge for j E , 1}. and Wz E Rr We assume all hidden layers share a common width r.
Next, we introduce our assumption on the activation function.
Assumption 3.2 (Activation). a : R - RR is monotonically increasing and satisfies o(0) = 0.
Especially, there exists constant < < 2 such that inf o' o'(z) holds" Moreover, o is zER
e-Lipschitz, i.e., for any u1, U2 E R. (us) ( S f/u1 u2l holds.
typical example of an activation function satisfying Assumption 3.2 the LeakyReLU activation defined by + max(2, (x, ax) for a < 1, which satisfies the assumption with a = and & 1. On the other hand, the standard ReI.U activation + max (x. 0} does not satisfy Assumption 3.2
Nevertheless, we provide global convergence result for networks with ReLU activation through modified BCD algorithm, as detailed in Section [6]
Given this neural network formulation, we formalize the supervised regression problem as
min W
[[)NN())) - -34l
(1)
where W = TWW:....... WL) denotes the collection of weight matrices. One of the most commonly used methods for solving (1) is the (stochastic) gradient method, which updates parameters based on the gradient of the loss function. In contrast, we employ layer-wise optimization method known as block coordinate descent, which we introduce in the following section.
4 Block Coordinate Descent
In this section, we first introduce the basic concept of block coordinate descent (BCD) and then describe the specific BCD algorithm considered in this paper. Originally developed within the field of mathematical optimization (see, e.g., (34), BCD is general framework for solving -igh-dimensional optimization problems by partitioning the set variables into disjoint blocks and optimizing each block iteratively while keeping the others fixed.
In our setting, instead of directly minimizing the original loss in (T. we introduce auxiliary variables Vi. VL-1.; for each training input z4, where each Vj IR' serves an approximation of the output of the j-th hidden layer for the i-th input. This leads us to reformulate the objective as:
L-1
min F(W, V) V) W.V
W vill +
Σ
(W, - Vi
(2)
1=1
where 7 is a regularization hyperparameter, Vo, Z. W (W ....... Wz), and V denotes the collection of all auxiliary variables. In this formulation, the second term in 2 quantifies the layer-wise reconstruction loss, measuring how well each auxiliary variable V,,, approximates the true output of the j-th layer, and the first term corresponds to the prediction error at the output layer. By construction, (W*, V*) satisfies F(W*, V*) 0, then the corresponding weight matrices V form global minimizer of the original problem
One of the key advantages of the reformulated objective in (2) is that it allows to treat the optimiza- tion with respect to the weights of each layer W1,..., Wt independently. This decoupling simplifies the optimization process and enables efficient implementation strategies, such as parallelization. Although various methods have been proposed for optimizing 2 we focus on a relatively simple yet effective scheme: we update the weight matrices W, and the auxiliary variables Vj, sequentially, starting from the output layer and proceeding backward through the network. Concretely, the update sequence is given by
Wz - VL-1, W + W... -1, +
by using the objective funtion 2 We summarize the full algorithm considered in this paper in Algorithm [
In the following, we provide a detailed explanation of each step of the algorithm.
"f is not differentiable, assume that (x1) (122) 2 a(x1 22) for any 3t, x2 E R.

---

Algorithm 1: Block Coordinate Descent
Input
K: outer iterations, Ky: inner iterations for Vj Kw: inner iterations for W1:
liv step size for V3.5. (1) 12); step sizes for weight updates
"Ww' iid ~ N00, ", (Wz)ah ~ (o for ......
Initialization: (Wi)as Lid.
Apply singular value bounding to W for j ....., ...,. (see Algorithm Set Vo,i & Iú. and V32=+ < (W,VV-1,,) for j = 1,...,
for k 1 to K do
2
Wr. f W,. "W
Vw E [[V - - yill²:
for f 1 to do
for j - - 1. - BΙ V VVL WV - 3:11?
Vi.-1.: f
do
W W 7W W E (WW,)))-1.)) - Vg.el1:
11)
for i < 1 to do
for kin t- to Kv do
Vi-1 t V5-1. YI lo, Visl1?:
for kin
to Kw do
W1 - W1 VI Ww, Ba - V1,=11
11
Remark 4.1. The introduction of auxiliary variables V slightly increases memory usage with the number of samples, but the computation for each block can be executed in parallel or distributed across devices. In practice, this allows the method to scale efficiently even for moderately large datasets.
Initialization: Each weight matrix W, is initialized with Gaussian entries: N(0,, d for W1, and r=)) for 2. For layers j = 2.... L., we apply singular value bounding (SVB) [18] by computing the singular value decomposition W; UEV. clipping singular values in Σ to the range 82]. and reconstructing W, UE'V. The detailed implementation is provided in Algorithm and is deferred Appendix A due to space limitation
Originally introduced to stabilize gradient-based training, SVB also enhances BCD performance. It improves the conditioning of the hidden layer loss [|o(W, Vj,i 112 and mitigates large activations by constraining the operator norm W,. Auxiliary variables V are then initialized exactly V VW..i) for all 1, ........ L - = I.....n, n, This approach ensures zero hidden loss at initialization and promotes faster convergence.
Update of V: We update the auxiliary variables Vj., via gradient descent with a common step size v/, applying multiple iterations per update. For VL-1, we minimize the output loss:
VL-1, + Vz-1, 'л V W - y:11?,
which corresponds to solving the linear system W2 WLV11 = y:. A unique solution exists WL E Rdon xr has full row rank.
For ....., T 1, we update VG-1, using the hidden layer loss: Vg-1, + V,- 7/V Vy,... Vy (W, - V2
Assuming satisfies Assumption 3.2 its strict monotonicity implies invertibility. Hence, updating V, approximates solving W VV, Vj.s (V,+1.). Provided W,+1 E Rrxr invertible, gradient descent with a properly chosen mу will converge to a solution.
Note that, unlike the hidden representations Vy,, for j L-1, 1, the update of the final hidden representation Vz.1,; (for the output layer) is performed only once per outer iteration, unlike the hidden layers. This asymmetry is intentional and theoretically justified (see Appendix D). since the output-layer subproblem is linear and converges in single step.
Unlike [8]. which applies SVB throughout training. we restrict it to initialization. With suitably small update step. the singular values of W, remain bounded, preserving the benefits of SVB without repeated enforcement.
5

---

Remark 4.2. In Algorithm each hidden representation V,, is updated using only the local loss [[o[W, (V, - Vl,, instead of solving the full BCD subproblem that also involves the adjacent layers. This simplified update sufficient for convergence (see Theorem 5.1 since the hidden-layer losses become very small after each outer iteration, and further updates would have little effect on the overall optimization.
Update of W: Each weight matrix Wj is updated using its corresponding loss term. For the output layer, the loss is 2 -im1 WWWVV-1, Ill while for hidden layers I,...,, 1, use E (W,,,, V V1
(1) Weights W, for j = .... L are updated once per iteration using step size ThW (line 2 and
(1)
WL - WL - -WW Vwz.
-
W, W3 7iW (1)
Vw,
Io(W, v- V.rel1?.
contrast, W, is updated multiple times per round using a different step size T/ (line 11
W1 + W1
?OW V W1 lo V1,ill
This asymmetry is essential for convergence. Since both Wj and Vj-1,5 are updated for j 2 2, single weight update suffices ensure the hidden loss decreases linearly by applying multiple updates to the auxiliary variables Vi-1,i, assuming the singular values of Wj remain bounded. However, multiple updates unnecessary and may destabilize training when r, exact minimizers may not exist. For W1, fixed inputs Vo.+ z; enable linear convergence under Assumption 3.1 (din 2 n, rank(X) n1), ensuring global minimizer exists and justifying repeated updates.
Remark 4.3. Unlike prior BCD-based approaches that incorporate regularization or proximal
updates 43 19 22]], our method uses plain gradient descent. Though the convergence analysis is
tailored this setting, the framework extends naturally to alternative loss functions, classification tasks, and regularized objectives, as discussed in Appendix B In addition, the same framework can be extended handle non-bijective activations such as ReLU by incorporating skip connections and non-negative projections (see Section 6)
Global Convergence of Block Coordinate Descent
In this section, demonstrate that block coordinate descent (BCD) applied neural networks with activation functions satisfying Assumption 3.2 converges to global minima. That is, the objective value F can be made arbitrarily small through the proposed training procedure. We focus first on the single-output case where dout = 1. The extension to the multi-output case is discussed in Appendix C Additionally, for the single-output setting, derive generalization bound under the assumption of i.i.d. data, utilizing the Rademacher complexity framework.
5.1 Global Convergence with Monotonically Increasing Activation
We consider the case of single-output regression (dout = 1), for which the objective function takes the form:
min F(W, V) (WZVL-1,5- 2 + Σ (o(WWV V3
(3)
We now state the first main result, the global convergence BCD with activation satisfying Assump-
tion 3.2

---

Theorem 5.1. Suppose that activation a satisfies Assumption the smallest singular value of the data matrix X. Let R₁ Wr. Vi.V1.,1,5 Yel be the ini- tial residual at the output layer, and define == =>= Ry. Rmax = max R2, and CK =
3.2
Let s = Tmin (X) denote
(2) ma +
2 Vave). Then, there exists a constans Cv > 0 such that under ($1. 82) Kv
=
VV" G 1), TV S 1oyer VW 8VFCCK (2) 'WW S
(1)
(2)
3exmmxx|1,.11 and K =
[ - log 3R
1 log yaloy
(187 )|
.KW==
4ysa2 (2) log
388 maxx]lz.1l'rrCC
) it holds
a²
V) S,
where W (W1, W and V (V1,1,--.. .....,,VV-- VL-1n) are the output of Algorithm 7
The proof provided in Appendix D Theorem 5.1 establishes that the proposed BCD algorithm provably converges to global minimum. In particular, for any arbitrary accuracy level e > 0, the algorithm guarantees that the objective function value can be made less than e. While the definitions of the inner and outer loop iteration counts K, Ky, and Kw are somewhat technical, the total number of gradient computations required to reach an e-accurate solution is bounded by Ô (KLLKy + Kw)) Ô (nL (1))
The proof is divided into two key parts: (i) the output-layer loss linearly decreases monotonically across outer iterations, and (ii) the hidden-layer losses remain sufficiently small the end of each iteration. Further details are deferred to Appendix[] D
It is important to emphasize that the convergence guarantees provided in Theorem 5. fall outside the scope of the neural tangent kernel (NTK) regime [17], among other related frameworks. Specifically, while the NTK regime assumes that the network parameters remain nearly constant throughout training, our analysis accommodates settings in which the parameters may evolve by a constant magnitude, i.e., change order (?1)..
Remark 5.2. While Assumption 3. requires the data matrix X E Raxdos to have full row rank, we note that the proposed algorithm remains well-behaved even when din- In this case, the residual error at the first layer does not vanish completely but remains bounded, leading to an effective error level Etotal e + 81, where 81 represents the first-layer approximation error. When X approximately spans the relevant subspace for Vi,i, 51 is small, and the convergence behavior is qualitatively similar the I d regime.
5.2 Generalization Error Bound
The objective of this subsection is to demonstrate that the BCD algorithm described in Algorithm not only enjoys strong convergence guarantees but also achieves favorable generalization performance. To this end, we make the following assumption on the data distribution:
|
Assumption 5.3. The training sample {(T;, }:)} 1 is independently sampled from a distribution (z..y) P. Under the distribution P, holds that ||>||| S Bx and lyl S By almost surely.
This assumption commonly used in generalization error analysis. The first part specifies the i.i.d. nature of the data, while the boundedness conditions ensure that the loss remains controlled with high probability. We next define the generalization gap: Definition 5.4 (Generalization gap). The generalization gap is defined as the difference between training and test error, that is,
Gap == E( (fNN(()) 27
Σ (fNN(a.) - yi 2
We now present the main result of this subsection:
Theorem 5.5. Let NNN be the output of Algorithm under the same condition as Theorem 5.1 Then, under Assumption 5.3 with probability at least 1 over the training samples ((x,, yi) 3 the generalization gap satisfies
Gap S o
|X|| n
By + 2h 1iel-BBx Bx)d L (2r) logr + (By + 2- Bx log(1/5)
7

---

The proof of Theorem 5.3 is provided in Appendix E This result establishes that deep neural networks trained via block coordinate descent not only converge global minima but also generalize well, extending guarantees beyond the NTK regime.
The derivation is based on the generalization analysis framework introduced by 8 which bounds the generalization gap in terms of the spectral norms of the weight matrices. As discussed in the previous sections, our convergence analysis guarantees that the spectral norm of each W; remains bounded throughout training. Combining this boundedness with the Rademacher complexity-basee bounds in we obtain a high-probability upper bound on the generalization error of trained networks.
g
ReLU Activation
In this section, we propose modified BCD algorithm tailored explicitly for neural networks with the ReLU activation function, defined as (xx) == max (z. 0). This setting is excluded from the analysis in Theorem [5. due to the violation of Assumption (.2 which requires strict monotonicity. The primary difficulty in handling ReLU lies in its non-negative range. To achieve zero hidden layer loss of the form |o (W, - V the approximation cannot reach zero due to the non-negativity constraint imposed by ReI.U. This necessitates a modification to the original BCD algorithm (Algorithm TT.
we must ensure that V, does not contain negative entries otherwise,
6.1 BCD for Neural Networks with Skip Connection
To address this issue, we employ residual network (ResNet) architecture [6] incorporating skip connections into the model. This modifies the BCD objective as follows:
min F(W, V) = Σ W. - y1)) +7 W.V
>
(o( + Vg
J=2
(W.lo( V1.i1
where the hidden layer loss now includes the skip connection term Vg-1. modifying the structure compared the original formulation in 3 To guarantee that the auxiliary variables Vy. remain within the feasible range of ReLU outputs. we introduce non non-ne nog-nnett projection steps of the form VJT = max V, f, 0}. The complete algorithm, incorporating skip connections and projections. is detailed in Algorithm 3 which is deferred to Appendix A due to space limitations. In the following, we provide a detailed explanation of this modified procedure.
The initialization and update procedures for weight matrices remain unchanged between Algorithm ] and Algorithm 3 However, several modifications introduced to accommodate the ReLU activation. First, Algorithm includes non-negative projection V + V+ applied to each Vj, after the inner loop, ensuring the equation ([,(WW) - -V,,l12 = 0 is solvable by aligning with the non-ne nog-tegative range of ReLU. Second, in contrast to Algorithm I the output layer weights W, are held fixed during training. This design ensures solvability of the equation W. WL = ys under the constraint VL-1,; 2 0. The following lemma formalizes this condition:
Lemma 6.1. Suppose the vector WL contains both positive and negative entries. Then, for any yo there exists non-negative vector VL.11; such that Wy VL.1,5 y:-
Lemma 6.
ensures solvability if WL has mixed-sign entries, a condition increasingly probable as hidden layer width grows. Specifically, the probability is - under Gaussian initialization. Moreover, we provide concentration bound on the positive and negative components of Wz, relevant to convergence rates:
Lemma 6.2. Let WTJ (0 (1)) w4 max(WL, 0 J and w_ min WL. 0 }. Then, for any 8 0, with probability at least - 28, w = || 11 || 1
8 (og(2/ holds.
To simplify analysis, we fix W,, throughout training, since extending the bound in Lemma 6.2 to dynamic updates across iterations is non-trivial.
The update of W, performed via gradient descent (line 12
Notably, the ReLU activation is omitted
in this update. Since the projection step ensures Vi,i 2 0. solving Vo,) Vi, reduces to
8

---

10a
Training loss without
10a
Training
without skip connection
10a
1055
l055
10
10-
10
10-
500
1000
1500
2500 3000 3500 4000 opoch
2000
500
1000
1500
2000
2500 3000 1500 4000
epoch
Figure 2: Training loss of Algorithm with LeakyReLU activation (a 0.5).
Figure 3: Training loss of Algorithm 3 with ReLU activation.
solving the linear system Wi Vo. Vi,i. which is more tractable. As in the previous section, consider the single-output case dout = 1. We now present the convergence result for Algorithm applied to ReLU networks with skip connections.
Theorem 6.3. Define Rú Rmaxo and CK as in Theorem
5.1
Then, there exists constant
Cv
O such that under (81,82) (0, 1) π
A
1
OW I
(1)
24/TCV (3)
2w
12y
(2) Tw
S 2.max|la;; 12, and K =
any wain log 3R Kv =
3 log
245(1_-))raC,, KW =
3e
2max|12211 ]
log
it holds
s²c
F(W, SE,
where W (Wi,..., Wt) and V .Vi,,...., V 1.) are the oulput of Algorithm
The proof is provided in Appendix[[ F This result establishes global convergence guarantee for BCD applied to deep neural networks with ReLU activation, under the skip-connection architecture.
7 Numerical Experiment
In this section, we conduct numerical experiments to empirically validate the theoretical results established in Sections 4 and 6 Specifically, we confirm that the BCD algorithms for networks with (i) strictly monotonically incrassing activation functions (Algorithm I and (ii) ReLU activation with skip connections (Algorithm 3 successfully converge global minima on a synthetic dataset. All experiments were conducted using Google Colab with T4 GPU. Each experiment is independently repeated five times. We report the mean training loss along with standard deviation bands.
7.1 Monotonically Increasing Activation
We first evaluate BCD using a strictly monotonically increasing activation function. We apply Algorithm [ to neural network with four hidden layers of width r 30, using LeakyReL activation defined by (zx) = max(2, (.5z). which satisfies Assumption 3.2 with a = 0.5 and é= The training data consists of n 500 samples generated from teacher network with one hidden layer and the same activation. Each input æ; E 18600 is sampled from a standard Gaussian distribution, and the output y; is computed by the teacher network. We set the hyperparameters to
Ky Kw 100, and all step sizes fγy = = = 7/w 1
The results are shown in Figure 2 The blue
represents the training loss. The training loss monotonically decreases, and the layer-wise residuals remain small, which aligns with our theoretical findings. To assess the effect of singular value bounding (SVB, Algorithm 2}. we conduct an ablation experiment where the network trained without applying SVB. The red curve in Figure 2 shows that, in this case, the loss stagnates around 10 This demonstrates that SVB contributes not only to theoretical convergence but also to practical training stability and effectiveness.
To further examine the scalability of the proposed BCD algorithm, we conducted additional exper- iments on deeper networks (T. 8, 12); the results consistently showed monotonic loss decrease across layers. Detailed results and plots are provided in Appendix G

---

7.2 ReLU Activation
We next evaluate Algorithm B on ReLU-activated network with skip connections. We use the same architecture as in the previous subsection: four hidden layers of width r = 30, with n = 500 training samples in R8,000 generated from teacher network with ReLU activation. As before, we set
Ky = Kw = 100 and step sizes = fWw
TW = 1.
Figure shows the results. The blue curve represents the training loss using skip connections. As expected, the loss decreases monotonically, and the internal residuals remain small. To demonstrate the importance of skip connections, shows that training fails to converge in this case due to the ReLU negatvivy constraint, which makes it challenging to match intermediate representations. This supports theoretical conclusion that skip connections are crucial for achieving global convergence under ReI.U activation.
also train network without them. The red curve in Figure 3
8 Conclusion
In this work, we proposed block coordinate descent (BCD) framework for training deep neural networks and established global convergence guarantees under strictly monotonically increasing activation functions. Our analysis demonstrated that the proposed method achieves arbitrarily small training loss, and we further derived generalization bound based on Rademacher complexity. To address the challenges posed by non-monotonic activations such as ReLU, we introduced modified BCD algorithm that incorporates skip connections and non-negative projections. This variant ensures global convergence even in the presence of ReLU activations, thereby extending the applicability of BCD to widely used modern architectures. Extensive numerical experiments corroborated our theoretical findings, showing that the proposed algorithms perform effectively in practice for both monotonie and ReLU activation functions.
References
[1] Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? Advances in Neural Information Processing Systems, 32, 2019.
[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers. Advances in neural information processing systems, 32, 2019.
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameteriizatonn. In International conference on machine learning, pages 242-252. PMLR, 2019.
[4] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pages 322-332. PMLR, 2019.
[5] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International conference on machine learning, pages 254-263. PMLR, 2018.
[6] Armin Askari, Geoffrey Negiar, Rajiv Sambharya, and Laurent Ghaoui. networks. arXiv preprint
Lifted neural
May 2018.
[7] Arindam Banerjee, Pedro Cisneros- Velarde, Libin Zhu, and Misha Belkin. Restricted strong convexity of deep learning models with smooth activations. In The Eleventh International Conference Learning Representations, 2023.
[8] Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normaaizee margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
[9] Peter I. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve- dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1-17, 2019.
10

---

[10] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Foundations and TrendsS in Machine learning, 3(1):1-122, 2011.
[11] Miguel Carreira- Perpinan and Weiran Wang. Distributed optimization of deeply nested systems. In Artificial Intelligence and Statisties, pages 10-19. PMLR, 2014.
[12] Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. Advances in neural information processing systems, 31, 2018.
[13] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning. pages 1675-1685. PMLR, 2019.
[14) Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of a single neuron with gradient descent. Advances in Neural Information Processing Systems, 33:5417-5428, 2020.
[15] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR, 2018.
[16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[17] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[18] Kui Jia, Dacheng Tao, Shenghua Gao, and Xiangmin Xu. Improving training of deep neural networks via singular value bounding. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 4344 4352, 2017.
[19] Tim Tiz-Kit Lau, Jinshan Zeng, Baoyuan Wu, and Yuan Yao. A proximal block coordinate descent algorithm for deep neural network training, arXiv preprini a0X0v21803.00082, 2018.
[20] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. Advances in neural information processing systems, 31, 2018.
[21] Dhruv Mahajan, S Sathiya Keerthi, and S Sundararajan. distributed block coordinate descent method for training 11 regularized linear classifiers. Journal of Machine Learning Research, 18(91):1-35, 2017.
[22] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on learning theory, pages 2388-2464, PMLR, 2019.
[23] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[24] Kensuke Nakamura, Stefano Soatto, and Byung- Woo Hong. Block-cyelic stochastic coordinate descent for deep neural networks. Neural Networks, 139:348-357, 2021.
[25] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally-normaaizze margin bounds for neural networks. arXiv preprint /70.:v::707709555 2017.
[26] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control neural networks. In Conference on learning theory, pages 1376-1401. PMLR, 2015.
[27] Phan-Minh Nguyen and Huy Tuan Pham. A rigorous framework for the mean field limit of multilayer neural networks. Mathematical Statistics and Learning, 6(3):201-357, 2023.
[28] Atsushi Nitanda and Taiji Suzuki. Stochastic particle gradient descent for infinite ensembles. arXiv preprint 17I.vv1112.054. 2017.

---

[29] Ravi G Patel, Nathaniel A Trask, Mamikon A Gulian, and Eric C Cyr. A block coordinate descent optimizer for classification problems exploiting convexity. arXiv preprint arXiv:2006. 2020.
[30] Huy Tuan Pham and Phan-Minh Nguyen. Global convergence of three-layer neural networks in the mean field regime. arXiv preprint arXiv:2105.05226 2021.
[31] Linbo Qiao, Tao Sun, Hengyue Pan, and Dongsheng Li. Inertial proximal deep learning alternating minimization for efficient neutral network training. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3895- 3899. IEEE, 2021.
[32] Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International conference on machine learning, pages 4433 4441. PMLR, 2018.
[33] Taiji Suzuki, Hiroshi Abe, and Tomoaki Nishimura. Compression based bound for non- compressed network: unified generalization error analysis of large compressible deep neural network. In International Conference Learning Representations, 2020.
[34] Paul Tseng. Convergence of block coordinate descent method for nondifferentiable minimiza- tion. Journal of optimization theory and applications, 109:475-499) 2001.
[35] Belinda Tzen and Maxim Raginsky. A mean-field theory of lazy training in two-layer neu- ral nets: entropic regularization and controlled mckean-vlasov dynamics. arXiv preprini arXiv:2002.01987. 2020.
[36] Martin J Wainwright. High diggeniimnni statistics: statissssss A non-asymptotic viewpoint, volume 48.
Cambridge university press, 2019.
[37] Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. Advances in Neural Information Processing Systems, 32, 2019.
[38] Jintao Xu, Chenglong Bao, and Wenxun Xing. Convergence rates of training deep neural networks via alternating minimization methods. Optimization Letters, 18(4):909-92) 9209999,,,, 2024.
[39] Tian Ye and Simon S Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. Advances in Neural Information Processing Systems, 34: 14:11499-443, 2021.
[40] Gilad Yehudai and Shamir Ohad. Learning a single neuron with gradient methods. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3756-3786. PMLR, 2020.
[41] Jinshan Zeng, Tim Tsz-Kit Lau, Shaobo Lin, and Yuan Yao. Global convergence of block coordinate descent in deep learning. In International conference on machine learning, pages 7313-7323. PMLR, 2019.
[42] Hui Zhang, Shenglong Zhou, Geoffrey Ye Li, and Naihua Xiu. 0/1 deep neural networks via block coordinate descent. arXiv preprint arXiv:2206.099:: 2022.
[43] Ziming Zhang and Matthew Brand, Convergent block coordinate descent for training tikhonov regularized deep neural networks. Advances in Neural Information Processing Systems, 30, 2017.
[44] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine learning, 109:467-49 492, 2020.
12

---

A Omitted Pseudocode
In this section, we provide pseudocode for two procedures that were omitted in the main paper due to space limitations. Specifically, describe the Singular Value Bounding (SVB, Algorithm 2 and the Block Coordinate Descent algorithm for ReLU activation (Algorithm
Algorithm 2: Singular Value Bounding (SVB)
Input :: weight matrix, (81, 82): lower and upper bounds on singular values Regularized matrix with bounded singular values
Output:
Compute the singular value decomposition: (U, E, V) <- WW)(W;);
foreach singular value in the diagonal of 2 do
8 f max(5), 51, m2n }}}
// Clip s to the interval [$1, s2]
return UEV
Algorithm 3: Block Coordinate Descent for ReI.U Activation
Input
:K: outer iterations, Ky: inner iterations for V,, Kw: inner iterations for W1.
(1) (1)) step sizes for weight updates T/: step size for Vg.i 7/W
Initialization:
(W1)ab lid. N(O,, d, (Wj)ab itd N for j = 2, ..... Apply singular value bounding to W, for j 2.... ..... L (see Algorithm
Set Vo,; + Ii,
Set V1.5 + oWW, Vo.)).
Set 13 & (W)V)- + V5-1, for j = 2.... . L
for k < 1 to K do
2
for i f 1 to n do
VL-1,
1-11 ny V2 V W -2:l2:
Vi,-1.i (Vi.-1a)*;
for j < L 1 do
W, < W, -W Vw, E loW, - V3-15 - Viul?
for <- 1 to n
for kim - to Kv do
V, v, < 1,, YM V - 10,, V--1, - Vy.e11:
10
Vj-1. + (Vg-1,))
11
for kmn 4- Kw do
12
W1 + W1 mw
V Ww En
Wo, - V1,a11?
B Discussion of Extension
As mentioned in Remark 4.3 convergence analysis is based simple variant of block coordinate
descent (BCD), where gradient descent is applied to minimize the standard squared loss. In this section, discuss possible extensions of the proposed algorithms (Algorithms and to broader settings.
General Loss Functions. natural and practically relevant extension is to replace the squared loss with general loss function f(.-)). This modification allows the framework to go beyond regression and encompass classification and other supervised learning tasks. Under this extension, the objective becomes:
min F(W, V) ((WLV-LL..)) +
Σ lo(W V3
W.V
where only the output-layer loss differs from the original formulation in 3
13

---

The hidden layer loss term remains unchanged, so the analysis in Theorem still applies to those layers. Therefore, to establish convergence in this generalized setting, suffices to prove that the output layer subproblem involving W,, and Vi.1 converges globally under the new loss t.
For example, if ((:-)) is strongly convex (e.g., logistic cross-entropy loss), standard results in convex optimization can be used to ensure convergence. A typical case is the cross-entropy loss for multi-class classification:
dous
exp((W
&. Vi)
Σ
Vie log
cd==1 (Wp (WVVV-1,,)))
dout
which is widely used for dont-class classification tasks.
Thus, although our main analysis focuses on regression using the squared loss, the BCD frame- work and associated convergence guarantees can be extended to classification problems and other supervised learning settings by appropriately modifying the output-layer loss.
Different Activation Functions Across Layers. While our analysis assumes that all layers share the same activation function a, it is straightforward to extend the results to the case where each layer uses a distinct activation a. provided that each oj satisfies Assumption 3.2 In this case, the convergence proof in Theorem remains valid by replacing a with oj in the convergence argument corresponding to the j-th layer.
Alternative Initialization Schemes. In Algorithm 1 initialize the weights W3 using Gaussian distributions and apply singular value bounding (SVB), while the auxiliary variables Vj.5 are initialized exactly as V a (W, 5- 1,s). However, global convergence only requires that the regularity condition from Lemma D.4 be maintained throughout training. Hence, the initialization scheme is flexible. In particular, Gaussian initialization is not necessary-alteneee initialization, which uses a uniform distribution with appropriately scaled bounds, can also be applied as long as they yield well-conditioned weight matrices.
methods such Xavier
We now consider the use of activation functions that do not satisfy Assumption 3.2. including those beyond ReLU. Our analysis heavily relies on the monotonicity of the activation function to ensure that the optimization landscape avoids undesirable local minima caused by vanishing gradients (e.g.. points where o' = 0). Without monotonicity, there is no guarantee that gradient- gradient-based updates will escape such critical points, which may result in failure to reach the global minimum.
Activations Violating Assumption 3.2
That said, some commonly used monotonic activations that violate Assumption 3.2 such as sigmoid and tanh, are still of interest. The key challenge in analyzing these functions fies in their bounded output ranges:
Sigmoid: (x) 1+expl- xx] E (0, 1),
Tanh: (zz)=
exp( (an(z)-en) expp -x)
(-1,
exp(x) texpl
In these cases, it becomes essential to ensure that the auxiliary variables Vj.; remain within the output range the corresponding activation function. This is analogous to the ReLU case, where we enforce non-negativv through projection. As discussed in Section we addressed this challenge for ReLU using skip connections. Similar techniques- such as range-aware projections or bounded initialization-mal be required to extend BCD to these bounded activations.
Training Loss with Regularization Terms. A line of work on BCD methods considers regularized training objectives, where the loss function includes additional penalty terms. In this setting, the objective takes the form:
min F(W, V) W.V
Σ ( (WLVL-1.1 v1)² rw +rr(WL) (WL)
+ +
(lo(W,Vs11.)) Vg. (W,)) + rv(V)))
14

---

where rw and rv denote regularization terms for weights and hidden representations, respectively. In this setting, additional gradient terms appear in the update steps for W and VJ, corresponding to the gradients of Tw and rv. While the inclusion regularization complicates the convergence analysis, global convergence still be established under certain oonditions-sseciffclllyy specifically, when the regularizers are strongly convex. A common example is Tikhonov (or (2) regularization.
However, incorporating regularization introduces trade-off between optimization and generalization. In particular, to derive a generalization error bound analogous to Theorem [.5] it necessary
to carefully analyze the gap in training loss introduced by the regularization terms. This involves quantifying how regularization affects the empirical risk and bounding its impact on the generalization gap.
C Extension to Multi-Dimeenional Output
We now consider the case of malti-dimenssonal outputs, where the loss function is given by:
min F(W, V) Σ WW.V -1:l lo(W,V)-L.) - Visll?
W.V.
with Ui Rdou and dout 1.
Compared to the scalar-output setting, the main challenge lies in analyzing the convergence of the output-layer parameters Wr. and Vi.i... When rank(Wr.) 2 dout. the linear system
WLVL-1, = y:
has solutions, and the convergence analysis follows similarly to Theorem 5.1 using standard gradient descent arguments.
However, when dout > rank(W,,)) the system may not admit a solution, making global con- vergence unattainable without additional assumptions. To address this, we introduce the following low-rank structure assumption on the labels:
Assumption C.1 (Low-Red Rann Label Representation), There exists an integer r < dout and matrix U1 E dout Xi such that for all i E (I....,1), the label satisfies yı Uı for some z; E R".
Under Assumption C.I. the system has solution for example, choosing WL U1 and V However, the question remains whether gradient descent can find such a solution in practice. To explore this, consider the gradient descent update for W,, as in line If Algorithm For general don.. the update can be written as:
w(b = (-(
1-7W T/W VL-LLVI + UW Σ
[
2, VV
Here, the first term implies that with sufficiently small step size 1Ww the norm of W, decays exponentially in directions orthogonal to the span of (V.-1.1). Meanwhile, the second term injects components aligned with U1. In particular, when the matrix E/= 2, ViVi-1, E Rrxr is full rank, the expression
W, U
Σ 2, V
L-15
may serve solution to 44 if an appropriate inverse exists.
While this offers intuitive insight, rigorous convergence guarantees in the multi-output case are non-trivial. Fortunately, recent result by [39] addresses this issue:
Theorem C.2 (Theorem 1.1 in (39). Suppose Y [y1...., , yn E Rdoon xn satisfies Assumption /. Let and s, denote the smallest and largest singular values Y, respectively. Assume all entries of Wr and V1 are initialized independently from N 82), where
8 δ
ST Vr3sI( + dout)
15

---

Then, using step size 1) O
gradient descent satisfies Ei=1 1
11,, - 3/2=
after
r8r
8r -
0
log
+
log
1781
178r
iterations.
To apply Theorem C.2 to our BCD setting, two modifications are required relative to the proof of Theorem 5.
1. Replace the convergence argument for WL and VL-1, with Theorem C.2 iteration bound from the theorem.
yielding the
2. Adjust the initialization scheme: Theorem assumes Gaussian initialization for both WL and V2-1.s. which differs from the exact-layer initialization Vj,+ = =WWW used in Theorem 5.1
As discussed in Appendix B the exact-layer initialization mainly serves to ensure a small initial objective value, and our analysis can be extended to other initialization schemes. Therefore, by adopting Gaussian initialization and integrating Theorem C.2 the convergence guarantees of BCD can be extended to multi-output settings.
D Proof of Theorem 5.1
In this section, we provide the proof to Theorem 5.1 The key notion is the block-wise analysis. First, we provide the preliminary lemmas for the proot. After that, we prepare the flockwiise analysis and combine them.
Throughout this section, we suppose that the conditions in Theorem are satisfied.
D.1 Preliminary Results
The following lemma immediately follows from the smoothness of the activation.
Lemma D.I. Let d 2 1 an integer. For any It, D2 E Idd it holds that [|o(x)) -(12)) < e|| 22/12.
Next, by utilizing Assumption 3.2 we derive the following lemma.
Lemma D.2. For activation function satisfying Assumption 3.2 for any E R, there exists & such that a E < l and ox + y) (z) Ey hold.
Proof. We first consider case y >> Then, we have
ae y) (xx) //' o' d'xx t)dt f ay.
The Lipschitz continuity of a gives (rr + s (xx) - by. Thus we get
a E = o(r v) (x) s/
which gives the conclusion.
The case < 0 can be proven by substituting x and in above discussion by x + and -y. In the case y 0 we can take arbitrary & with - & to satisfy the assertion.
This lemma gives the following proposition, which utilize throughout the convergence analysis.
Proposition D.3. For activation functions satisfying Assumption 3.2 and an integer d > 1, for any x, y E Rdd, there exists a diagonal matrix 3\t such that euch diagonal entry Ej of A satisfies Egj < l and oxx y) o(x) + Ey.
16

---

Proof. Note that by Lemma D.2 for each j 1......dd d, there exists Ej satisfying a(r + +y1 = a + プ. Then, diag(E1 ....... Edd) satisfies the desired condition.
Next, we prove that the singular values of W3 2,.2..... L) are upper and lower bounded during the training.
Lemma D.4 (Regularity of weight matrix W during training). For j 2..... L, v
1/2 (W,W7) I 1/2 (W,W,) s always holds during the training.
To obtain this lemma, we utilize the following fact:
Lemma D.5 (Weyl's incquality for singular values). Let A E IRd1 xd2 be real-valued matrix, then, for every matrix A ddd,
, it holds that
max oo
(A (A
A) - ox((A) - m (A);
where (A) denotes the k-th largest singular value of A and J (A) denotes its maximum singular value.
Proof of Lemma D.4 By Lemma D.5 suffices to show that every row w W, satisfies ||Aw|| < LVF: where Aw denotes the difference between w at the start and end of the training. Indeed, this implies
Tmax (AW) A (AWA S
>((AWAWT) V Tr(AWAWT)
=AWW| S 4
Combining this bound with 3 S mmnn (W,) & o max (W,) S 5. which holds at the initialization, gives the conclusion.
1
To this end, we prove |Awll S T This follows from
TW Vollo(VV
2'12 2n r
(a(wV) VOI
< 2mw
(1) 1211/2 (VVT) [[((W) V'Il
s 21w XLCv TM (2)
4K
where the second incquality follows from Lemma D.6 and the last inequality follows from the (1)
definition of 1/w
Lemma D.6. Let cy = max E Vy where V,s are the parameters at the initialization.
Under the same settings as Theorem Cy holds for l,...,,, during the training.
5.1 let Cv = cv + (nmv Then, Amax (V2V,)) S
Proof. First, we have
Amax (V,VT)) Σ - = tr
Σ
Vy 32
Σ tr
(VV
1=1
Σ
(5)
This implies that we only need to evaluate the norm of V3.s during the training. Remind that the update of V, given by
V3 - Vy, 2, D(o - Vi+1.),
17

---

where D = (i,g( (W,,, Let A, = -2mv ; V,,) - V4+1a). Then, we have
,, = 2ynv [ P(o
V/++,)|
- 2ynv |W P P lo Vi+1,ll S 4yemyCK
where in the second inequality, we use || lop = > (W, - from Lemma D.4 | S l,
and ||o (WV,,) - V=+1. S Ck from (15) (Note that objective function [|o Vj+1. monotonically decreasing from Lemma Va is Kv, by using the triangle incquality we have
D.mmaaD.8) D.8. (15) always holds). Since the total number of updating
||V S || + K Kv .4l1yy Ck:
where [|5]3
is the initial value of V2,5.
Substituting this bound ( we obtain
Amax A (VGV)) =
Vinsel J.
+ K Kv 4y Ck)
1m1
72
(11V + (K Kv 4y0my
$
cv + ((TmvnnkKy?)
where we use the inequality (a + b)2 - 2a² + 2b in the second inequality. Thus, we obtain the conclusion.
D.2 Analysis of Gradient Descent in General Form
First, we introduce the key idea of analysis with general notations problem with an objective
Let us consider the regression
F gen (w) = Σ (oww (w Ta) ((WTTKo))))) ya)
(6)
where Rd is trainable parameter. Let w/ parameter obtained by a single update of gradient descent with a step-size 17 > 0. Denote X (01, .. TT)T E Rixd and Y (V1, yb) RR.. Then, Edzı (a(w" (owTxo xxa) ya) (Xo) - 2 holds and a straightforward calculation shows w' = w - 2n ((o(Xw) - Y). where = diag((o'(() 21),..., o'(w" r=))))
1/ F gen (w), where w' denotes the
Now, assume that there exists unique optimal solution w satisfying Fgen (wn) 0, ie.. = (X Then, we have
I|wl w" w²1l
|| 17 V W Fyen gen (w) w w01
= ||u - w²1 112 V w Feen pgen(w)) (w)T(w=- (w- (w0-w)) + 1/ F (en((w))
and
V FwFgen [ww - (w)) = 2(o(Xw) - o(Xw")) DX - ww) 2((X )))) DX w²)
2(w w²) T T EDX (w w")
2 2Amin (x EDX w| - w 11? where E is a diagonal matrix determined by Proposition D.3 and Amin (x (XTEXX) is the smallest eigenvalue of TDX..
Moreover, we have the upper bound of the gradient as
V gen (w) = | D(o(Xw) - y) < 4Amax 4 (D)) - Y1I,, where Amaxe (DXT XD) > 0 the largest eigenvalue of the matrix DXT X.D
"Our analysis is similar that 40 14
18

---

D.3 Block-wise Convergence Analysis
According to the observation in Appendix D.2, we provide the bliek-wise convergence analysis, that is, the convergence analysis of the W and Vj of the each layer.
Update of V3,s (j L...., 2) is written by
2)
According Algorithm
!
the update of V3.a Gj L....,, 1)
Vvs. (o(w),PV..) -())))()))())))))) (V5+1.)))²
Va V3s YV
where Wii denotes the p-th row of the weight matrix of the j-th layer W, and (V)+1,))p denotes the p-th component of Vj+1,5-
Despite the abuse of notation, omit the layer index j and the sample index for notational simplicity. We note that the analysis here can be independently applied to each layer and sample, shown in the proof of the main theorem; hence, this abbreviation does not matter in the proof of Theorem 5.1 Then, can be rewritten by
V
TMV
V - Vy)
(8)
where we denote V = (V)+1,))p-
Let (v = E,
(=
(Wo - V and v(() be the initial point of V, of the
inner loop for each outer iteration (we also use abuse of notation here), and V(k) be the parameter obtained by k iterations of the inner loop.
Under these settings, first show the existence of global minima of Fv follows:
Lemma D.7 (Existence of v²). Suppose that 2 S Jmin (W) and Fmar (W) S 2 hold. Let Av = (WV](0)) V' Then, there exists unique satisfying (v and
| -v-
S 2 Av|l.
Proof. Let Au = oa + Av) - (V Then, it follows that o² v(0) + W-140 Au since
((00+ o ( + +ao) =o =o(w))) + Av.
Now, quently
of (-)) is 1 Lipschitt and satisfies o(0) = 0. Then, we have | S 2 | and conse-
| - 0-| = -| Aull < 'I ||ul| S |
2 2 a
This gives the assertion.
Next, by using the observation in Appendix D.2 we provide the convergence analysis to the update
g
Lemma D.8 (Convergence analysis of V).
Under the same condition as Theorem 5.1
it holds that
[((W)())) - -v1l² s a
16
a²
exp
Proof. By letting + D. r, Ca - wp. Ha
6 we have
||
- 1// 1 -
(9)
+ 7 -v+) = =||v(k) - -0- -2 Vv (vit)) T (v(K)-
Vr (v(x))
19

---

The second term can be bounded by -()))-0) where D = diag (iiag((o((u)) v(k)),.... ,...,,,, ('u Rxxr Then, we have
Voliv (v(ct) T -v)) 2 2dmin (W EDW) || -
-0-
WWTW) 2 a²
mmn (W EDW) 2 a² Amia ( W)
4
where we use Lemma D.4 for the last inequality. Moreover, the third term can be bounded by
|FvFV (v - (DW WWD]DDolOXX) - oXxx )1
I 46 Xmxx (W (W W (WTT)|lo(wv(()) o(Wo'') 2
I A ((()
((0) - vi 4c5 [(()
where we use Lemma D.4 in the third and last inequalities and Lemma D.1 in the third inequality.
By substituting these bounds to 9
we obtain
[(++1)
((k) 0.
2 2
v01 + + 1(:))_v01)
ed) [(()) - 001
7/V
2
((N)
0²
2
YiV
a²
(ommet)lurgg }|(((0) 111
2
(()))
a²
[(()] w²1 7(11- 10-4mm0))) MV |(/0 1|10)//0+ 0011?
a²
-
where we use TV
a² 164ट in the last inequality. This implies
((0) 0-1 2 s (11
a²
4 (mm) )'1 1 -011-
=exp' a² -|r= s exp 1app--mmm (pmmk>|r1o ||:000 v0
where we use
x S eep((=9p -x) in the first inequality, and hence,
|o(WV())) r1I² s /2 w -(()) )1
- 462
((())
vr1?
S 48 exp
a²
4 mmk
| - v'1
166
(-4nnxx) (WV - -vl??
a²
a² exp
which gives the conclusion.
Finally, we provide a lemma evaluating distance to global minima based on the objective value: Lemma D.9. Suppose that Fv(v)= S e holds. Then, || - o=ll || S VVe.
Proof. Since
e 2 Pv())= = (o(Wo)-o(Wo"]] alIlWo wo > - v²
we obtain ||0 w0 S VV.
20

---

Update of w (j = ...... --1) 1) update of each Wip given by
Let wAp E R" be the p-th row of the weight matrix W,. Then,
Wip
Wjp
VIW
(1)
(o(w) (V++1.),)²
(10)
For notational simplicity, we omit the layer index j and the node index p. Namely, the update (T0 simply rewritten by
V (o(wVV) - V!)²
W t w MI
where we denote Vi == V3, and V (Vi+1,))p Let Fw((w) = (i=(o((VV) (= (lo(w) v'I and w be the initial point of Wii of the inner loop for each outer iteration (we also use abuse of notation here), and ((a) be the parameter obtained by k iterations of the inner loop. Against to the argument Fy in the above paragraph, Fw have not solution w² satisfying
Fw (w("w) 0 especially when n > However, we can still ensure that the objective value remains small during the update of W
Update of W1 given by
Let up E Id the p-th row of the weight matrix W1. Then, the update of each up
(o(w)x:)- (Vi.)),
" t wp MW
(11)
Despite the abuse of notation, we omit the node index p for notational simplicity. Namely, the update T simply rewritten by
(h) (K-1)
W/
(2)
V (u (o((tt)))z))) V:) vi)²
(12)
where we denote V; == (V1,))--
Let Fw (w) = (o - v-)² (la - VII2) and (0) be the initial point of wy of the inner loop for each outer iteration (we also use abuse of notation here), and (k()) be the parameter obtained by i iterations of the inner loop.
Lemma D.10 (Existence of W*). Let Ar = (lw(0)x,) V4. Then, there exists a w such that Fm (ww) = 0 and
(0)
w²
Arll.
Proof. The proof essentially same that of Lemma D.7
We then provide the convergence analysis to the update 12) by using the observation in Appendix D.2
Lemma D.11 (Convergence analysis of Wi). Under the same condition as Theorem 5.7
e max 1 | (x(()))) - vill? <
exp ==2=2mm1
(2) (o Vi
(0)
a282
Proof. By letting i b + i, Fa + 24 and yo in Appendix D.2 we obtain
/wi(tt1) w0
(13)
= =||w(00) w² ||= - -2 Ven Fwr (w)(i)) (w)()) - w² + 2 12)2 Fw Fw (wott))
12)²
21

---

The second term can be bounded by
Fw (t)(t) (mo(*) w²) 2 2Amin (x* w(()) w²
Then, we have
Amin (x EDX) 2 a² Amin Amiin(X) (xx) = =a²
Moreover, the third term can be bounded by
Vw F'w (w)(t)) ||
I 4Amax (DX (DXT (X)] -o o(Xw")) x
S 46 Amax T (x o(X w0)) !?2
S max||>=|| es y(s - v/(..
3 e e e op (k) w²
1
where we use Lemma D.4 in the third inequality and Lemma D.1 the third inequality.
By substituting these bounds to
13 we obtain
(++1) w¹
(k) w²
2a 202222mh v (x) w²1 + +
(2)
(2)² e e 12 (()) w'
1/
(k) w²
MWl (2)
22a23² -mmi ex max (1] (10)))/(000 (0) w0
(k) w¹
a² 3 MW
(2)
(h) w0 1|- = -1-a222mmis
a²s² s (2) |w( - w0
where we use T/ 5 7t max a. 1 in the last inequality. This implies
[w(k) w+
1| s (1 a² 25 2,22"16 (2) | w w- S exp (-o² =22=m k) (0))) w-
where we x S exp( -x) in the first inequality, and hence,
(w x) vi
s (2) (t) - -w")
$ 62 max 1|2 (k) w0 112
$ 6 max 12 exp(
a22 (2>2)(12bb)) x)) (0) w- w²1
@ max
|
la²
(2) kk //
(1 (0
- vi
exp
2²
which gives the conclusion.
D.3.1 Proof of Theorem 5.1
Before providing the proof of Theorem 5.1 we introduce the following lemma:
Lemma D.12 (Bound on Au at the output layer). Let Rg = w/(0 ((() 2 Vs Then, we have
| - v s 4R,
Proof. By the construction of the algorithm, we have
|| - - ((--))
22 (w/" (R) (k--)) w
s 2nv
|
((t b-1يt Vz
op
s 4nv
|
((0)
yi = 4nv Ri:
which gives the conclusion.
22

---

Then, we move to the proof to Theorem 5.1
Proof of Theorem
5.7
Let us consider the decomposition of F as
L-1
F FL
Σ
F
+
j=1
i=1
j=1
where
Ft, (W -1))
Fr. Σ i=1
Fi.
and
n
Fja.p == -
Fj
F
for = 1, ...., L 1. The proof consists of two parts: (1) Fz is monotonically decreasing in the outer loop and (II) Fj...p (j I,....,............ L 1, I..... n, = 1, ,,...,7) is sufficiently small at the end of each inner iteration.
(I) Bound on Fz
The update of Vz-1, is described by
(()) 1-1,1 = v/A-1 21 (w// (/ 1-113 Mi W/(
Then, we have
( W 1-11; - Vi = -1--2
2n/v 11) -0:-012200
(w/" 1-n
/// - v.)
This results in
F (k) L. S 1
(1-22 201 [1/ p(k-1) S exp -4nv | 11') F S exp (-nv) p(t-1).
where the second inequality follows from x S - and the last inequality from This concludes
[/(b)
2 2
F( S exp (-Tly F(.)
Since F()) R by the definition of R, after k:
1 log nj
3R iterations, F(l) &
holds.
(i)) Bound on 2,...,...,44 1- Let us define Ao the initial value of (W V,s)) V for 1, 1,..., T, when update V,, the kth outer iteration, where denote
LL == yr- Then, by Lemma D.7 and Lemma [.9 we have
Av (k)
2 A1
j+1, + VE)
<
for any 2 and I,..., n. We have
4R by Lemma D.12 By
using this bound, derive
(k) |
x
4.Ruux/ly +
2
vc
(
2
L-1-j
2 a
Ve
(14)
a
a
2
2
L
$ [Rmaxx]yy +
V(
(15)
2 - a
a
23

---

by induction. Indeed, hypothesis, holds that
(4 holds for = L with equality. Moreover, under the induction
Au (k)
2
A
(k)
+ +VE))
b-j
2
2
2
2
a
(Rmaax)/V
+
2 2-aa
Vt
12
ve (j-1)
2
Ve
4Rmaxt/y
2 a ve)
2
2
L.
2
Ve.
a
This concludes (14) for j 1 l....,, Then, by using Lemma D.8 we have
Pjápp S7 a² exp ( a²
16
-4 mick) ( 11o ( - v/l²
4 (2)
2 2
4 4Rmax//v
+
ve)
2
Thus,
log (2)
Ve ) #48 2)rmy
2
( 4 +
Env
2 -
a²e
gives Fj S 3(L-2)r) and hence, Pj S 3[L-2] by summing up Fj..p.
(II) Bound on Fi
By using Lemma D.Il
we have
(2 max |
Σ
Fiap S
exp -a 22 " (2) kim
| vil"
a2
1=1
Since Auj.) S [4RmaxTiV + 2-a
2 vo)()(() (2)
2- we have
((W(100) - V1 1|
2 Aellll +c)
S Σ
i=1
/2 2 2L
n 4RmaxlI +
2 vt
Thus.
(2 2L 382 max max 10 3r
1
hin
(2) log [Rmax'/v +
vc)
a2 a2227mhh
a?s²c
gives E Fi.i. S s for p = 1, ,....rr. This results in Fi En Ep Fi.i S 5.
,
(III) Summing up all have
By combining all, after K outer iterations and Ky and Kw inner iterations,
F=
F3
3
2)
3
j=1
==
Fr.
which gives the conclusion.
E Proof of Theorem 5.5
Here, we provide the proof of Theorem 5.5 the generalization error bound neural networks trained by Algorithm I
24

---

Proof of Theorem 5.3
By using the bound on u and supposed in Assumption 5.3 we have
f((u) ya By
S By +
(00......(.W))))). (Wyu)....
L II
S By + ph-1
|Wiuul
5=2
< By + 2 ||u||| I By + 2h
Hence, by taking M By + 2t pT. 1..11BB, Bx and R(F) as what derived by Lemma E.2 in Lemma E. obtain the conclusion.
Lemma E.1 (Theorem 11.3 in 123 For hypothesis class F and training data {( y: us define its (empirical) Rademacher complexity by
y:) Di ler
f(u) n
R(F) = sup JEF
where f(x) (f(x))..... ))
T and is a random vector whose each component independently takes value +1 with probability 2.- Suppose that [h(x) yl S M a.s. for any h E F. Then, for any 8 < with probability at least 1 ô over a sample, we have
Σ (1((a)) - y1)² + 2MR(F) - 3M² log(2/8)
E (2.9)~p
(1(x)) (1(())
-)
w)
T
2n
Lemma E.2 (Rademacher complexity bound). Let F be the class of neural network predictors obtained by Algorithm Then, the Rademacher complexity of F can be bounded by
4
R2
R(F)
<
+ -og
nvn
\/
with Ry = din (2r) 12r (log
To obtain this result, we apply the obtained bound on the spectral of W to the Rademacher complexity bound shown in as follows:
Lemma E.3 (Lemmaa A.8 in [8). Assume activation functions {a,())= such that each og is
Pi-lipschitz continuous and a (0) = O. Let us define
F foLWWoLL------ 01 (W.))....) [15
s By, 115 Sb (1 (13551)}
Then, it holds that
4
1
12 12
R(F)= < n
log
where R3 > O a constant defined by
3
R = || log(2r (logn)
(logg)
II Bips
Σ
Bj
Proof of Lemma
E.2
By applying Lemma E.3 with P and by. = 2, we obtain
PL 1. By 2, b, 2d,n. and
by 2r for j
h-1
$
Ry = | log(2r3)
4dim II (2r)
(2r)
Σ
j=2
j=1
|X|| log((r>) (log log(2r3)(
(2r) 3 = d (2r) ( 1 1og(2r (logm))
2
which gives the conclusion.
25

---

Proof of Theorem 6.3
F.1 Proof of Lemma 6.2
Proof of Lemma 6.2 First, we have [1]| [| the symmetricity, and the second equality follows from
||| |||lw=111 2.
The first equality follows from
W
[2]
2 E
[[
| + ||w- = E u+ 11 + [1] = ||||
w -- 11
2
where use | w+ [13] Blll | the last equality. Then, by using the concentration inequality argument (see Example 2.11 1 in [36 for example), we have
rt2
P |/0++ 1|
2 eexp
8
for any & E (0, 1). By letting
8log(2/6)
we obtain
8 (2gg(2/))
||++ 11?
<
2
Since the same argument holds with w., taking union bound concludes the assertion.
F.2 Analysis gradient descent with skip connection
We introduce the key idea of analysis with general notations similarly to Appendix D while there exists skip connection. Let us consider the regression problem with an objective
Fretu (w)
Σ Co(w xa) + wa - yo)
where w E Rdd is a trainable parameter. Let w' == w V En (aww ra) + wa - va)² where w' denotes the parameter obtained by a single update gradient descent with step- 26). E Roxd and Y = (yI...., 36) R². Then, Ea (a(w" xa) + Wa ya)² (o(Xw) + - Y holds and straightforward calculation shows w' =w- 2--22m(' D+ (ax) + w Y). where D = diag((o'(u 21)...., xx))).
size 77 > 0. Denote X
Now, we assume that there exists unique optimal solution w* satisfying Frei i.e. Y = (Xxw)) w". Then, we have
||w6 - w = || WWwFreiu w w01
||w w012 2 (re (w -w") +
and
Freta(( [ww (ww-w)
2(o(Xw) + wx") + 1)( ww)
=2((EX I)(W - - w0)l DX w²)
2(w w (x== (D + +[](w w²)
2/ "xx 2 + 2( - w²) x TEX (w - w²) + 2(w wx +D))( w (16)
where E is a diagonal matrix whose all diagonal components are within [0, 1], whose existence is guaranteed by the same argument as Proposition D.3 Then, we evaluate the right hand side. Lemma F.1. < D < I holds.
Proof. The assertion directly follows from o' d'(u) 1) for arbitrary e R.
26

---

Lemma F22 Suppose |X olop S 3. Then, the inequality 16
4 3 11 - w0 12 holds.
Proof. Since XDEX is positive semi-definite matrix, have
16 2 2 == x DX op
llw. w0
2 1 3) 11:0 - w" 2 3 I - w01l
which gives the conclusion.
Besides the lower bound
16 have the upper bound of the gradient
V Fretu (w) [ 1 |2x D(a(Xw) + |
(17)
< 4Amax ((DD) T (XD + () -
where
mma ((XD 1)" (XD +))
the largest eigenvalue matrix (XD+ I) (XD+ I).
Moreover, we provide several lemmas, which we utilize in the proof of Theorem 6.3
Lemma F.3. Suppose ||W] op S and V 2 O. Then, if (WW) + V - 2'I S then
49
||V - (V)
( v'12 v
9
Proof. Since a (WV) 0 and V 0, we have
<2 (2llo(VV) V v Σ [o(WV) +V, V 2 Σ (v,)==|V V
<,<0
which gives the first conclusion. The second follows from
||o (W())) + v'll
o(WV) - (V)+ lo +V -V
$ ( -| lo +V l
[[ + + + 2
3 7
7
where we use the triangle inequality in the first and second inequalities, and I-Lipschitzness of the ReLU activation in the third inequality.
Lemma E4. Suppose that (0) satisfies a (WV + v(0) - V =: Av and V satisfies a (WV*)
V* V", [f| L, it holds that
-v
5 1 W|
1
Aull
Proof.
We have
| = (W + v(0) - v
OW (0)) + (0)) -(WV))- vill
((0) V
- -o(V))) |
((0) V
W(V -vo
((0) V
| om ((0) v-l
W 1
| -- vl]:
where we use the the triangle inequality in the first inequality, the 1-Lipschitzn continuity of ReLU activation in the second inequality. Dividing each term by ||lloop gives the conclusion.
D
27

---

E33
Preliminary Results
Lemma F. (Regularity weight matrix W, during training). For 2.....L 1W S
always holds during the training.
Proof. By Lemma D.5 suffices show that every of W satisfies || S 12 where Aw denotes the difference between w at the start and end of the training by the same as the proof of Lemma D.4
To this end, we prove | S
12 This follows from
(1) MW VV +V
2n r [[diag(((wVV) (o(w)) +V
S 21w
(1) re (VVT) ([((w]) + V - -VII
3 1.
S 2TW ylOv - TI
S
2
12K VT
where the last inequality follows from the definition of 1/
Lemma F6 (Bound on Au at the output layer). Let Rg = w, (())
1--1, y/ Then, we have
||
1-1,1
4RMm..
Proof. Since v--1] 2 0, we have
((()) 1-1,2 - 1,
1)
(k--1)
1-1,8 - 2112 Wv WW. 1- - Vi WT.) - v(k-1)
(V/ - 2n1v (W (b-1))
1--1, Wi Wv. - ((-1))
1 (WL (K) (((-11)
1-1,s w/) L.
20V
[/(3/ lpp
|w(h (
v y/
s 4nv
[ (0) (0)
1-1, y/ = 4ny R.
which gives the conclusion.
F.4 Proof of Theorem 6.3
Proof of Theorem
6.3
We follow the similar argument that of Theorem 5.1
Let consider the
decomposition
F as
L-
L- Σ
F=
Σ F3= = Σ
FL, + y
Fj
j=1
i=1
j=1 p=1
where
n FL Σ
= (WLVL-1, - 31)
F
and
Fj... = (o(W,Vs-L.), + (VS-15)p (V5-1s)p-(V33))))
Fj =
Fj..p
for j 1,...,,. 1.
28

---

(I) Bound on Fz described by
We only need to consider the case W - V/ # 0. The update of V2-1,6 is
VL-1,1 (VI-1! -27 (WLV Vi WL) +
=V2-1, 2n (WL 1- y0)
where we define v = (W (/--1) 1111; - -w:)) ( - v/ Then, we have
W 1-11 yi (1- 2 Wi.) (Wa VV 116)
Then, we show an inequality
② T Wz 2 min ||++1 ||= 1
(18)
First we consider a case W2 V 1-1
(k-1)
> 0. In this case, we have
(2nl (Wr. W - -3:) 31)2i)) 20)
= ((v 2TT (Wr 1 (W2
- ) v
v1
2nv
(W,V W. (k-1)
1-1,3 -M/ 11)) (WE)s ifj = { (WW) s =0]
W Wy
(WL)s ifj J2 = {1l (WD), > and v((-1)
> 211 (W W/LW
L-1, - v1 w.)
2n1
1-1,1
1-1,3
otherwise.
This gives
w
T Wr. Σ (w))((())
21v (WiVZ-T!! - -vi) -1 (v (Wr));
Σ (Wn.)++ +
Σ
JEJIUJ2
jE(Juu))
2 Σ (Wn,)=1lw-11
= 1|"-
(19)
JEJ1
where in the inequality we use (v(A-,)) > 0 and (WL), > for (J1 U.2.
If WW (K-1) 1/ y1 < 0. it holds that
27/
Wr, 11 -v:) )
(k-1)
20
Wy, Wr. V' (1-
1/1 (Wr)s ifj = [11 (WL),, 2 20). - 1/i (Wr),
Wr, W/ 1-11
(1-1)
if i (Wr), < and L-1, > 21v (Wi v. (WW1)))
2nv
(((k-))
b-1,()
otherwise.
This gives
T T WT = Σ (WL),
j=1
Σ (Wi)} +
Σ
2TV
(WLV (k-1)
L-1,8 -11) -1 "(((tt=)) (Wa),
jEJNU12
JE(J)W)))
2 Σ (WL) = -1|++12,
(20)
JEJ1
29

---

where in the inequality we use (Vi-I!) and (WE), for (J1 J2) The two bounds
(99 and 20 conclude (18).
This results in
L, 2 (1 - 2 T W1)
2 FE, ((--1)
W1) ((k-1) I exp - 4nv min I|+ 11?, ||==112] 11] F(t="1
where the second inequality follows from 1 - x. S e and the last inequality from 18). This concludes
(b) S exp
exp((4nn (-4nv min || 11? -|, ) Ft
Since F R by the definition of R, as long as we set 1J I 2mi [|0 11. w [1}] after =
log 3RR)
iterations, FL (k)
3 holds.
4ny min |00 11 F/
(II) Bound on Fj (j = ,,..,, 1-11 Let us define Au as the initial value of oW Vg,)) -
Vys - Vi+1. for j 1.....
when we update Vg, at the kth outer iteration, where we denote
VL, = yr. Then,
A J,
(k)
- 2n/v R² holds and Lemma F.4 gives
Auja (k)
WW (| (K) + vt) +es
(| 3vc)
S
By these inequalities, we can ensure
Au (k) < (4Rmax + 5vE)
3 2
by taking in 14). By the observation in Appendix F22 for each j, let v" E R" be solution of o aW (W5+10") + o" VJ+1, = 0. Let (V(kst))
J Je.. sequence generated by the gradient descent. Then, holds that
|| | - ||
(21)
= -1| 0-
27 Vv FV (v(nt)) -00) + + Vv (V
For the second term, Lemma gives
4 VvE (v( 2 ((kin) -
3
For the third term, 17 gives
VvP (V
5 mmxax (W (W 1) (W (W 1)) |W
+ v(kin) Vs+e.
< 4. (IW op +1) 2
O(W ,-1 V(kin)) -o V(kin) -0- 1/12
4
[ ((WW)i -o(Ws+1u*>/ + ||((ken)) |||+++||eeww -|
0²1 00((()
4.
+1 1
2
128
1)|
((kkn) v-|
1280
((kkm) -br| 1- 1pp vollvvl _ =
<
+
1
9
81
30

---

where we use (a b)2 - 2(a² + b²) in the third inequality and [WW++ll S 3 in the third and fourth inequalities. Then, by substituting these bounds to 21 we obtain r (1int))
V (Menn) 10
7/ ((hw) - -01l" + +16,21 ((hm)) -001
|(lknn - 10
3 nT 6ym)) / - v0//
2
(((k))) 1-1 - (1=1==113)00)0 -m/
3 mm ) r |((kw) - -201
< ((hm)))
3
where we use 7V S 127
I
in the second inequality.
This results in
((kenn) 0z 1| 3
4 mn
Rin [(w)- w²1 S exp
3 m Kion |200 =
4
- I S exp((= -x) in the last inequality, and hence, where we use
lo No(W,+ (o(W+z1Vlln)) + ((Hen)) Vi+a. || 2 1 [(Him))
1
10112
20
||110) 0²
s exp
9
20
9
A (8)|1
s
exp
9
(4Rmax + 5 2 2 22 2
4 7 Kin
$ exp
where in the third inequality, we use
|v (k)
V(0) -²Il, following from
Au
W j+1 v())
+ (0)) o(W - 0²
v(0) v0
0 W (W)=-r00 o(W ,(W
((0) v²
|| ((0)- - -01|
ス 2 3
V(0) 0*
Hence, by taking kin
log (4RmaxlTv + 5)))2(2) 21 2-
we obtain Fj,
4ynv
3x
49. I. 2)rn Then, Lemma
36
F33 gives FjJ I 3(--2jmn after the non-negative projection (line
10
is applied.
(ii) Bound on Fj The update of W, is same what we considered in Theorem 5.1 (Alge (Algo- rithm T by setting a t= 1. Therefore, by using Lemma D.11 we have
F exp --m (2)1 1:
(w - vi
12x1122112
(3) 2L
exp -())k))))) (4Rmax"Iv + 5VE)²
2
1. Smmxx |Ix:
Thus, h:
ray log
(4Rmaxe + (50)(3)
gives Fi S 5-
32mp
(III) Summing up all
By combining all, after K iterations and Kv and Kw iterations, we have
L-1 F
4-1
F=
Σ F Σ
3 - 2)rn
rnc +
3 =
1=1
1=2
which gives the conclusion.
31

---

G Additional Experiments on Deeper Architectures
We conducted additional experiments evaluate the scalability of the proposed BCD algorithm on deeper networks trained with the LeakyReLU activation (a = 0.5). Networks with depths 4, 8, and 12 were trained on the same synthetic dataset and with the same hyperparameters as in Section 7.1
Figure illlsstaate the training loss trajectories for each setting. As expected, deeper architectures exhibit slower initial convergence due to increased optimization complexity. Nevertheless, the loss consistently decreases over epochs for all depths, demonstrating that the proposed method remains stable and effective even for substantially deeper models, in agreement with the theoretical convergence results presented in Theorem 5.1.
10
10 2
loss
10-4
L=4
L=8
10
L=12
1000
2000
3000
4000
epoch
Figure 4: Training loss curves for networks of depth T. 4, 8, and I. 12.
32

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA]-
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1 (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked While "[Yes] " is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providded a proper justification is given (e.g., "error bars expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
the checklist one of the factors in their evaluation.
reported because it would be too computationally
"[No] " or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer often more nuanced, so please just use your best, judgment and write justification elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims in the abstract and introduction-suuce as provable convergence of
BCD to global minima, extension to ReLU networks, and generalization guarantees are explicitly supported by theoretical results (Theorems 5.5 (..3 and empirical evidence (Section 7
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
33

---

Answer: [Yes]
Justification: Section discusses the limitations of extending the convergence guarantee ReLU due its non-monotonicity, requiring modifications like skip connections. Ap- pendix B also notes challenges when using non- non-monotonic activations or more general loss functions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the puper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faireess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The paper clearly states assumptions (c.g., Assumptions 3.1 3.2 and 5.3) and
provides formal proofs Appendix for the theoretical results in Sections 4 and
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
34

---

Answer: [Yes]
Justification: Section 7 outlines the network architecture, activation functions, data genera- tion process, hyperparameters (e.g., step sizes, number of iterations), and settings for each experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis-
sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: While the main paper confirms reproducibility through detailed descriptions, code and data are to be released in the supplemental material, consistent with NeurIPS anonymization guidelines.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
httii///uuiiee//eeuuimessse public/ wwblic/guides/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips https//..wcp/pooeeeeee////////ss
for more details.
35

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
reproducible, they
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section provides a comprehensive description of hyperparameters, dataset construction, network configuration, and training loop setup for both activation types.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Section 7 includes comparisons of training loss curves across different settings (e.g., with and without singular value bounding skip connections), and reports consistent behavior across runs, effectively supporting the statistical significance of the observations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
36

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiment??
Question:
Answer: [Yes)
Justification:
The experimental setup, including compute resources, described Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tte::///eeuiss// http:///urrass.cpppcl///tttcieee cc/ppublccttthiccsuddellll...a.d
Answer: [Yes]
Justification: The work does not involve sensitive data, human subjects, or deployment concerns and aligns with ethical principles described in the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Sections and 8 mention that the theoretical insights into optimization and generalization may benefit the understanding and reliability of deep learning. However, broader societal implications (e.g., misuse) are not discussed in detail.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
37

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The proposed methods not pose high risk misuse.No pretrained models scraped datasets are used.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-uss should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The experiments use synthetic data and code developed by the authors. No external assets are reused.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the sesrrswithhodee package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The paper introduces new algorithms (Algorithms) I and 3 which are clearly specified in pscudocode and supported by theoretical analysis and empirical results.
Guidelines:
38

---

The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The work does not involve any human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The study does not involve human participants, hence IRB approval is applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not use large language models the methodology or experi- mental pipeline.
Guidelines:
39

---

The answer NA means that the core method development in this research does not involve LLMs as any important. original, non non-standard components.
Please refer to our LLM policy (https://neurig: /ttp://pp.ccc//offfeeeee//////// for what should or should not be described.
40


Reviews:
[{"review_id": "VVtayw0DKN", "reviewer": "Reviewer_St1t", "summary": "This paper studies block coordinate descent (BCD) applied to deep neural networks with strictly monotonically increasing activation functions. It claims to be the first theoretical results proving a convergence to global minima with arbitrarily many layers without NTK. It provides a theoretical generalization bound analysis assuming iid samples. The paper further modifies (BCD) (by incorporating skip connections and non-negative projection steps) so that the corresponding analysis extends to networks using ReLU activation.\nBCD is formalized so that each layer of the neural network is treated as one block, and additional auxiliary variables are introduced corresponding to each pair of (input, layer output). A small numerical experiment is performed.", "questions": "see strength and weaknesses.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- the paper is very well written\n- global convergence of any neural network training is a valuable analysis, and this is corroborated by numerical experiments\n\nWeakness:\n- the paper assumes the number of data points $n \\leq d$ the number of dimensions, which is non-standard\n- the re-formulation of the objective leads to a blowup in the number of variables. And in fact, it is not clear to me why on page 7, line 218, you have that the total number of gradient computations is $\\tilde{O}(\\log^2(1/\\epsilon))$ without a dependence on $n$.\n- On page 5, lines 172-176, you discuss the role of SVB as a heuristic but not in sufficient detail. Is there a formal discussion of why the singular values of $W$ should remain bounded throughout training? Based on the numerical experiment, it looks like loss plateaus above $10^{-4}$ without SVB, suggesting that this is in fact a crucial step for ‘fast’ convergence. Could you add a longer discussion or additional experiments?", "was_revised": true, "final_justification": "The authors did a good job addressing my concerns. I am not an expert in this topic--to me, the contribution seems sound technically, though perhaps practically limited. I have kept my original score.", "rebuttal": "We sincerely thank the reviewer for the thoughtful and detailed feedback.\nWe would like to address your concerns here.\n\n**Assumption $n\\le d$ and Practicability**\n\nWe appreciate your pointing out a limitation of our results. \nAs we stated in Section 2, we consider the high-dimensional settings where the dimensionality is larger than the sample size, which may not be suitable for several applications. \n\nOn the other hand, Assumption 2.1 is required for the global convergence of BCD. \nWhen optimizing $W_1$, we solve the equation $\\lVert\\sigma(W_1X)-V_{1}\\rVert^2=0$, where $V_{1}$ is a matrix whose $j$-th column is $V_{1,i}$. \nIf $X$ is not full-rank, we can no longer ensure the existence of $W_1^*$ satisfying this equation, which is why we impose this condition. \nTo the best of our knowledge, this assumption is inevitable when we consider the backward procedure. \nAddressing this point is a significant future direction for our results.\n\n**Gradient Complexity and Dependence on $n$**\n\nWe appreciate you pointing out the confusion regarding the complexity estimate around line 218.\n\nThe expression $\\tilde{O}(\\log^2(\\frac{1}{\\epsilon}))$ written there was meant to highlight only the dependency on the target accuracy $\\epsilon$, not to reflect the complete computational cost. \nIn reality, when including the number of auxiliary variables, which depends on the number of training data and layers, the total number of gradient computations is described as $\\tilde{O}(nL\\log^2(\\frac{1}{\\epsilon}))$ since the updates of all auxiliary variables $V_{j,i}$ for $j=1,\\dots,L-1$ and the weights $W_j$, particularly $W_1$, require $\\tilde{O}(\\log^2(\\frac{1}{\\epsilon}))$ iterations.\n\nNote that this overall complexity remains comparable to that of standard backpropagation-based methods, especially considering that BCD allows for decoupled and potentially parallel updates.\nWe apologize for the confusion and will revise this part in the revised version to provide a more precise and comprehensive complexity statement.\n\n**Role of SVB (singular value bounding)**\n\nWe thank the reviewer for their thoughtful request for a more detailed discussion of Singular Value Bounding (SVB).\n\nAs described in lines 172–176 and further evidenced by the ablation experiment in Figure 2, SVB stabilizes training by bounding the singular values of each weight matrix.\nApplying SVB is not only motivated by heuristic considerations but also utilized to ensure global convergence in Theorem 5.1.\nBounding the singular values helps maintain a favorable condition number of the hidden layer loss $\\lVert\\sigma(W_jV_{j-1,i})-V_{j,i}\\rVert^2$. \nWhile SVB is only applied at initialization in our algorithm (unlike in [Jia et al., 2017]), our theoretical results ensure that the singular values remain bounded if the step sizes are chosen appropriately (please see Lemma D.4 in the supplementary material for details).\n\nAlthough these considerations were omitted in the original manuscript due to space constraints, we will include a more comprehensive discussion in the revised version to clarify the theoretical and empirical significance of SVB, particularly its essential role in ensuring convergence.\n\nWe appreciate the reviewer’s overall positive assessment and insightful suggestions, which we believe will strengthen the clarity and impact of our work."}, {"review_id": "Uecosj7IIz", "reviewer": "Reviewer_8M2p", "summary": "This paper proposes a block coordinate descent algorithm for training deep neural networks by reformulating the standard training objective with auxiliary variables that represent the activations at each layer for each training sample. This lifted formulation allows the optimization problem to be decomposed into simpler subproblems over weights and activations, enabling alternating updates. The authors prove that, under several assumptions on data rank and network width, their method converges to global minima of the objective function, with guarantees provided for both bijective and certain non-bijective activation functions.", "questions": "1. Why do the authors aim to achieve zero training loss under relatively strong assumptions, given that perfect fitting is often unnecessary in practice?\n2. Although some BCD variants modify the block-wise objective for simplified updates in practice, could the authors explain why the update for $V_{j-1,i}$ considers only one of the two relevant terms in the original objective?\n3. How can we handle the extra memory overhead of $V_{j,i}$'s? While GPU parallelism may alleviate the issue, could the authors provide extra analytical or experimental evidence to support its practicality?\n4. The authors explicitly mention the use of skip-connections as in ResNet in Section 6, but the corresponding experiment is still simple (see weakness 5). Could the authors consider adding experiments on real-world tasks with deeper networks?\n5. Please address the minor issues to improve paper quality.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. The paper introduces a lifted optimization formulation that decouples layer-wise computations using auxiliary variables, enabling a principled application of block coordinate descent to neural network training.\n\n2. The convergence analysis is rigorous, showing that the proposed method reaches global minima under several assumptions, and accommodates both bijective and certain non-bijective activation functions.\n\n3. The authors derive a generalization bound based on Rademacher complexity, showing that the learned model exhibits provable generalization ability under norm and width constraints.\n\n4. The experimental results on a synthetic dataset support the theoretical claims for both bijective and certain non-bijective activation functions, and the ablation studies highlight the necessity of key assumptions in ensuring convergence. Experiments are reproducible with the provided codes.\n\n**Weaknesses**\n1. The paper focuses on achieving zero training loss through a carefully constructed optimization framework under several restrictive assumptions, such as the invertibility of the hidden layer matrices $W_2, \\cdots, W_{L-1}$ and wide first layer $W_1$ (The authors assume $n\\leq d_{in}$). However, these conditions may be unrealistic in practical settings, where perfect fitting is neither expected nor necessary for good generalization.\n\n2. The update of $V_{j-1,i}$ deviates from the standard BCD principle by considering only one of the two terms in the objective involving this variable. Specifically, the update minimizes $\\|\\| \\sigma(W_j V_{j-1,i}) - V_{j,i} \\|\\|^2$ but ignores the term $\\|\\| \\sigma(W_{j-1} V_{j-2,i}) - V_{j-1,i} \\|\\|^2$, which also depends on $V_{j-1,i}$. This partial update may simplify computation but is not a full block minimization step, and the paper does not provide a clear justification.\n\n3. The introduction of auxiliary variables $V_{j,i}$ incurs non-negligible memory overhead, as it requires storing separate variables for each layer and each data sample. Even if one can leverage GPU parallelism to reduce memory usage, this extra cost remains significant in large-scale deep learning applications such as training LLMs.\n\n4. The paper discusses how the proposed framework can be adapted to handle non-bijective activation functions, such as ReLU. This extension is valuable, but it would be better if the approach were formalized in a more general way without relying on a specific example.\n\n5. The authors critique prior work for being limited to shallow architectures, typically with *two* or *three* layers, and emphasizes that the proposed method can in principle handle networks of *arbitrary depth*. However, the experiments are only conducted on a network with *four* hidden layers. It would be helpful to evaluate deeper architectures to better demonstrate the method’s practical scalability.\n\n6. Minor issues:\n- Please use vector graphics for Figure 1.\n- The contributions are summarized too long, please make them concise.\n- Line 178 tells that the algorithm applies multiple iterations per update for V, is it possible that Lines 3 and 4 in Algorithm 1 miss an inner loop?", "was_revised": true, "final_justification": "The authors have provided clarifications and additional context that address several of the raised concerns, and have outlined reasonable directions for relaxing assumptions, extending the update rules, and broadening empirical validation. While these enhancements would strengthen the work, they are nontrivial and would require substantial effort. Overall, the paper presents theoretical contributions with clear potential for further development.", "rebuttal": "We thank the reviewer for the constructive and thorough feedback. \nWe would like to comment on your concerns here.\n\n**Restrictive Assumptions and Invertibility of Hidden Layers (Weakness 1, Questions 1)**\n\nThank you for pointing this out. We agree that the algorithm may appear restrictive due to assumptions such as the invertibility of hidden layer weight matrices and the attainment of perfect fitting. \nHowever, we emphasize that our theoretical framework is aligned with the conventions in the literature on regression tasks using neural networks, particularly those involving NTK or mean-field analyses, where convergence to zero training error is standard and serves to understand the optimization dynamics in a rigorous setting.\n\nThat said, we also acknowledge that relaxing some of these assumptions is feasible and worthwhile. \nIn particular, the condition $n\\le d$ could be relaxed without undermining the core structure of the analysis when we do not require perfect fitting.\nOn the other hand, the use of Singular Value Bounding (SVB) is not merely a theoretical tool—it is empirically validated in our experiments (Section 7)  to improve convergence stability and speed significantly.\nThus, even in practical settings, SVB will remain an effective and relevant component of the proposed method.\n\n**Update of $V_{j,i}$ (Weakness 2, Questions 2)**\n\nWe appreciate the reviewer’s observation regarding the partial update of $V_{j-1,i}$.\nAs noted, our current formulation focuses on the loss term involving $\\lVert\\sigma(W_jV_{j-1,i})-V_{j,i}\\rVert^2$, while omitting the preceding layer’s term $\\lVert\\sigma(W_{j-1}V_{j-2,i})-V_{j-1,i}\\rVert^2$ from the update of $V_{j-1,i}$.\n\nThis choice is made purely to simplify the theoretical analysis and algorithmic presentation. \nTechnically, incorporating both loss terms into the update of $V_{j-1,i}$ is feasible: the omitted term is a convex function in $V_{j-1,i}$, and it does not involve any nonlinear or parameterized transformation of $V_{j-1,i}$.\n Thus, extending the update rule to minimize both terms jointly would not introduce significant analytical challenges.\n\nIndeed, we believe that an update scheme involving both terms—i.e., a more complete BCD step for $V_{j-1,i}$—is a promising variant. We plan to mention and briefly discuss this extension in the revised version of the manuscript.\n\n**Memory Overhead and Auxiliary Variables (Weakness 3 and Questions 3)**\n\nAs the reviewer mentioned, it is correct that storing adds memory overhead. \nHowever, this is a trade-off for achieving decoupled layer-wise optimization and theoretical convergence guarantees. \nThe memory burden can be mitigated using batch-wise updates or recomputation strategies, akin to those used in backpropagation through time or gradient checkpointing. \nAdditionally, as noted in Section 4, these variables enable significant parallelism, particularly valuable for distributed training and hardware acceleration.\n\n**Clarification on ReLU Extensions (Weakness 4)**\n\nWe appreciate the insightful comment. \nWhile our convergence analysis for non-objective activations (e.g., ReLU) is demonstrated through a specific ResNet architecture with skip connections and fixed output-layer weights (Algorithm 3), this choice was made to enable rigorous theoretical guarantees in the presence of non-strict monotonicity.\n\nThat said, we stress that our approach is not limited to this particular design. \nAs elaborated in Appendix B in the supplementary material, the block coordinate descent (BCD) framework we develop is flexible and can be extended to a wide range of settings, including:\n\n- alternative activation functions (including those violating strict monotonicity),\n- general loss functions such as cross-entropy,\n- regularized objectives.\n\nIn this broader context, the skip-connection-based formulation serves as a concrete instantiation to demonstrate the viability of global convergence even for ReLU networks. \nHowever, we see the development of more general treatments for non-objective activations—possibly without architectural constraints such as fixed weights or skip connections—as an important and promising direction for future work. \n\nSection B outlines several such avenues, including projection techniques for bounded activations like sigmoid or tanh. \nWhile our current analysis focuses on one specific architecture to make convergence guarantees tractable, the underlying methodology lays the foundation for broader generalizations, and we regard this as a key future research opportunity.\n\n**Experiments with Small Architectures (Weakness 5, Questions 4)**\n\nThank you for the valuable comment. \nAs the reviewer rightly noted, most existing theoretical convergence analyses are limited to two or three layers. \nTherefore, we believe that conducting experiments on 4-layer architectures already represents a meaningful advance over prior work and appropriately reflects the theoretical contributions of our paper.\n\nThat said, we fully agree on the importance of evaluating deeper architectures. We plan to conduct additional experiments on networks with greater depth, both in synthetic and real-world settings. \nThese results will be included in a future revision of the paper to support the practical applicability of our method further.\n\n**Minor issues (Weakness 6, Questions 5)**\n\n- *Vector Graphics for Figures*: We will provide a vector-format image for Figure 1 to enhance readability. \nWe appreciate this suggestion.\n- *Summary Conciseness*: We appreciate the feedback and will revise the summary to be more concise.\n- *Algorithm 1 Inner Loop Clarification (Line 178)*: Thank you for pointing this out. To clarify, the update strategy in Algorithm 1 is indeed correct as written.\nFor the final hidden representation $V_{L-1,i}$, only a single gradient step is performed per iteration, while the hidden layers $V_{j,i}$ for $j<L−1$ are updated multiple times using inner loops. \nThis asymmetry is intentional and theoretically justified in our convergence analysis (see discussion in Section 4 and Lemma D.6 in the supplementary material).\nWe acknowledge that the explanation in Section 3 has caused confusion regarding the update schedule of $V$. \nIn particular, the description does not sufficiently emphasize the difference in treatment between the output layer and the others. \nWe will revise this part in a future version.\n\nWe thank the reviewer again for the detailed critique. \nWe hope the above responses clarify the contributions and address the concerns."}, {"review_id": "nhAhc1sQsR", "reviewer": "Reviewer_A53r", "summary": "This paper studies the convergence property of block-coordinate descent on deep multi-layer perceptrons. The primary focus of the paper is on activation functions with derivatives bounded from above and below by positive numbers. By rewriting the objective into layer-wise components, the paper shows a linear convergence of the training error. Moreover, the paper also provides a generalization bound based on the Rademacher complexity. The paper also extended the theory to ReLU activation by adding skip connections. The paper provided experimental result to demonstrate the layer-wise loss dynamic under both the strictly monotonic activation and the ReLU activation, which shows that on the re-written objective, the ReLU network without skip connection does not achieve a favorable loss.", "questions": "None.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\n1. The theoretical contribution of this paper is quite comprehensive: the paper covers both the training convergence and generalization property. The analysis is on standard MLP with strict monotonic activation, but is also extended to ReLU activations by adding skip connection. Lastly, it seems that the paper also has an extension to the case of output dimension greater than 1.\n\n2. The convergence guarantee is strong in the sense that it is a linear convergence to arbitrarily small training loss. The assumptions on the neural network structure is fairly relaxed since it does not require a significant over-parameterization.\n\n**Weaknesses**\n\n1. The primary concern I have about the paper is that it deviates from the standard way of training neural networks. Traditional block coordinate descent should be simply update layer weights separately. By re-writing the objective, the algorithm requires the optimization of both the hidden-layer outputs and the neural network weights, to enforce alignment between the two. It is not clear whether this algorithm has practical applicability. On the other hand, the paper also lacks experimental support to show that the behavior of the algorithm considered in this paper is similar to the behavior of traditional coordinate descent. Therefore, there might be possibility that the paper offers limited insight into algorithms people use in practice.\n\n2. The generalization bound seems to be quite large given that it scales as $(2r)^\\frac{L}{2}$. Also since rank$(X) = n$, it is necessary that $d\\_{in} \\geq n$. Moreover, based on the standard matrix concentration result, for $X$ with I.I.D. entries, we have $\\\\|X\\\\| = O(\\sqrt{n})$. Therefore, the first term in the generalization gap's bound may not decrease with $n$ under a lot of input data.\n\n3. The experiments are conducted only on artificial data so it remains doubt whether the same behavior can be carried along to real-world applications.", "was_revised": true, "final_justification": "Mybiggest concern (about the generalization bound) is resolved in the author's rebuttal. I believe that the author's point regarding the practical applicability of the algorithm is reasonable, and the author has promised to add the discussion in the camera ready version.", "rebuttal": "We thank the reviewer for the thoughtful review and for recognizing the strength and comprehensiveness of our theoretical contributions.\nWe would like to comment on your concerns here.\n\n**On Deviation from Traditional Training and Practical Applicability (Weakness 1)**\n\nWe agree that our algorithm deviates from standard backpropagation. \nWe intend to propose a theoretically sound alternative that may inspire new algorithmic designs. \nAs explained in Section 3 and illustrated in Algorithm 1, our approach uses auxiliary variables to decouple the optimization of hidden layers and weights, enabling global convergence proofs for deep neural networks with an arbitrary number of layers outside of the NTK regime (Theorem 5.1) and a generalization error bound (Theorem 5.4).\nSuch a theoretical tractability will be helpful in applications where interpretability, formal analysis, or convergence guarantees are critical (e.g., safety-critical ML, robust training, or model verification). \nWhile this structure is non-standard, it allows for parallelism and layer-wise optimization, which could benefit certain distributed or hardware-constrained settings. \nWe would like to add a discussion about potential practical scenarios in Section 7 and will further clarify this in the revised manuscript.\n\n**On Generalization Bound Scaling (Weakness 2)**\n\nWe appreciate that the reviewer raises a significant concern regarding the dependence of the generalization bound on the number of layers, particularly the $(2r)^{\\frac{L}{2}}$ scaling. \nWe would like to clarify that such exponential dependence on depth is not uncommon in norm-based generalization bounds, such as [Bartlett et al., 2017], which we utilize to derive Theorem 5.4, where similar depth-related dependencies arise due to layer-wise norm products. \nOur goal is to offer a principled, analyzable framework, and our bounds align with the established literature in this regard.\n\nThat said, we agree that improving this dependence is essential.\nRecent advances using compression-based (such as [Arora et al., 2018]) or information-theoretic approaches [He et al., 2023] show potential to yield tighter bounds with more favorable dependence on depth.\nExtending our analysis in this direction is a valuable avenue for future work.\n\nRegarding the dependence on the input norm $\\lVert X\\rVert$, we note that simple preprocessing steps such as input rescaling or normalization can effectively control this term. \nIn practical applications where the labels are bounded (e.g., $O(1)$), this does not pose a significant limitation from a representational standpoint.\nWe will clarify these aspects to avoid misinterpretation of the bounds' applicability in the revised manuscript.\n\nS. Arora, R. Ge, B. Neyshabur, and Y. Zhang. Stronger Generalization Bounds for Deep Nets via a\nCompression Approach. In Proceedings of the 35th International Conference on Machine Learning, 2018.\n\nHe, C. Yu, and Z. Goldfeld. Information-Theoretic Generalization Bounds for Deep Neural Networks. In NeurIPS 2023 workshop: Information-Theoretic Principles in Cognitive Systems.\n\n**On Real-World Applicability (Weakness 3)**\n\nWe appreciate you raising the concern about real-world applicability. \nIn Section 7, we chose synthetic data to highlight specific convergence behaviors predicted by our theory under controlled settings. \nThese experiments confirm the layer-wise dynamics and the impact of activation functions as theoretically predicted. \nWe acknowledge that broader empirical validation on real-world datasets would strengthen the paper, and we are actively working on this for future extensions.\n\nWe hope this clarifies the motivation and scope of our work. \nWe believe the theoretical insights offered are valuable for understanding deep learning optimization, and we appreciate your feedback to help improve the manuscript."}, {"review_id": "buEUMWjZ5v", "reviewer": "Reviewer_CnMC", "summary": "This paper provides a theoretical justification for the global convergence of a custom Block Coordinate Descent (BCD) algorithm applied to deep neural networks with more than two layers. In their formulation, the algorithm introduces auxiliary variables $V_{j,i}$, which approximate the outputs of each hidden layer and allows the optimization problem to be decomposed into layer-wise subproblems. Under assumptions including i.i.d. data, full-rank input, and strictly monotonic activation functions, the authors prove global convergence to zero training loss. They also extend their framework to accommodate ReLU activations by introducing a residual network structure with skip connections and non-negative projection operators. Additionally, they show justification for a generalization error bound, showing that the difference between training and test error of their approach remains small with high probability.", "questions": "Could this approach potentially be extended to handle other non-strictly monotonic activation functions beyond ReLU? \n\nWhat would be the practical applications of this approach be?\n\nCould you provide a more explicit discussion of the time and memory complexity of the proposed BCD approach?", "limitations": "Yes, as they mention the assumptions needed in order for their justifications to be true.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "This paper provides a theoretical analysis of a custom Block Coordinate Descent (BCD) algorithm for training deep neural networks with more than two layers. It justifies a global convergence guarantee outside of frameworks like RKHS and NTK, where previous work often allows minimal parameter movement. The authors show global convergence under a more dynamic optimization regime, using auxiliary variables and assuming monotonically increasing activation functions. However, there is not much experimental validation, as they rely on synthetic data generated from a teacher network and do not empirically verify the claimed generalization bounds. Additionally, while the theoretical results are interesting, the proposed algorithm does not seem very practical for larger applications due to its reliance on multiple nested updates and restrictive assumptions on data structure. So while this paper provides an interesting contribution to the theoretical understanding of optimizing models, its practicality is limited.", "was_revised": true, "final_justification": "I was initially on the fence about the paper, but the rebuttal has addressed most of my concerns. As a result, I am inclined to raise my score.", "rebuttal": "We thank the reviewer for the constructive feedback and for acknowledging the theoretical novelty of our work.\n We would like to comment on your concerns here.\n\n**On Practical Applicability and Experimental Validation**\n\nOur primary goal is to provide the first provable global convergence guarantee for block coordinate descent (BCD) applied to deep neural networks.\nAs we mentioned in the paper, to the best of our knowledge, this is the first result that ensures the global convergence of deep neural networks with an arbitrary number of layers outside of the NTK regime.\nAccordingly, our theoretical framework focuses on optimization and generalization rather than large-scale empirical benchmarking. \nTo complement the theory, we included experiments on synthetic data (Section 7), which confirm our theoretical predictions and highlight the behavior of the training loss under both strictly monotonic and ReLU activations (Figures 2 and 3).\n\nAs emphasized in Appendix B in the supplementary material, our framework is extensible to general loss functions and classification tasks. \nWe plan to include broader empirical results on real-world datasets in a future version to reinforce the algorithm’s practical relevance.\n\n**Scope of Activation Functions**\n\nThe current convergence analysis (Theorem 5.1) is based on the strict monotonicity condition stated in Assumption 3.2, which notably excludes activation functions such as ReLU. \nAddressing activation functions that violate this assumption presents a key challenge: their outputs are confined to bounded ranges. \nFor instance, the sigmoid function satisfies $\\sigma(u) = \\frac{1}{1 + \\exp(-u)} \\in (0, 1)$, and the hyperbolic tangent function satisfies $\\sigma(u) = \\frac{\\exp(u) - \\exp(-u)}{\\exp(u) + \\exp(-u)} \\in (-1, 1)$.\n\nIn such cases, it becomes crucial to ensure that the auxiliary variables $V_{j,i}$ remain within the output range of the corresponding activation function (see the paragraph titled **Activation Violating Assumption 3.2** in Section B for further discussion). \nFor the ReLU activation, which produces only nonnegative outputs, we extend our algorithm by incorporating skip connections and nonnegative projections. \nThis modification leads to a novel convergence result presented in Theorem 6.3, supported by Lemmas 6.1 and 6.2.\n\nLooking ahead, techniques such as range-aware projections or bounded initialization may offer viable strategies for extending the block coordinate descent (BCD) framework to bounded activation functions. \nExploring these directions constitutes a promising avenue for future research.\n\n**Practical Use Cases and Applications**\n\nOur work derives generalization bounds via the Rademacher complexity framework (Theorem 5.4), showing that our BCD-trained networks not only minimize training loss but also generalize well.\nPotential applications include distributed or parallel training regimes, where the structure of BCD, updating auxiliary parameters (and layers, although our algorithms do not cover parallel training of layers), can reduce communication overhead or support large model scaling (please see lines 30–32).\n\nMoreover, we envision applications in settings where interpretability, formal analysis, or convergence guarantees are critical (e.g., safety-critical ML, robust training, or model verification). \n\n**Computational Complexity**\n\nWe appreciate the request for a more explicit analysis of computational and memory complexity. \nAs for the memory complexity, we need to introduce auxiliary parameters $V_{j,i}$ (that is, vectors in $\\mathbb{R}^{r}$), which represent an output of the $j$-th layer for the $i$-th input. \nThen, in our notation, we need to memorize $nL$ $r$-dimensional vectors, which may be huge in several practical situations. \nOn the other hand, this memory size can be mitigated when one can leverage parallelism computation, as reviewer 82Mp mentioned.\n\nAs for the iteration complexity, detailed in Theorem 5.1 and discussed in Lines 218–220, the number of iterations to reach $\\epsilon$-accuracy is $\\tilde{O}(\\log^2(\\frac{1}{\\epsilon}))$, which just represents a dependency on $\\epsilon$.\nIndeed, we have to update auxiliary variables $V_{j,i}$ ($j=1,\\dots, L-1$) for $\\tilde{O}(\\log^2(\\frac{1}{\\epsilon}))$ times and the weights $W_j$, particularly $W_1$, for $\\tilde{O}(\\log^2(\\frac{1}{\\epsilon}))$ times. \nThus, the overall number of gradient computations, which includes other parameters than $\\epsilon$, should be $\\tilde{O}(nL\\log^2(\\frac{1}{\\epsilon}))$.\nWe will provide these explicit discussions in a final manuscript."}]

Author rebuttal:

Meta-review: This paper proposes and analyzes a block coordinate descent (BCD) algorithm for training deep neural networks with multiple layers by reformulating the standard training objective using auxiliary variables for layer activations. The key points include:

A. Theoretical Contributions:

- The authors provide convergence to global optima for wide deep networks—when sample size is smaller than dimensionality $n<d$—in over-parametric senario.
- They prove a linear convergence rate for the training error under the assumption of strictly monotonically increasing activation functions with bounded derivatives, which is extended to handle ReLU activations through the inclusion of skip connections and non-negative projection steps.
- A generalization bound based on Rademacher complexity is also derived with i.i.d samples.

B. Practical Limitations:

- The experimental validation is limited to synthetic data generated from a teacher network, with minimal real-world evidence supporting the generalization bounds.
- The wide network assumption $n<d$ for global optima convergence, though typically used for NTK models, does not meet practical senarios.

Overall, while the paper contributes valuable theoretical insights into the convergence properties of BCD for deep networks, its practical studies remain limited. After the rebuttal period, the reviewers uniformly think the current manuscript is above the borderline of accept, so is the final proposal.
Decision: Accept (poster)