A Proximal Adaptive Momentum Algorithm with Variance Reduction for Nonconvex Composite Optimization: Convergence Analysis and Complexity Bounds

We propose and analyze the Proximal Adaptive Momentum with Variance Reduction (PAMVR) algorithm, a
novel first-order method for solving nonconvex composite optimization problems of the form min F(x) = f(x) + g(x), where
f is a smooth nonconvex function and g is a proper convex, lower-semicontinuous regularizer. PAMVR integrates three
complementary mechanisms: (i) a momentum-corrected gradient estimator with adaptive step sizes, (ii) a periodic variancereduction snapshot strategy inspired by SVRG, and (iii) a proximal operator for handling the nonsmooth component. Under
standard Lipschitz-gradient and bounded-variance assumptions, we establish global convergence to an epsilon-approximate
stationary point with a sample complexity of O(n + n^{2/3}/epsilon^2) stochastic gradient evaluations, matching the bestknown bounds for this problem class while requiring weaker algorithmic assumptions than existing momentum-based
methods. We further prove almost-sure convergence of the iterate sequence under a Kurdyka-Lojasiewicz (KL) regularity
condition, obtaining explicit convergence rates depending on the KL exponent. The theoretical findings are validated on
benchmark nonconvex problems including sparse logistic regression, matrix completion, and neural network training,
demonstrating consistent improvements of 15–32% in convergence speed over PROX-SVRG, ProxGD-M, and Spider-Boost
baselines. These results establish PAMVR as both a theoretically sound and practically competitive method for large-scale
nonconvex optimization.