Enhanced Bilevel Optimization via Bregman Distance

Abstract

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, they still suffer from the high computational complexities and do not consider the more general bilevel problems with nonsmooth regularization. In the paper, thus, we propose a class of enhanced bilevel optimization methods with using Bregman distance to solve bilevel optimization problems, where the outer subproblem is nonconvex and possibly nonsmooth, and the inner subproblem is strongly convex. Specifically, we propose a bilevel optimization method based on Bregman distance (BiO-BreD) to solve deterministic bilevel problems, which achieves a lower computational complexity than the best known results. Meanwhile, we also propose a stochastic bilevel optimization method (SBiO-BreD) to solve stochastic bilevel problems based on stochastic approximated gradients and Bregman distance. Moreover, we further propose an accelerated version of SBiO-BreD method (ASBiO-BreD) using the variance-reduced technique, which can achieve a lower computational complexity than the best known computational complexities with respect to condition number $\kappa$ and target accuracy $\epsilon$ for finding an $\epsilon$-stationary point. We conduct data hyper-cleaning task and hyper-representation learning task to demonstrate that our new algorithms outperform related bilevel optimization approaches.

arXiv commentPublished in NeurIPS 2022

References in corpus (17)

• DARTS: Differentiable Architecture Search
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Bilevel Programming for Hyperparameter Optimization and Meta-Learning
• Approximation Methods for Bilevel Programming
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
• Bilevel Optimization: Convergence Analysis and Enhanced Design
• Momentum-Based Variance Reduction in Non-Convex SGD
• On the Adaptivity of Stochastic Gradient-Based Optimization
• A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization
• Provably Faster Algorithms for Bilevel Optimization
• SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients
• BiAdam: Fast Adaptive Bilevel Optimization Methods
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization
• Bregman Gradient Policy Optimization

Cited by in corpus (2)

• Communication-Efficient Robust Federated Learning with Noisy Labels
• Projection-Free Algorithm for Stochastic Bi-level Optimization