Deep learning has aroused extensive attention due to its great empirical
success. The efficiency of the block coordinate descent (BCD) methods has been
recently demonstrated in deep neural network (DNN) training. However,
theoretical studies on their convergence properties are limited due to the
highly nonconvex nature of DNN training. In this paper, we aim at providing a
general methodology for provable convergence guarantees for this type of
methods. In particular, for most of the commonly used DNN training models
involving both two- and three-splitting schemes, we establish the global
convergence to a critical point at a rate of ${\cal O}(1/k)$, where $k$ is the
number of iterations. The results extend to general loss functions which have
Lipschitz continuous gradients and deep residual networks (ResNets). Our key
development adds several new elements to the Kurdyka-{\L}ojasiewicz inequality
framework that enables us to carry out the global convergence analysis of BCD
in the general scenario of deep learning.

本文介绍了一种针对深度学习中常用的两分和三分网络结构的 Block Coordinate Descent 方法，论证了它的全局收敛性和迭代收敛速度。

深度学习中块坐标下降的全局收敛性

Global Convergence of Block Coordinate Descent in Deep Learning

In this paper we consider the composite self-concordant (CSC) minimization
problem, which minimizes the sum of a self-concordant function $f$ and a
(possibly nonsmooth) proper closed convex function $g$. The CSC minimization is
the cornerstone of the path-following interior point methods for solving a
broad class of convex optimization problems. It has also found numerous
applications in machine learning. The proximal damped Newton (PDN) methods have
been well studied in the literature for solving this problem that enjoy a nice
iteration complexity. Given that at each iteration these methods typically
require evaluating or accessing the Hessian of $f$ and also need to solve a
proximal Newton subproblem, the cost per iteration can be prohibitively high
when applied to large-scale problems. Inspired by the recent success of block
coordinate descent methods, we propose a randomized block proximal damped
Newton (RBPDN) method for solving the CSC minimization. Compared to the PDN
methods, the computational cost per iteration of RBPDN is usually significantly
lower. The computational experiment on a class of regularized logistic
regression problems demonstrate that RBPDN is indeed promising in solving
large-scale CSC minimization problems. The convergence of RBPDN is also
analyzed in the paper. In particular, we show that RBPDN is globally convergent
when $g$ is Lipschitz continuous. It is also shown that RBPDN enjoys a local
linear convergence. Moreover, we show that for a class of $g$ including the
case where $g$ is Lipschitz differentiable, RBPDN enjoys a global linear
convergence. As a striking consequence, it shows that the classical damped
Newton methods [22,40] and the PDN [31] for such $g$ are globally linearly
convergent, which was previously unknown in the literature. Moreover, this
result can be used to sharpen the existing iteration complexity of these
methods.

本文介绍了一种基于随机块参数下降方法的分块近似牛顿法，用于解决复合自共轭（CSC）极小化问题的问题，该方法的计算成本通常比传统的 PDN 方法低，已在处理大规模 CSC minimization 问题方面取得了显着效果。

基于随机分块的近端阻尼牛顿法用于复合自共轭最小化

Randomized block proximal damped Newton method for composite  self-concordant minimization

Consider the problem of minimizing the sum of a smooth (possibly non-convex)
and a convex (possibly nonsmooth) function involving a large number of
variables. A popular approach to solve this problem is the block coordinate
descent (BCD) method whereby at each iteration only one variable block is
updated while the remaining variables are held fixed. With the recent advances
in the developments of the multi-core parallel processing technology, it is
desirable to parallelize the BCD method by allowing multiple blocks to be
updated simultaneously at each iteration of the algorithm. In this work, we
propose an inexact parallel BCD approach where at each iteration, a subset of
the variables is updated in parallel by minimizing convex approximations of the
original objective function. We investigate the convergence of this parallel
BCD method for both randomized and cyclic variable selection rules. We analyze
the asymptotic and non-asymptotic convergence behavior of the algorithm for
both convex and non-convex objective functions. The numerical experiments
suggest that for a special case of Lasso minimization problem, the cyclic block
selection rule can outperform the randomized rule.

本论文提出了一种基于多核并行处理技术和凸逼近的近似并行块协调下降（BCD）方法，并研究了该方法的收敛性，结果表明在 Lasso 问题的特定情况下，循环块选择规则优于随机规则。