Single-loop Projection-free and Projected Gradient-based Algorithms for Nonconvex-concave Saddle Point Problems with Bilevel Structure
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_ | 1866913762896773120 |
|---|---|
| author | Ahmadi, Mohammad Mahdi Hamedani, Erfan Yazdandoost |
| author_facet | Ahmadi, Mohammad Mahdi Hamedani, Erfan Yazdandoost |
| contents | In this paper, we explore a broad class of constrained saddle point problems with a bilevel structure, wherein the upper-level objective function is nonconvex-concave and smooth over compact and convex constraint sets, subject to a strongly convex lower-level objective function. This class of problems finds wide applicability in machine learning, encompassing robust multi-task learning, adversarial learning, and robust meta-learning. Our study extends the current literature in two main directions: (i) We consider a more general setting where the upper-level function is not necessarily strongly concave or linear in the maximization variable. (ii) While existing methods for solving saddle point problems with a bilevel structure are projection-based algorithms, we propose a one-sided projection-free method employing a linear minimization oracle. Specifically, by utilizing regularization and nested approximation techniques, we introduce a novel single-loop one-sided projection-free algorithm, requiring $\cO(ε^{-4})$ iterations to attain an $ε$-stationary solution, moreover, when the objective function in the upper-level is linear in the maximization component, our result improve to $\cO(ε^{-3})$. Subsequently, we develop an efficient single-loop fully projected gradient-based algorithm capable of achieving an $ε$-stationary solution within $\cO(ε^{-5})$ iterations. This result improves to $\cO(ε^{-4})$ when the upper-level objective function is strongly concave in the maximization component. Finally, we tested our proposed methods against the state-of-the-art algorithms for solving a robust multi-task regression problem to showcase the superiority of our algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_13021 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Single-loop Projection-free and Projected Gradient-based Algorithms for Nonconvex-concave Saddle Point Problems with Bilevel Structure Ahmadi, Mohammad Mahdi Hamedani, Erfan Yazdandoost Optimization and Control In this paper, we explore a broad class of constrained saddle point problems with a bilevel structure, wherein the upper-level objective function is nonconvex-concave and smooth over compact and convex constraint sets, subject to a strongly convex lower-level objective function. This class of problems finds wide applicability in machine learning, encompassing robust multi-task learning, adversarial learning, and robust meta-learning. Our study extends the current literature in two main directions: (i) We consider a more general setting where the upper-level function is not necessarily strongly concave or linear in the maximization variable. (ii) While existing methods for solving saddle point problems with a bilevel structure are projection-based algorithms, we propose a one-sided projection-free method employing a linear minimization oracle. Specifically, by utilizing regularization and nested approximation techniques, we introduce a novel single-loop one-sided projection-free algorithm, requiring $\cO(ε^{-4})$ iterations to attain an $ε$-stationary solution, moreover, when the objective function in the upper-level is linear in the maximization component, our result improve to $\cO(ε^{-3})$. Subsequently, we develop an efficient single-loop fully projected gradient-based algorithm capable of achieving an $ε$-stationary solution within $\cO(ε^{-5})$ iterations. This result improves to $\cO(ε^{-4})$ when the upper-level objective function is strongly concave in the maximization component. Finally, we tested our proposed methods against the state-of-the-art algorithms for solving a robust multi-task regression problem to showcase the superiority of our algorithms. |
| title | Single-loop Projection-free and Projected Gradient-based Algorithms for Nonconvex-concave Saddle Point Problems with Bilevel Structure |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2404.13021 |