Nonconvex Big-Data Optimization via System Theory: a Block-wise Incremental Gradient Method

In this paper, we propose and analyze Block-wise Incremental Gradient with Averaging (BIG-A), i.e., a novel optimization algorithm tailored for large-scale and bigdata nonconvex optimization problems with a composite cost function. At each iteration, the algorithm uses a block of a single function gradient to properly update auxiliary variables providing a proxy of a descent direction. We interpret BIG-A as a dynamical system arising from the interconnection between a fast, time-varying scheme and a slow, time-invariant one. This interpretation allows us to prove the convergence properties by using system theory results relying on the LaSalle-Yoshizawa invariance principle and singular perturbations. The solution estimate sequence generated by BIG-A is shown to converge toward the set of stationary points of the problem, which is not assumed to be convex nor satisfying the Polyak-Łojasiewicz condition. If strong convexity is also assumed, linear convergence toward the unique optimal solution is established. Finally, numerical simulations confirm the theoretical findings.