Contextual Stochastic Bilevel Optimization
We introduce contextual stochastic bilevel optimization (CSBO) -- a stochastic bilevel optimization framework with the lower-level problem minimizing an expectation conditioned on some contextual information and the upper-level decision variable. This framework extends classical stochastic bilevel optimization when the lower-level decision maker responds optimally not only to the decision of the upper-level decision maker but also to some side information and when there are multiple or even infinite many followers. It captures important applications such as meta-learning, personalized federated learning, end-to-end learning, and Wasserstein distributionally robust optimization with side information (WDRO-SI). Due to the presence of contextual information, existing single-loop methods for classical stochastic bilevel optimization are unable to converge. To overcome this challenge, we introduce an efficient double-loop gradient method based on the Multilevel Monte-Carlo (MLMC) technique and establish its sample and computational complexities. When specialized to stochastic nonconvex optimization, our method matches existing lower bounds. For meta-learning, the complexity of our method does not depend on the number of tasks. Numerical experiments further validate our theoretical results.
Code (0)
등록된 구현이 없습니다.
Tasks
Bilevel OptimizationFederated LearningMeta-LearningPersonalized Federated LearningSimilar Papers 제목 키워드 기반
Contextual Bilevel Reinforcement Learning for Incentive Alignment
The optimal policy in various real-world strategic decision-making problems depends both on the environmental configuration and exogenous events. For these settings, we introduce Contextual Bilevel Reinforcement Learning…
Bilevel OptimizationDecision Makingreinforcement-learningReinforcement LearningA Single-Timescale Method for Stochastic Bilevel Optimization
Stochastic bilevel optimization generalizes the classic stochastic optimization from the minimization of a single objective to the minimization of an objective function that depends the solution of another optimization p…
Bilevel OptimizationMeta-LearningStochastic OptimizationNonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise
Existing decentralized stochastic optimization methods assume the lower-level loss function is strongly convex and the stochastic gradient noise has finite variance. These strong assumptions typically are not satisfied i…
Stochastic OptimizationBilevel OptimizationEnhanced Bilevel Optimization via Bregman Distance
Bilevel optimization has been recently used in many machine learning problems such as hyperparameter optimization, policy optimization, and meta learning. Although many bilevel optimization methods have been proposed, th…
Bilevel OptimizationHyperparameter OptimizationMeta-LearningRepresentation LearningOnline Nonconvex Bilevel Optimization with Bregman Divergences
Bilevel optimization methods are increasingly relevant within machine learning, especially for tasks such as hyperparameter optimization and meta-learning. Compared to the offline setting, online bilevel optimization (OB…
Bilevel OptimizationHyperparameter OptimizationMeta-Learning