Name
Abstract | ||
|---|---|---|
AbstractRecently, convex-concave bilinear Saddle Point Problems (SPP) is widely used in lasso problems, Support Vector Machines, game theory, and so on. Previous researches have proposed many methods to solve SPP, and present their convergence rate theoretically. To achieve linear convergence, analysis in those previouse studies requires strong convexity of φ(z). But, we find the linear convergence can also be achieved even for a general convex but not strongly convex φ(z). In the article, by exploiting the strong duality of SPP, we propose a new method to solve SPP, and achieve the linear convergence. We present a new general sufficient condition to achieve linear convergence, but do not require the strong convexity of φ(z). Furthermore, a more efficient method is also proposed, and its convergence rate is analyzed in theoretical. Our analysis shows that the well conditioned φ(z) is necessary to improve the efficiency of our method. Finally, we conduct extensive empirical studies to evaluate the convergence performance of our methods. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1145/3420035 | ACM Transactions on Intelligent Systems and Technology |
Keywords | DocType | Volume |
Saddle point problems, linear convergence, strong convexity, min-max optimization | Journal | 12 |
Issue | ISSN | Citations |
1 | 2157-6904 | 0 |
PageRank | References | Authors |
0.34 | 0 | 8 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| WuWendi | 1 | 0 | 0.34 |
| ZhaoYawei | 2 | 0 | 0.34 |
| En Zhu | 3 | 349 | 50.63 |
| LiuXinwang | 4 | 0 | 0.34 |
| Xingxing Zhang | 5 | 134 | 16.05 |
| Lailong Luo | 6 | 18 | 6.50 |
| WangShixiong | 7 | 0 | 0.34 |
| Jianping Yin | 8 | 978 | 89.94 |