Logo image
Back
A Note on Complexity for Two Classes of Structured Non-Smooth Non-Convex Compositional Optimization
Preprint   Open access

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

Yao Yao, Qihang Lin and Tianbao Yang
ArXiV.org
Cornell University
11/21/2024
DOI: 10.48550/arxiv.2411.14342
url
https://doi.org/10.48550/arxiv.2411.14342View
Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

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 (δ,ϵ)-stationary point--specifically defined for compositional optimization--in O(1/(δϵ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 ϵ-critical point in O(1/ϵ2) iterations.
Mathematics - Optimization and Control

Details

Metrics

18 Record Views
Logo image