Projection-Free Algorithm for Stochastic Bi-level Optimization

Abstract

This work presents the first projection-free algorithm to solve stochastic bi-level optimization problems, where the objective function depends on the solution of another stochastic optimization problem. The proposed Stochastic Bi-level Frank-Wolfe (SBFW) algorithm can be applied to streaming settings and does not make use of large batches or checkpoints. The sample complexity of SBFW is shown to be O(^-3) for convex objectives and O(^-4) for non-convex objectives. Improved rates are derived for the stochastic compositional problem, which is a special case of the bi-level problem, and entails minimizing the composition of two expected-value functions. The proposed Stochastic Compositional Frank-Wolfe (SCFW) is shown to achieve a sample complexity of O(^-2) for convex objectives and O(^-3) for non-convex objectives, at par with the state-of-the-art sample complexities for projection-free algorithms solving single-level problems. We demonstrate the advantage of the proposed methods by solving the problem of matrix completion with denoising and the problem of policy value evaluation in reinforcement learning.

Tasks

Reproductions