Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods.

Area of Science:

• Optimization Theory
• Machine Learning
• Operations Research

Background:

• Online optimization deals with sequential decision-making where data arrives over time.
• Bilevel optimization involves nested optimization problems, common in hierarchical decision-making.
• Existing regret bounds are primarily for single-level online optimization.

Purpose of the Study:

• To introduce and analyze an online bilevel optimization framework for time-varying problems.
• To extend existing regret analysis from single-level to bilevel online optimization.
• To develop and evaluate a novel algorithm for this setting.

Main Methods:

• Definition of new bilevel regret notions tailored for the online setting.
• Development of an online alternating time-averaged gradient method.
• Analysis of regret bounds leveraging problem smoothness and path-length properties.

Main Results:

• Extension of regret bounds from single-level to bilevel online optimization.
• Introduction of a novel online alternating gradient method.
• Regret bounds are established in terms of the path-length of inner and outer minimizers.

Conclusions:

• The proposed methods effectively handle time-varying bilevel optimization problems.
• The new bilevel regret bounds provide theoretical guarantees for the developed algorithm.
• This work opens avenues for applying online bilevel optimization in dynamic, hierarchical systems.