Accelerated Stochastic Conjugate Gradient for a class of convex optimization

Abstract

The conjugate gradient method is widely recognized as a foundational technique for large-scale unconstrained optimization. In this work, we introduce an Accelerated Stochastic Conjugate Gradient (ASCG) algorithm, specifically designed for a class of convex empirical risk minimization problems. The proposed ASCG method integrates a variance-reduced gradient estimator-inspired by modern stochastic variance reduction techniques-to control noise and improve stability in the optimization process. Moreover, the ASCG algorithm incorporates a novel acceleration mechanism via a deflation factor on the step size, which is shown to achieve faster practical convergence compared to the baseline stochastic FR method. We provide a rigorous theoretical analysis demonstrating that ASCG achieves an expected linear convergence rate under strong convexity assumptions and attains a superior reduction in function values compared to non-accelerated stochastic counterparts. Extensive numerical experiments on four widely-used benchmark datasets confirm that ASCG consistently outperforms state-of-the-art stochastic optimization methods.