Block Coordinate Descent for Neural Networks Provably Finds Global Minima
This provides theoretical guarantees for a practical optimization method in deep learning, addressing the challenge of global convergence for neural network training.
The paper proves that block coordinate descent (BCD) can find global minima for deep neural networks with strictly monotonic activations, achieving arbitrarily small loss with exponential convergence in the output layer. It also extends these guarantees to ReLU networks through a modified algorithm with skip connections and non-negative projection.
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.