Research map / Optimization / Optimizers
First-Order Minimax Bilevel Optimization
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 FOSL, a fully first-order single-loop method, and MemCS, a memory-efficient cold-start double-loop method, for multi-block minimax bilevel optimization, evaluated on deep AUC maximization and rank-based robust meta-learning.
Problem
Multi-block minimax bilevel optimization is costly because existing algorithms need second-order Hessian computations or store all block-specific parameters, which is memory-intensive for many blocks such as few-shot meta-learning.
Approach
Reformulate the lower-level constraint as a value-function Lagrangian turning the problem into a single minimax problem; FOSL updates all variables simultaneously with first-order gradients, while MemCS re-initializes block-specific variables randomly each round (cold start) and runs K inner gradient steps, avoiding storage of block parameters.
Key results
- FOSL achieves test AUC 0.9540 on CIFAR100 vs 0.9272 for mAUC-CT and 0.9044 for mAUC, and 0.8516 on OGBG-MolPCBA vs 0.8406 for mAUC-CT.
- MemCS reaches 69.25% clean test accuracy on Mini-ImageNet vs 64.75% for MAML, and 60.25% vs 52.50% under random noise.
- FOSL convergence is O(T^{-2/7}) with sample complexity O(P eps^{-7/2}); MemCS achieves per-block sample complexity of order eps^{-1} with full-block participation, claimed to improve F2SA by eps^{-0.5}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use FOSL instead of mAUC | deep AUC maximization · CIFAR100, CelebA, CheXpert, and OGBG-MolPCBA | test AUC: 0.9044 (0.0015) -> 0.9540 (0.0009); 0.9062 (0.0042) -> 0.9267 (0.0018); 0.8084 (0.1455) -> 0.8166 (0.0051); 0.7793 (0.00 | Mixed |
| use FOSL instead of mAUC-CT | deep AUC maximization · CIFAR100, CelebA, CheXpert, and OGBG-MolPCBA | test AUC: 0.9272 (0.0014) -> 0.9540 (0.0009); 0.9192 (0.0004) -> 0.9267 (0.0018); 0.8198 (0.1495) -> 0.8166 (0.0051); 0.8406 (0.00 | Mixed |
| use MemCS instead of MAML | few-shot meta-learning · Mini-ImageNet and Tiered-ImageNet, Clean, Flip, and Rand | test accuracy (%): 64.75 -> 69.25; 52.75 -> 57.50; 52.50 -> 60.25; 66.25 -> 67.25; 44.75 -> 57.00; 54.25 -> 59.75 | Helped |
| use MemCS instead of MAML as the Flip noisy ratio increases | few-shot meta-learning · Mini-ImageNet and Tiered-ImageNet, Flip noisy ratios 0.2–0.8 | test accuracy (%): 59.50 -> 65.00; 56.50 -> 61.75; 52.75 -> 57.50; 42.00 -> 53.50; 63.75 -> 66.50; 53.25 -> 62.75; 44.75 -> 57.00; 39.00 -> | Helped |
| vary the FOSL penalty parameter λ (ablation) | FOSL · CIFAR100 and CelebA | test AUC | No clear effect |
Surprising findings
- MemCS achieves linear speedup in the number of blocks under partial participation, claimed as the first such result in multi-block minimax bilevel optimization.
Limitations
- Theoretical guarantees rely on strong assumptions such as strong convexity of the lower level and bounded lower-level solutions for MemCS partial participation.
- Lagrangian multiplier lambda must be large enough for approximation, but too large values inflate gradient variance and slow convergence.
- FOSL requires storing all block-specific parameters, which is memory-prohibitive when many blocks exist.
Experimental setup
Datasets: CIFAR100 CelebA CheXpert OGBG-MolPCBA Mini-ImageNet Tiered-ImageNet
Benchmarks: CIFAR100 CelebA CheXpert OGBG-MolPCBA Mini-ImageNet Tiered-ImageNet
Metrics: test AUC test accuracy average iteration time model parameter size
Baselines: mAUC mAUC-CT MAML
Builds on: F2SA bilevel optimization via value-function Lagrangian multi-block minimax AUC maximization (mAUC-CT) MAML
Closest papers by meaning
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.90)
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling (NeurIPS 2024 · similarity 0.89)
- A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (ICML 2024 · similarity 0.88)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.88)
- Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis (ICLR 2025 · similarity 0.88)
- A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization (NeurIPS 2025 · similarity 0.88)
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.