# A Doubly Stochastically Perturbed Algorithm for Linearly Constrained Bilevel Optimization

arXiv: https://arxiv.org/abs/2504.04545 · HTML: https://mlsanity.com/paper/2504.04545/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2025.

## Built on by (most cited first, 2 of 2)

- [A Fully First-Order Layer for Differentiable Optimization](https://mlsanity.com/paper/2512.02494/) (2025)
- [Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints](https://mlsanity.com/paper/2511.09845/) (2025)

## Abstract (arXiv)

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 widetildeO(ε-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.