mlsanityData to 7 Oct 2026

Projection-Free Algorithm for Stochastic Bi-level Optimization

arXiv 2110.11721 ↗First posted 22 Oct 2021math.OC cs.CC cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 39 of its 66 references that are in the map. First posted on arXiv 22 Oct 2021.

Builds on

39 of 66 references.

References · 39

  1. 2019Meta-Learning with Implicit Gradientscited by 523
  2. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  3. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  4. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  5. 2018Approximation Methods for Bilevel Programmingcited by 231
  6. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 219
  7. 2020Coresets via Bilevel Optimization for Continual Learning and Streamingcited by 191
  8. 2020On the Iteration Complexity of Hypergradient Computationcited by 154
  9. 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
  10. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  11. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 93
  12. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
27 more
  1. 2016Convergence Rate of Frank-Wolfe for Non-Convex Objectivescited by 59
  2. 2018A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimizationcited by 53
  3. 2020Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimizationcited by 51
  4. 2018Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximizationcited by 47
  5. 2016Accelerating Stochastic Composition Optimizationcited by 46
  6. 2016Variance-Reduced and Projection-Free Stochastic Optimizationcited by 40
  7. 2016Stochastic Frank-Wolfe Methods for Nonconvex Optimizationcited by 40
  8. 2019Bi-level Actor-Critic for Multi-agent Coordinationcited by 38
  9. 2021BiAdam: Fast Adaptive Bilevel Optimization Methodscited by 33
  10. 2019One Sample Stochastic Frank-Wolfecited by 32
  11. 2021Enhanced Bilevel Optimization via Bregman Distancecited by 28
  12. 2019A Stochastic Composite Gradient Method with Incremental Variance Reductioncited by 26
  13. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 21
  14. 2021Bilevel methods for image reconstructioncited by 20
  15. 2019Efficient Projection-Free Online Methods with Stochastic Recursive Gradientcited by 19
  16. 2016Finite-sum Composition Optimization via Variance Reduced Gradient Descentcited by 15
  17. 2016Investigating practical linear temporal difference learningcited by 13
  18. 2017Accelerated Method for Stochastic Composition Optimization with Nonsmooth Regularizationcited by 13
  19. 2020Addressing Catastrophic Forgetting in Few-Shot Problemscited by 12
  20. 2020Conservative Stochastic Optimization with Expectation Constraintscited by 10
  21. 2019Low-rank matrix completion and denoising under Poisson noisecited by 6
  22. 2019Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimizationcited by 6
  23. 2020Stochastic Recursive Momentum Method for Non-Convex Compositional Optimizationcited by 6
  24. 2021Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimizationcited by 6
  25. 2017Variance Reduced methods for Non-convex Composition Optimizationcited by 5
  26. 2020Stochastic Compositional Gradient Descent under Compositional Constraintscited by 3
  27. 2020Supervised Learning of Sparsity-Promoting Regularizers for Denoisingcited by 2

Built on by

Cited by year

Citing papers per year: 2023: 4; 2024: 4.

8 papers.

  1. 2023An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learningcited by 39
  2. 2023PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedbackcited by 38
  3. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  4. 2023Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problemcited by 13
  5. 2024First-Order Methods for Linearly Constrained Bilevel Optimizationcited by 10
  6. 2024Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applicationscited by 4
  7. 2024Differentially Private Bilevel Optimizationcited by 2
  8. 2024Exploring the Generalization Capabilities of AID-based Bi-level Optimizationcited by 1