Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper provides the first high-probability generalization guarantees for Randomized Block Coordinate Descent (RBCD) on nonconvex learning objectives, addressing a significant gap in theoretical understanding. By analyzing gradient bounds under standard smoothness assumptions and employing polynomially decaying step sizes, the authors demonstrate how early stopping can optimize the trade-off between empirical risk minimization and population risk generalization. The work further extends these guarantees to the gradient-dominated setting and derives dimension-independent bounds for specific loss structures, broadening RBCD's applicability to high-dimensional nonconvex problems.
Early stopping of Randomized Block Coordinate Descent can achieve optimal generalization rates in nonconvex learning, a feat previously unquantified.
Randomized block coordinate descent (RBCD) is a popular optimization algorithm for many large-scale machine learning problems. The existing theoretical analysis of RBCD mainly focuses on its convergence behavior from an optimization perspective, while its generalization behavior remains less understood for nonconvex problems. In this paper, we establish high-probability generalization guarantees for RBCD with nonconvex objectives. In the general nonconvex setting, we derive bounds on the gradients of both empirical and population risks, requiring only standard smoothness assumptions. With polynomially decaying step sizes, we tune the iteration number to balance optimization and generalization, thereby quantifying how early stopping leads to the optimal convergence rate for the population gradients. In the gradient-dominated setting, we provide bounds in terms of functional suboptimality, which nearly match the optimistic rates in convex and low-noise settings. Finally, we develop dimension-independent bounds for loss functions of a specific structure, making the generalization guarantees applicable to high-dimensional problems.