An Accelerated Algorithm for Nonconvex Optimization Based on Adaptive Block Random Projection and Variance Reduction with Convergence Analysis

Currently, solving large-scale non-convex optimisation problems faces two challenges: the computational complexity of stochastic gradients and high variance. This article presents a novel accelerated non-convex optimisation algorithm (Adaptive-VRBSP) based on adaptive block random projection and variance reduction, together with a convergence analysis. The approach draws on Kaczmarz projection theory and SVRG denoising principles, aiming to combine the inherent advantages of projection methods with variance reduction techniques to overcome the high variance and local optimality traps associated with non-convex optimization. The algorithm uses a ‘free’ adaptive importance sampling scheme based on snapshot gradients, which optimises the constant terms in the convergence rate. We show that on non-convex manifolds satisfying the Polyak-Łojasiewicz condition (PL), the constructed generalised projection operator guarantees geometric rate contraction between the iteration sequence and the optimal solution set. This discovery extends the theoretical boundaries of Kaczmarz-type algorithms. It proves their effectiveness not only for linear systems, but also as a universal geometric optimisation tool for a wide range of non-convex tasks in machine learning.