Accelerated Proximal Gradient Methods for Nonconvex Programming
Nonconvex and nonsmooth problems have recently received considerable attention in signal/image processing, statistics and machine learning. However, solving the nonconvex and nonsmooth optimization problems remains a big challenge. Accelerated proximal gradient (APG) is an excellent method for convex programming. However, it is still unknown whether the usual APG can ensure the convergence to a critical point in nonconvex programming. In this paper, we extend APG for general nonconvex and nonsmooth programs by introducing a monitor that satisfies the sufficient descent property. Accordingly, we propose a monotone APG and a nonmonotone APG. The latter waives the requirement on monotonic reduction of the objective function and needs less computation in each iteration. To the best of our knowledge, we are the first to provide APG-type algorithms for general nonconvex and nonsmooth problems ensuring that every accumulation point is a critical point, and the convergence rates remain O 1 k 2 when the problems are convex, in which k is the number of iterations. Numerical results testify to the advantage of our algorithms in speed.
The paper proposes an accelerated gradient-based algorithm for         non-convex composite optimization. Essentially, it provides an         alternative to the existing work of Ghadimi and Lan, 2013. The main         features of the algorithm is to preserve Nesterov's acceleration for         convex problems, while providing convergence to stationary points for         non-convex ones. The paper also presents convergence analysis from         various points of views.          I like the paper and believe that it is a strong contribution.         Nevertheless, there are a few points that could improve the paper         - I found the comparison with Ghadimi and Lan not quite fair. On the one         hand, their approach requires a convex function g and does not apply to          the more general problem considered in the paper. On the other hand,         their convergence results are significantly stronger than simple convergence         to stationary points, since they also provide convergence rates.         - The experimental part is poor compared to the rest of the paper. The purpose         of this experiments should be to convince the reader that acceleration          applies in practice. To settle the case, it would have been good to          simply report the objective function achieved by the different methods as          as function of the number of iterations. Instead, the table reports a         comparison for a specific arbitrary objective function value. Why         this objective function value makes sense is not clear. It is also         not clear that conclusions drawn for this value would generalize to         other ones.          - Finally, I found the experimental setup presented in the         supplementary material (sparse PCA) more interesting than the one         presented in the main paper. sparse PCA is more challenging, and more         interesting. This is of course subjective, but perhaps, the authors         should consider including the sparse PCA experiment in the main paper         instead of the logistic regression one.          Misc comments:         - Please define and comment on the KL assumption in the final version         of the paper, if it is accepted. The paper should be self-content         without having to read the supplementary material.