# Online Nonconvex Bilevel Optimization with Bregman Divergences

**Authors:** Jason Bohne, David Rosenberg, Gary Kazantsev, Pawel Polak  
**arXiv:** [2409.10470](https://arxiv.org/abs/2409.10470)  
**Date:** 2024-09-16  
**Summary page:** https://www.summarizepaper.com/en/paper/2409.10470v1/

## Key points

- Bilevel optimization methods are important in machine learning for tasks like hyperparameter optimization and meta-learning.
- Online bilevel optimization (OBO) is a dynamic framework for handling time-varying functions and sequentially arriving data.
- The study focuses on online nonconvex-strongly convex bilevel optimization in both deterministic and stochastic settings.
- In deterministic scenarios, the study introduces the online Bregman bilevel optimizer (OBBO) using adaptive Bregman divergences to enhance sublinear rates for bilevel local regret.
- OBBO achieves enhancement through a unique hypergradient error decomposition that adapts to the problem's geometry.
- In stochastic contexts, the study presents the first stochastic online bilevel optimizer (SOBBO) which uses window averaging to update outer-level variables with recent stochastic approximations of hypergradients.
- SOBBO achieves sublinear rates of bilevel local regret and serves as an effective variance reduction strategy by eliminating additional stochastic gradient samples at each timestep.
- Experimental results demonstrate superior performance, efficiency, and adaptability of these Bregman-based algorithms compared to established benchmarks in tasks like online hyperparameter optimization and meta-learning.

## Summary

In the realm of machine learning, bilevel optimization methods have gained increasing relevance in tasks such as hyperparameter optimization and meta-learning. One area of interest within this field is online bilevel optimization (OBO), which provides a dynamic framework for handling time-varying functions and sequentially arriving data. This study delves into the realm of online nonconvex-strongly convex bilevel optimization, addressing challenges in both deterministic and stochastic settings. In deterministic scenarios, the study introduces a novel approach known as the online Bregman bilevel optimizer (OBBO), utilizing adaptive Bregman divergences to enhance sublinear rates for bilevel local regret. This enhancement is achieved through a unique hypergradient error decomposition that adapts to the underlying geometry of the problem at hand. On the other hand, in stochastic contexts, the study presents the first stochastic online bilevel optimizer (SOBBO). This method employs a window averaging technique to update outer-level variables using a weighted average of recent stochastic approximations of hypergradients. Notably, SOBBO not only achieves sublinear rates of bilevel local regret but also serves as an effective variance reduction strategy by eliminating the need for additional stochastic gradient samples at each timestep. Experimental results on tasks like online hyperparameter optimization and online meta-learning showcase the superior performance, efficiency, and adaptability of these Bregman-based algorithms compared to established online and offline bilevel benchmarks. The study contributes valuable insights into optimizing nonconvex-strongly convex problems in both deterministic and stochastic environments, paving the way for advancements in dynamic optimization frameworks within machine learning applications.