Stochastic Frank-Wolfe Algorithm for Constrained Bilevel Optimization With Improved Per-Iteration Complexity

Jie Hou, Xianlin Zeng, Shisheng Cui, Xia Jiang, Jian SunIEEE TSP 2025 · OpenReview

Abstract

Bilevel optimization, where one optimization problem is inherently nested within another, has gained significant attention due to its extensive applications in machine learning, such as hyperparameter optimization and meta-learning. Most existing algorithms are designed to address unconstrained bilevel optimization problems, with few are capable of effectively tackling complex constrained settings. To address this gap, we propose a novel, fully single-loop stochastic Frank-Wolfe algorithm. This algorithm incorporates a Hessian-inverse-vector approximation technique, momentum-based gradient tracking, and a Frank-Wolfe update. Our proposed algorithm improves per-iteration complexity and achieves lower sample complexity compared to existing Frank-Wolfe algorithms for bilevel optimization. We also conduct numerical simulations to demonstrate the efficacy of our algorithm compared to state-of-the-art methods.
BibTeX
@article{hou2025stochastic,
  author = {Jie Hou and Xianlin Zeng and Shisheng Cui and Xia Jiang and Jian Sun},
  title = {{Stochastic Frank-Wolfe Algorithm for Constrained Bilevel Optimization With Improved Per-Iteration Complexity}},
  journal = {IEEE Trans. Signal Process.},
  year = {2025},
  url = {https://openreview.net/forum?id=GNC6mz1uW6},
}

Loading related content...

Figure