Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization

Abstract

In this paper, we consider non-convex stochastic bilevel optimization (SBO) problems that have many applications in machine learning. Although numerous studies have proposed stochastic algorithms for solving these problems, they are limited in two perspectives: (i) their sample complexities are high, which do not match the state-of-the-art result for non-convex stochastic optimization; (ii) their algorithms are tailored to problems with only one lower-level problem. When there are many lower-level problems, it could be prohibitive to process all these lower-level problems at each iteration. To address these limitations, this paper proposes fast randomized stochastic algorithms for non-convex SBO problems. First, we present a stochastic method for non-convex SBO with only one lower problem and establish its sample complexity of $O(1/{\epsilon }^3)$ for finding an $\epsilon$-stationary point under Lipschitz continuous conditions of stochastic oracles, matching the lower bound for stochastic smooth non-convex optimization. Second, we present a randomized stochastic method for non-convex SBO with $m>1$ lower level problems (multi-task SBO) by processing a constant number of lower problems at each iteration, and establish its sample complexity no worse than $O(m/{\epsilon }^3)$, which could be a better complexity than that of simply processing all $m$ lower problems at each iteration. Lastly, we establish even faster convergence results for gradient-dominant functions. To the best of our knowledge, this is the first work considering multi-task SBO and developing state-of-the-art sample complexity results.

References in corpus (11)

• DARTS: Differentiable Architecture Search
• Meta-Learning with Implicit Gradients
• Approximation Methods for Bilevel Programming
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• Accelerated Method for Stochastic Composition Optimization with Nonsmooth Regularization
• Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization
• Stochastically Controlled Stochastic Gradient for the Convex and Non-convex Composition problem
• Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence

Cited by in corpus (3)

• Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems
• BiAdam: Fast Adaptive Bilevel Optimization Methods
• Enhanced Bilevel Optimization via Bregman Distance