Research map / Optimization / Implicit bias and generalization

Block Coordinate Descent for Neural Networks Provably Finds Global Minima

NeurIPS 2025 · Optimization › Implicit bias and generalization · approach: Shallow ReLU network convergence · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves global convergence to arbitrarily small loss for block coordinate descent (layer-wise auxiliary-variable BCD) training of deep networks with strictly monotone activations, adds a skip-connection and non-negative projection variant for ReLU, and derives Rademacher generalization bounds.

Problem

Existing convergence guarantees for block coordinate descent (BCD) training of neural networks only reach stationary points, not global minima, for deep networks.

Approach

Reformulate the loss with auxiliary hidden-layer variables and update weights and variables layer-wise (output to input) with plain gradient descent; under strictly monotone activations with bounded singular values of weights, show linear decay of the output loss and small hidden losses, yielding global convergence. Extend to ReLU via skip connections and non-negative projections.

Key results

• Theorem gives F(W,V) <= epsilon for BCD with strictly monotone activations under singular values of W_j in [3/4,5/4], with total gradient computations O(nL log^2(1/epsilon))
• Generalization gap bound derived via Rademacher complexity under bounded inputs and labels, with high-probability guarantee
• Experiments on a 4-hidden-layer width-30 network with LeakyReLU (alpha=0.5) and skip-connected ReLU show training loss decreasing monotonically; without SVB loss stagnates around 1e-3

Measured effects reported in the paper

Surprising findings

• Without singular value bounding, training loss stagnates around 1e-3 in the LeakyReLU experiment
• Plain ReLU networks without skip connections fail to converge in the experiments

Limitations

• Requires full-rank data matrix (n <= d_in) and strictly monotone activation with bounded slope for main result
• ReLU result needs a skip-connection architecture and fixed output layer W_L
• Experiments are small and synthetic only

Experimental setup

Datasets: synthetic teacher-network data

Metrics: training loss

Builds on: Neural tangent kernel Rademacher complexity generalization bounds ResNet Singular value bounding

Closest papers by meaning

• Global Convergence of Block Coordinate Descent in Deep Learning (ICML 2019 · similarity 0.95)
• Convergent Block Coordinate Descent for Training Tikhonov Regularized Deep Neural Networks (NeurIPS 2017 · similarity 0.93)
• Stability and Generalization of Learning Algorithms that Converge to Global Optima (ICML 2018 · similarity 0.90)
• Implicit bias of SGD in $L_2$-regularized linear DNNs: One-way jumps from high to low rank (ICLR 2024 · similarity 0.88)
• Non-Singularity of the Gradient Descent Map for Neural Networks with Piecewise Analytic Activations (NeurIPS 2025 · similarity 0.87)
• Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification (NeurIPS 2025 · similarity 0.87)