Ada-BPSG is introduced, a line-search-free BPSG method that couples the SAGA gradient table with a stabilized Barzilai--Borwein (BB) candidate and yields a direct analytical chain from relative smoothness and component-wise variance control to convergence in finite-dimensional normed spaces.
Abstract
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.
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.
A new convergence rate for SMG in terms of the squared Pareto-stationarity (PS) measure is established, to exploit the Lipschitz continuity of the PS measure, defined by the norm of the multi-gradient descent algorithm (MGDA) direction, rather than the $(1/2)-H\"older continuity of the MGDA direction.
The stochastic recursive gradient algorithm (SARAH) has garnered considerable attention owing to its implementation of a straightforward recursive framework for stochastic gradient updates. Motivated by this, we propose to integrate the importance sampling strategy with mini-batch techniques into the SARAH framework, developing a variant termed SARAH-MI-RBB. During each inner iteration of SARAH-MI-RBB, the mini-batch technique and importance sampling method are employed to dynamically adjust the Barzilai-Borwein (BB) step size and update the iterates. We establish the linear convergence in expectation of the outer iterates to the unique optimal solution for strongly convex problems. Furthermore, we establish the complexity analysis of the algorithm. Numerical experiments demonstrate that the proposed algorithm outperforms existing state-of-the-art methods in its class.
Lei Liu, Hai-Lin Sun, Dan Xue· Asia-Pacific Journal of Oper...· 0 citations
The paper proposes a novel proximal difference-of-convex (DC) algorithmic framework to solve general non-convex, non-smooth optimization problems. By combining Barzilai-Borwein (BB) step sizes with nonmonotone line search strategies, our approach effectively overcomes the conservative step sizes and stability issues inherent in standard proximal DC algorithms. Furthermore, we develop extrapolation mechanisms to accelerate convergence while ensuring global stability. The global convergence of the proposed algorithms is rigorously established under the Kurdyka-\L ojasiewicz property. Numerical experiments on the SCAD-regularized least squares problem and graphic Ginzburg-Landau image segmentation models demonstrate that the proposed methods achieve highly competitive efficiency and accuracy compared to existing DC algorithms.
We introduce two novel randomized iterative regularization frameworks, termed \texttt{RIGKT} and \texttt{RIAT}, for solving large-scale linear ill-posed inverse problems governed by systems of equations. The proposed methods combine randomized iterated Tikhonov regularization with Krylov subspace projection techniques, utilizing Golub--Kahan bidiagonalization for general rectangular systems (\texttt{RIGKT}) and Arnoldi decomposition for square systems (\texttt{RIAT}). Unlike existing deterministic schemes that rely on fixed iteration counts, our framework incorporates randomized equation selection, an adaptive step-size strategy, and a global, discrepancy-based a posteriori early-stopping rule tailored specifically to the stochastic setting. We present a comprehensive regularization analysis establishing Bregman-distance monotonicity, finite termination, exact-data convergence, and pathwise stability under noise. Furthermore, we prove that the stopped iterates converge almost surely and in the mean-square sense to the true solution, establishing a rigorous regularization property. To the best of our knowledge, this is the first theoretical framework to simultaneously account for randomization, Krylov-subspace dimension reduction, and implementable early stopping. Numerical experiments involving two-dimensional X-ray computed tomography (CT) and image deblurring demonstrate that \texttt{RIGKT} and \texttt{RIAT} reliably reconstruct structural features across various noise regimes.
Ravi Verma, Harshit Bajpai, Ankik Kumar Giri· arXiv.org· 0 citations
We study stochastic convex optimization under asymmetric \((L_0,L_1)\)-generalized smoothness, a model motivated by machine-learning objectives whose local curvature may grow with the gradient norm. We assume an unbiased first-order oracle with additive norm-sub-Gaussian noise. Acceleration is difficult in this setting because momentum may enter regions of much larger curvature, while stochastic gradients cannot reliably certify an unrestricted trajectory. We propose \textsf{ARC-SG}, a two-phase accelerated method: Phase~I reduces excessively large gradients using a generalized-smoothness-aware stochastic step, then Phase~II solves strongly convex proximal subproblems by a restarted accelerated solver confined to certified smoothness balls. Exact proximal points do not increase the gradient norm, allowing these certificates to propagate through the outer loop. The contribution is a query-by-query certified-localization construction with explicit generalized-smoothness factors and a strongly convex restart extension. \textsf{ARC-SG} achieves, with high probability, an accelerated optimization contribution and smooth-subclass-optimal statistical dependence on accuracy, up to logarithmic and generalized-smoothness factors. Its convex accuracy exponents agree with a contemporaneous public stochastic-acceleration result under a broader smoothness and affine-variance model; our distinction is the certified geometry, explicit parameter accounting, and strongly convex guarantee. The results recover classical accelerated stochastic rates when \(L_1=0\). Experiments on objectives with unbounded gradients illustrate the two-phase mechanism and its finite-budget advantage.
D. Dvinskikh, A. Gasnikov, A. Lobanov et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
