Completely Randomized Trust-Region Algorithms Incorporating Barzilai–Borwein Step Sizes

Abstract

This study introduces novel stochastic gradient algorithms that integrate Barzilai–Borwein adaptive step sizes within a trust-region-inspired framework for solving finite-sum optimization problems. The proposed approach, referred to as TRishBB, extends the foundation of the Trust-Region-ish (TRish) framework developed by Curtis, Scheinberg, and Shi (2019) in the INFORMS Journal on Optimization. The objective of TRishBB is to improve the computational efficiency and optimization performance of the original TRish scheme while avoiding the high cost associated with its second-order variant. Three distinct algorithms under the TRishBB family are introduced, and their convergence behavior is analyzed for both convex and nonconvex objectives using biased or unbiased stochastic gradients. The theoretical results are obtained without assuming diminishing step lengths or full gradient evaluations. Experimental evaluations on machine learning benchmarks confirm that employing Barzilai–Borwein step sizes within stochastic trust-region schemes enhances both convergence speed and testing accuracy relative to the standard TRish method.