Adaptive Barzilai-Borwein Proximal Gradient Method for Nonconvex Optimization
TL;DR
The proposed AdaBBNC incorporates a flexible BB-based curvature estimate into the proximal gradient framework to enhance adaptability in nonconvex settings and achieves the optimal iteration complexity of $\mathcal{O}(\epsilon^{-2})$ for finding an $\epsilon$-stationary point, without requiring any prior knowledge of the global Lipschitz constant.
Abstract
The Barzilai-Borwein (BB) method is an efficient gradient-based approach for unconstrained optimization that approximates spectral information of the Hessian matrix to capture curvature at low computational cost. In this paper, we extend the BB stepsize strategy to composite nonconvex optimization problems consisting of a smooth nonconvex term and a proper closed convex term, and propose an adaptive Barzilai-Borwein proximal gradient method for nonconvex optimization (AdaBBNC). The proposed method incorporates a flexible BB-based curvature estimate into the proximal gradient framework to enhance adaptability in nonconvex settings. Under mild assumptions, we establish that AdaBBNC achieves the optimal iteration complexity of $\mathcal{O}(\epsilon^{-2})$ for finding an $\epsilon$-stationary point, without requiring any prior knowledge of the global Lipschitz constant. Numerical experiments demonstrate the effectiveness and robustness of the proposed method. Compared with recent parameter-free and line-search-free adaptive proximal gradient methods, AdaBBNC exhibits more aggressive yet stable behavior in ill-conditioned optimization problems.