<p>Momentum-based proximal gradient methods perform well on convex empirical risk minimization, but face challenges in nonconvex settings common in modern machine learning. As datasets grow in size and complexity, nonconvex and nonsmooth regularization becomes essential for improving generalization and controlling model complexity in tasks like logistic regression, sparse recovery, and neural networks. However, exact gradient computation is costly, and the nonsmooth, nonconvex nature of such problems complicates convergence analysis. Algorithms with strong theoretical convergence guarantees for these challenging problems remain scarce. Our approach incorporates momentum using only current sample gradient, dynamically controls mini-batch size to balance stochastic gradient noise and computational efficiency, and scales step size proportionally to mini-batch size for enhanced convergence. The proposed algorithm achieves an optimal rate of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {O}(K^{-1/2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>K</mi> <mrow> <mo>-</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> under general nonconvex nonsmooth settings and a relaxed gradient variance bound. For Kurdyka-Łojasiewicz (KL) problems, convergence rates for the expected function value are established based on different KL exponents, and linear convergence of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathcal {O}(\rho ^{k})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>ρ</mi> <mi>k</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> (<InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\rho \in (0,1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ρ</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>) is attained in suitable scenarios. Logistic regression and neural networks demonstrate that it outperforms state-of-the-art algorithms in efficiency and accuracy, guides the selection of hyperparameters like mini-batch size and step size, and enhances robustness.</p>

Adaptive Sampling and Step Size for Momentum Proximal Stochastic Gradient Method in Nonconvex Nonsmooth Problems

期刊论文
发表日期：

2026年6月1日

查看全文

Mengxiang Zhang,
Ailun Jian,
Gonglin Yuan

摘要

Momentum-based proximal gradient methods perform well on convex empirical risk minimization, but face challenges in nonconvex settings common in modern machine learning. As datasets grow in size and complexity, nonconvex and nonsmooth regularization becomes essential for improving generalization and controlling model complexity in tasks like logistic regression, sparse recovery, and neural networks. However, exact gradient computation is costly, and the nonsmooth, nonconvex nature of such problems complicates convergence analysis. Algorithms with strong theoretical convergence guarantees for these challenging problems remain scarce. Our approach incorporates momentum using only current sample gradient, dynamically controls mini-batch size to balance stochastic gradient noise and computational efficiency, and scales step size proportionally to mini-batch size for enhanced convergence. The proposed algorithm achieves an optimal rate of $\mathcal {O}(K^{-1/2})$ $O (K^{- 1 / 2})$ under general nonconvex nonsmooth settings and a relaxed gradient variance bound. For Kurdyka-Łojasiewicz (KL) problems, convergence rates for the expected function value are established based on different KL exponents, and linear convergence of $\mathcal {O}(\rho ^{k})$ $O (ρ^{k})$ ( $\rho \in (0,1)$ $ρ \in (0, 1)$ ) is attained in suitable scenarios. Logistic regression and neural networks demonstrate that it outperforms state-of-the-art algorithms in efficiency and accuracy, guides the selection of hyperparameters like mini-batch size and step size, and enhances robustness.