A Note on Complexity for Two Classes of Structured Non-Smooth Non-Convex Compositional Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910707408175104 |
|---|---|
| author | Yao, Yao Lin, Qihang Yang, Tianbao |
| author_facet | Yao, Yao Lin, Qihang Yang, Tianbao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_14342 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Note on Complexity for Two Classes of Structured Non-Smooth Non-Convex Compositional Optimization Yao, Yao Lin, Qihang Yang, Tianbao Optimization and Control 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. |
| title | A Note on Complexity for Two Classes of Structured Non-Smooth Non-Convex Compositional Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2411.14342 |