Research map / Optimization / Nonconvex and smooth optimization
Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis
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 two fully tuning-free bilevel optimizers, D-TFBO (double-loop) and S-TFBO (single-loop), using inverse-of-cumulative-gradient-norm adaptive stepsizes, with O(1/T) and O(log^4(T)/T) rates respectively.
Problem
Bilevel optimization with nonconvex outer and strongly convex inner problems requires tuning stepsizes that depend on unknown problem parameters (Lipschitz, strong convexity, optimal values).
Approach
Adapt all stepsizes via inverse of accumulated (hyper)gradient norms: cold-start stepsizes in sub-loops for D-TFBO, and a theory-motivated joint stepsize design (1/beta for y, 1/max(beta,gamma) for v, 1/(alpha*max(beta,gamma)) for x) updated simultaneously for S-TFBO.
Key results
- D-TFBO achieves O(1/T) convergence matching well-tuned AID methods, with gradient complexity O(1/epsilon^2); S-TFBO achieves O(log^4(T)/T) rate with gradient complexity O(1/epsilon log^4(1/epsilon)).
- On Split CIFAR100 coreset selection, D-TFBO reaches 59.54% balanced average accuracy and S-TFBO 58.90%, versus BCSR's 61.60%, with comparable results.
- Under initial stepsize variations in {2,4,6,8}, relative average accuracy change is 0.3% for D-TFBO and 0.4% for S-TFBO versus 5.8% for BCSR.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use D-TFBO instead of BCSR | coreset selection · Split CIFAR100 balanced | FGT_T: 0.051±0.015 -> 0.041±0.005 | Helped |
| use D-TFBO instead of BCSR | coreset selection · Split CIFAR100 imbalanced | A_T: 47.30±0.57 -> 46.68±0.72 | Hurt |
| use D-TFBO instead of BCSR | coreset selection · Split CIFAR100 imbalanced | FGT_T: 0.022±0.005 -> 0.029±0.002 | Hurt |
| use D-TFBO instead of S-TFBO | coreset selection · Split CIFAR100 balanced | FGT_T: 0.046±0.009 -> 0.041±0.005 | Helped |
| vary initial values across 2, 4, 6, and 8 | D-TFBO · Split CIFAR100 balanced | Relative Average Change: 5.8% -> 0.3% | Helped |
| vary initial values across 2, 4, 6, and 8 | S-TFBO · Split CIFAR100 balanced | Relative Average Change: 5.8% -> 0.4% | Helped |
Surprising findings
- Double-loop tuning-free method has worse gradient complexity (1/epsilon^2) than single-loop tuning-free method (1/epsilon log^4(1/epsilon)), reversing the usual well-tuned ordering.
Limitations
- Tuning-free design yields sub-linear sub-loop convergence, giving worse gradient complexity than well-tuned double-loop methods by a factor of 1/epsilon.
- Analysis limited to deterministic setting; stochastic extension left open.
- Practical D-TFBO uses fixed loop counts as approximation to the stopping criteria.
Experimental setup
Datasets: Covtype MNIST Split CIFAR100
Benchmarks: Covtype regularization selection MNIST data hyper-cleaning Split CIFAR100 coreset selection
Metrics: convergence vs running time average accuracy forgetting measure relative average change under initial stepsize sensitivity
Baselines: AmIGO BSA FSLA MRBO SOBA StocBiO SUSTAIN TTSA VRBO BCSR PBCS iCaRL
Builds on: AdaGrad-Norm AdaNGD AID-based bilevel methods Polyak stepsize bilevel methods
Closest papers by meaning
- Problem-Parameter-Free Decentralized Bilevel Optimization (NeurIPS 2025 · similarity 0.91)
- Double Momentum Method for Lower-Level Constrained Bilevel Optimization (ICML 2024 · similarity 0.90)
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling (NeurIPS 2024 · similarity 0.90)
- Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis (ICLR 2024 · similarity 0.90)
- A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (ICML 2024 · similarity 0.90)
- A Single-Loop Gradient Algorithm for Pessimistic Bilevel Optimization via Smooth Approximation (NeurIPS 2025 · 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.