A Note on Complexity for Two Classes of Structured Non-Smooth Non-Convex Compositional Optimization

Abstract

This note studies numerical methods for solving compositional optimization problems, where the inner function is smooth, and the outer function is Lipschitz continuous, non-smooth, and non-convex but exhibits one of two special structures that enable the design of efficient first-order methods. In the first structure, the outer function allows for an easily solvable proximal mapping. We demonstrate that, in this case, a smoothing compositional gradient method can find a $(\hat{I}´,\hat{I}\mu )$-stationary point--specifically defined for compositional optimization--in $O(1/(\hat{I}´\hat{I}{\mu }^2))$ iterations. In the second structure, the outer function is expressed as a difference-of-convex function, where each convex component is simple enough to allow an efficiently solvable proximal linear subproblem. In this case, we show that a prox-linear method can find a nearly $\hat{I}\mu$-critical point in $O(1/\hat{I}{\mu }^2)$ iterations.