Research map / Optimization / Nonconvex and smooth optimization
Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes WiOR-BO and WiOR-CBO, bilevel optimization algorithms that use without-replacement (random-reshuffling / shuffle-once) example sampling instead of independent sampling, achieving O(ε^-3) for bilevel and O(ε^-4) for conditional bilevel, with experiments on synthetic IRM, hyper-data cleaning, and hyper-representation learning.
Problem
Bilevel optimization methods typically require mutually independent sampling of examples for outer and inner gradient/Hessian estimates, which raises the per-iteration backward-pass cost for large models and slows convergence.
Approach
Replace independent sampling with permutation-based without-replacement example orders shared across the hyper-gradient components (reusing the same example for several derivatives), and analyze convergence with an aggregated block-wise analysis that exploits the faster gradient-averaging error O(K^-2) of permutation orders.
Key results
- WiOR-CBO (shuffle-once and random-reshuffling) outperforms DL-SGD and is comparable to RT-MLMC on Omniglot hyper-representation learning, per the authors.
- Theory: WiOR-BO reaches an epsilon-stationary point with O(epsilon^-3) steps versus O(epsilon^-4) for independent-sampling stocBiO/SOBA; WiOR-CBO achieves O(epsilon^-4) sample complexity versus O(epsilon^-6) for DL-SGD.
- On hyper-data cleaning, WiOR-BO-SO and WiOR-BO-RR achieve similar performance and both outperform the listed baselines in validation loss/F1 vs. iterations and running time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use permutation-based without-replacement sampling instead of independent sampling | WiOR-BO · Bilevel optimization | gradient evaluation complexity to reach an ε-stationary point: O(ε^{-4}) -> O((max(m,n))^{q}ε^{-3}) | Helped |
| Use permutation-based without-replacement sampling instead of independent sampling | WiOR-CBO · Conditional bilevel optimization | sample complexity to reach an ε-stationary point: O(ε^{-6}) -> O((max(m,n))^{2q}ε^{-4}) | Helped |
| Use a herding-based permutation with q=0 | WiOR-BO · Bilevel optimization | gradient evaluation complexity to reach an ε-stationary point: O((max(m,n))^{q}ε^{-3}) | Helped |
| Use a q=0 example order | WiOR-CBO · Conditional bilevel optimization | sample complexity to reach an ε-stationary point: O((max(m,n))^{2q}ε^{-4}) | Helped |
| Use shuffle-once or random-reshuffling instead of independent sampling | WiOR-CBO · Invariant Risk-Minimization | performance | Helped |
| Use shuffle-once or random-reshuffling instead of independent sampling | WiOR-BO · Hyper-Data Cleaning (MNIST, noisy fraction 0.6) | validation loss | Helped |
| Use shuffle-once or random-reshuffling instead of independent sampling | WiOR-BO · Hyper-Data Cleaning (MNIST, noisy fraction 0.6) | F1 score | Helped |
| Use shuffle-once or random-reshuffling instead of independent sampling | WiOR-CBO · Omniglot N-way-K-shot classification | classification performance | Helped |
| Use independent sampling instead of without-replacement sampling (ablation) | WiOR-CBO · Hyper-representation learning | classification performance | No clear effect |
| Use shuffle-once or random-reshuffling instead of independent sampling | WiOR-BO · Hyper-Data Cleaning (MNIST, noisy fraction 0.6) | convergence speed versus running time | Helped |
Limitations
- Convergence depends on the gradient-averaging constant C, which grows with max(m,n) for random-reshuffling and shuffle-once orders unless sample order is carefully chosen (e.g., herding).
- Analysis assumes non-convex-strongly-convex inner problems and bounded sample-gradient errors, and the herding-based q=0 improvement is only cited rather than implemented.
- Experiments are small-scale benchmarks (MNIST, Omniglot, MiniImageNet) and the paper does not evaluate on large-scale models.
Experimental setup
Datasets: MNIST Omniglot MiniImageNet synthetic invariant risk minimization data
Benchmarks: synthetic invariant risk minimization MNIST hyper-data cleaning Omniglot N-way K-shot MiniImageNet N-way K-shot
Metrics: validation loss F1 score validation error running time hyper-iterations
Baselines: reverse stocBiO BSA AID-CG MRBO VRBO WiR-BO DL-SGD RT-MLMC
Builds on: stocBiO SOBA single-loop bilevel optimization random reshuffling DL-SGD
Closest papers by meaning
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.91)
- Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.91)
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.90)
- Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis (ICLR 2025 · similarity 0.90)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.90)
- Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets (NeurIPS 2026 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.