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 appropriate conditions , 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 by processing only one lower problem at each iteration, and establish its sample complexity no worse than O(m/\epsilon^3), which could have a better complexity than  simply processing all m lower problems at each iteration.  To the best of our knowledge, this is the first work considering SBO with many lower level problems and establishing state-of-the-art sample complexity  .
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 .
R
appropriate conditions
Lipschitz continuous conditions of stochastic oracles
R
by processing only one lower problem
(multi-task SBO) by processing a constant number of lower problems
R
have
be
A
that of
A
Lastly, we establish even faster convergence results for gradient-dominant functions.
R
SBO with many lower level problems and establishing
multi-task SBO and developing
A
results