A Note on Complexity for Two Classes of Structured Non-Smooth Non-Convex Compositional Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |