Linear Convergence of Accelerated Stochastic Gradient Descent for Nonconvex Nonsmooth Optimization

Abstract

In this paper, we study the stochastic gradient descent (SGD) method for the nonconvex nonsmooth optimization, and propose an accelerated SGD method by combining the variance reduction technique with Nesterov's extrapolation technique. Moreover, based on the local error bound condition, we establish the linear convergence of our method to obtain a stationary point of the nonconvex optimization. In particular, we prove that not only the sequence generated linearly converges to a stationary point of the problem, but also the corresponding sequence of objective values is linearly convergent. Finally, some numerical experiments demonstrate the effectiveness of our method. To the best of our knowledge, it is first proved that the accelerated SGD method converges linearly to the local minimum of the nonconvex optimization.

This paper has been withdrawn by the author due to some errors in the proof of the convergence analysis. They will modify these errors as soon as possible

References in corpus (4)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Variance Reduction for Nonconvex Optimization
• A SMART Stochastic Algorithm for Nonconvex Optimization with Applications to Robust Machine Learning
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization