Complexity of Finite-Sum Optimization with Nonsmooth Composite Functions and Non-Lipschitz Regularization

In this paper, we present complexity analysis of proximal inexact gradient methods for finite-sum optimization with a nonconvex nonsmooth composite function and non-Lipschitz regularization. By getting access to a convex approximation to the Lipschitz function and a Lipschitz continuous approximation to the non-Lipschitz regularizer, we construct a proximal subproblem at each iteration without using exact function values and gradients. With certain accuracy control on inexact gradients and subproblem solutions, we show that the oracle complexity in terms of total number of inexact gradient evaluations is in order \({\mathcal O}(\epsilon^{-2})\) to find an \((\epsilon,\delta )\)-approximate first-order stationary point, ensuring that within a \(\delta\)-ball centered at this point the maximum reduction of an approximation model does not exceed \(\epsilon \delta\). This shows that we can have the same worst-case evaluation complexity order as in [C. Cartis, N. I. M. Gould, and P. L. Toint, SIAM J. Optim., 21 (2011), pp. 1721?1739, X. Chen, Ph. L. Toint, and H. Wang, SIAM J. Optim., 29 (2019), pp. 874?903], even if we introduce the non-Lipschitz singularity and the nonconvex nonsmooth composite function in the objective function. Moreover, we establish that the oracle complexity regarding the total number of stochastic oracles is in order \(\tilde{\mathcal O}(\epsilon^{-2})\) with high probability for stochastic proximal inexact gradient methods. We further extend the algorithm to adjust to solving stochastic problems with expectation form and derive the associated oracle complexity in order \(\tilde{\mathcal O}(\epsilon^{-10/3})\) with high probability.