A Doubly Stochastically Perturbed Algorithm for Linearly Constrained Bilevel Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915231454724096 |
|---|---|
| author | Khanduri, Prashant Tsaknakis, Ioannis Zhang, Yihua Liu, Sijia Hong, Mingyi |
| author_facet | Khanduri, Prashant Tsaknakis, Ioannis Zhang, Yihua Liu, Sijia Hong, Mingyi |
| contents | In this work, we develop analysis and algorithms for a class of (stochastic) bilevel optimization problems whose lower-level (LL) problem is strongly convex and linearly constrained. Most existing approaches for solving such problems rely on unrealistic assumptions or penalty function-based approximate reformulations that are not necessarily equivalent to the original problem. In this work, we develop a stochastic algorithm based on an implicit gradient approach, suitable for data-intensive applications. It is well-known that for the class of problems of interest, the implicit function is nonsmooth. To circumvent this difficulty, we apply a smoothing technique that involves adding small random (linear) perturbations to the LL objective and then taking the expectation of the implicit objective over these perturbations. This approach gives rise to a novel stochastic formulation that ensures the differentiability of the implicit function and leads to the design of a novel and efficient doubly stochastic algorithm. We show that the proposed algorithm converges to an $(ε, \overlineδ)$-Goldstein stationary point of the stochastic objective in $\widetilde{O}(ε^{-4} \overlineδ^{-1})$ iterations. Moreover, under certain additional assumptions, we establish the same convergence guarantee for the algorithm to achieve a $(3ε, \overlineδ + {O}(ε))$-Goldstein stationary point of the original objective. Finally, we perform experiments on adversarial training (AT) tasks to showcase the utility of the proposed algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04545 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Doubly Stochastically Perturbed Algorithm for Linearly Constrained Bilevel Optimization Khanduri, Prashant Tsaknakis, Ioannis Zhang, Yihua Liu, Sijia Hong, Mingyi Optimization and Control In this work, we develop analysis and algorithms for a class of (stochastic) bilevel optimization problems whose lower-level (LL) problem is strongly convex and linearly constrained. Most existing approaches for solving such problems rely on unrealistic assumptions or penalty function-based approximate reformulations that are not necessarily equivalent to the original problem. In this work, we develop a stochastic algorithm based on an implicit gradient approach, suitable for data-intensive applications. It is well-known that for the class of problems of interest, the implicit function is nonsmooth. To circumvent this difficulty, we apply a smoothing technique that involves adding small random (linear) perturbations to the LL objective and then taking the expectation of the implicit objective over these perturbations. This approach gives rise to a novel stochastic formulation that ensures the differentiability of the implicit function and leads to the design of a novel and efficient doubly stochastic algorithm. We show that the proposed algorithm converges to an $(ε, \overlineδ)$-Goldstein stationary point of the stochastic objective in $\widetilde{O}(ε^{-4} \overlineδ^{-1})$ iterations. Moreover, under certain additional assumptions, we establish the same convergence guarantee for the algorithm to achieve a $(3ε, \overlineδ + {O}(ε))$-Goldstein stationary point of the original objective. Finally, we perform experiments on adversarial training (AT) tasks to showcase the utility of the proposed algorithm. |
| title | A Doubly Stochastically Perturbed Algorithm for Linearly Constrained Bilevel Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2504.04545 |