Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions
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_ | 1866912119843192832 |
|---|---|
| author | Hu, Quanqi Qi, Qi Lu, Zhaosong Yang, Tianbao |
| author_facet | Hu, Quanqi Qi, Qi Lu, Zhaosong Yang, Tianbao |
| contents | In this paper, we study a class of non-smooth non-convex problems in the form of $\min_{x}[\max_{y\in Y}ϕ(x, y) - \max_{z\in Z}ψ(x, z)]$, where both $Φ(x) = \max_{y\in Y}ϕ(x, y)$ and $Ψ(x)=\max_{z\in Z}ψ(x, z)$ are weakly convex functions, and $ϕ(x, y), ψ(x, z)$ are strongly concave functions in terms of $y$ and $z$, respectively. It covers two families of problems that have been studied but are missing single-loop stochastic algorithms, i.e., difference of weakly convex functions and weakly convex strongly-concave min-max problems. We propose a stochastic Moreau envelope approximate gradient method dubbed SMAG, the first single-loop algorithm for solving these problems, and provide a state-of-the-art non-asymptotic convergence rate. The key idea of the design is to compute an approximate gradient of the Moreau envelopes of $Φ, Ψ$ using only one step of stochastic gradient update of the primal and dual variables. Empirically, we conduct experiments on positive-unlabeled (PU) learning and partial area under ROC curve (pAUC) optimization with an adversarial fairness regularizer to validate the effectiveness of our proposed algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18577 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions Hu, Quanqi Qi, Qi Lu, Zhaosong Yang, Tianbao Optimization and Control Machine Learning In this paper, we study a class of non-smooth non-convex problems in the form of $\min_{x}[\max_{y\in Y}ϕ(x, y) - \max_{z\in Z}ψ(x, z)]$, where both $Φ(x) = \max_{y\in Y}ϕ(x, y)$ and $Ψ(x)=\max_{z\in Z}ψ(x, z)$ are weakly convex functions, and $ϕ(x, y), ψ(x, z)$ are strongly concave functions in terms of $y$ and $z$, respectively. It covers two families of problems that have been studied but are missing single-loop stochastic algorithms, i.e., difference of weakly convex functions and weakly convex strongly-concave min-max problems. We propose a stochastic Moreau envelope approximate gradient method dubbed SMAG, the first single-loop algorithm for solving these problems, and provide a state-of-the-art non-asymptotic convergence rate. The key idea of the design is to compute an approximate gradient of the Moreau envelopes of $Φ, Ψ$ using only one step of stochastic gradient update of the primal and dual variables. Empirically, we conduct experiments on positive-unlabeled (PU) learning and partial area under ROC curve (pAUC) optimization with an adversarial fairness regularizer to validate the effectiveness of our proposed algorithms. |
| title | Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2405.18577 |