Stochastic variance-reduced prox-linear algorithms for nonconvex composite optimization

• 成果类型: Article
• 署名作者: Zhang, Junyu; Xiao, Lin
• 署名单位: Princeton University; Facebook Inc
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01709-z
• 发表日期: 2022
• 页码: 649-691
• 关键词: minimization; nonsmooth

摘要

We consider the problem of minimizing composite functions of the form f(g(x))+h(x), where f and h are convex functions (which can be nonsmooth) and g is a smooth vector mapping. In addition, we assume that g is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose a class of stochastic variance-reduced prox-linear algorithms for solving such problems and bound their sample complexities for finding an epsilon-stationary point in terms of the total number of evaluations of the component mappings and their Jacobians. When g is a finite average of N components, we obtain sample complexity O(N+N-4/5 epsilon(-1)) for both mapping and Jacobian evaluations. When g is a general expectation, we obtain sample complexities of O(epsilon(-5/2)) and O(epsilon(-3/2)) for component mappings and their Jacobians respectively. If in addition f is smooth, then improved sample complexities of O(N+N-1/2 epsilon(-1)) and O(epsilon(-3/2)) are derived for g being a finite average and a general expectation respectively, for both component mapping and Jacobian evaluations.