Convergent Block Coordinate Descent for Training Tikhonov Regularized Deep Neural Networks
By lifting the ReLU function into a higher dimensional space, we develop a smooth multi-convex formulation for training feed-forward deep neural networks (DNNs). This allows us to develop a block coordinate descent (BCD) training algorithm consisting of a sequence of numerically well-behaved convex optimizations. Using ideas from proximal point methods in convex analysis, we prove that this BCD algorithm will converge globally to a stationary point with R-linear convergence rate of order one. In experiments with the MNIST database, DNNs trained with this BCD algorithm consistently yielded better test-set error rates than identical DNN architectures trained via all the stochastic gradient descent (SGD) variants in the Caffe toolbox.
This manuscript proposes a modification of feed-forward neural network optimization problem when the activation function is the ReLU function.
My major concern is about the convergence proof for the block coordinate descent algorithm. In particular, Theorem 1 is incorrect for the following reason:
A. It assumed that the sequence generated by the algorithm has a limit point.
This may not be the case as the set U is not compact (closed but not bounded). Therefore, the sequence may not converge to a finite point.
B. It stated that the sequence generated by the algorithm has a unique limit point (line 263: "the" limit point).
Even the algorithm has limit points, it may not be unique. Consider the sequence x_i = (-1)^n - 1/n, clearly it has 2 limit points: +1 and -1.
For the rest parts of the paper, my comments are as follows.
1. The new formulation seems interesting, and it can be separately discussed from the block coordinate descent part, and it looks to me the major novelty is the new formulation but not the algorithm.
However, the major concern for the new formulation is that it has much more variables, which can potentially lead to spatial unfeasibility when there are more data instances. This problem hinders people from applying the formulation to large-scale problems and thus its usefulness is limited.
2. I do not see that the problem in line 149 is always convex with respect to W. This requires further elaboration.
3. In the introduction, some efforts were put in describing the issue of saddle points. However, this manuscript does not handle this problem as well. I'd suggest the authors to remove the related discussion.
4. The format of paper reference and equation reference is rather non-standard. Usually [1] is used for paper reference and (1) is for equation reference.
5. The comparison with Caffe solvers in term of time is meaningless as the implementation platforms are totally different. I do not understand  the sentence "using MATLAB still run significantly faster" especially regarding the word "still", as matlab should be expected to be faster than python.
6. The comparison of the objective value in 3(a) is comparing apples to oranges, as the two are solving different problems.
=== After feedback ===
I did notice that in Line 100 the authors mentioned that U,V,W are compact sets, but as we see in line 124, U is set to be the nonnegative half-space, which is clearly unbounded and thus non-compact.
Therefore, indeed when U is compact, this is correct that there will be at least a limit point and thus the convergence analysis may hold true (see details below), it is not the case for the problem (4) or (5).
Regarding the proof, I don't agree with the concept of "the" limit point when t = \infty. I don't think such thing exists by nature.
As stated in my original review, there might be several limit points, and by definition we always have all limit points are associated with t = \infty, just in different ways.
The authors said in the rebuttal that because their algorithm converges so "the" limit point exists, but this is using the result proved under this assumption to prove that the assumption is true. I don't think that is a valid way of proof.
In addition, in the extremest case, consider that the sets U,V,W all consist of one point, say u,v,w, and the gradient at (u,v,w) is not zero. Clearly in this case there is one and only one limit point (u,v,w), but apparently it is not a stationary point as the gradient is non-zero.
Therefore, I will keep the same score.