Search papers, labs, and topics across Lattice.
This paper introduces Ada-BPSG, an innovative line-search-free Bregman proximal stochastic gradient method that leverages a stabilized Barzilai鈥揃orwein step size to enhance optimization in poorly conditioned landscapes. By aggregating incremental secant information and applying safeguards to curvature estimates, Ada-BPSG achieves robust convergence rates, including an $O(n/K)$ ergodic rate for convex objectives and an $O(1/K)$ bound in nonconvex scenarios. Experimental results on logistic regression and sparse nonnegative matrix factorization demonstrate that Ada-BPSG significantly reduces sensitivity to initial step sizes while maintaining competitive objective values compared to standard variance-reduced methods.
Ada-BPSG achieves robust optimization with significantly reduced sensitivity to initial conditions, outperforming traditional methods without the need for line searches.
Bregman proximal stochastic gradient (BPSG) methods bring variance-reduced composite optimization to objectives whose geometry is poorly captured by Euclidean smoothness. Their performance, however, remains sensitive to the step size: raw stochastic curvature estimates can fluctuate sharply, whereas line searches add repeated proximal evaluations. We introduce Ada-BPSG, a line-search-free BPSG method that couples the SAGA gradient table with a stabilized Barzilai--Borwein (BB) candidate. A mediant aggregates incremental secant information so that nearly singular local ratios receive little weight, and an explicit safeguard translates the resulting curvature estimate into the bounded step-size sequence required for convergence. This design yields a direct analytical chain from relative smoothness and component-wise variance control to convergence in finite-dimensional normed spaces. We prove an $O(n/K)$ ergodic rate for convex objectives, a restarted linear rate under relative quadratic growth, and an $O(1/K)$ bound for a Bregman proximal residual in the nonconvex setting. On logistic regression and sparse nonnegative matrix factorization, Ada-BPSG combines low objective values with substantially less sensitivity to the initial step size than standard variance-reduced baselines, while avoiding line search.
