Research map / Optimization / Nonconvex and smooth optimization
TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex 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 TSP, a single-loop stochastic primal-dual method with two-sided Moreau envelope smoothing for nonconvex bilevel optimization, proving O(ε^-4) iteration complexity to approximate KKT points.
Problem
Stochastic bilevel optimization where both upper- and lower-level objectives are nonconvex or weakly convex, without assuming LL strong convexity or unique LL solutions; existing penalty methods lack stochastic KKT guarantees.
Approach
Reformulates the bilevel problem via a Moreau envelope of the lower-level value function and runs a single-loop stochastic primal-dual method that adds proximal smoothing on both upper-level (x, y) variables and a moving-average dual update that dynamically weighs the lower-level constraint.
Key results
- On data hyper-cleaning, TSP reaches a peak test accuracy of 90.4% (variance 0.0429%) and F1 of 92.4%, versus 90.06% for BOME, 90.01% for PBGD, and 90.34% for MEHA.
- TSP converges faster in iterations than penalty baselines BOME, PBGD and MEHA on data hyper-cleaning, and attains the best generalization on the multi-head meta-learning task.
- Theoretical result: TSP finds (ε,ε)-approximate KKT points with O(ε^-4) iteration complexity with high probability, using constant or size-1 batches.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TSP instead of MEHA | MNIST data hyper-cleaning · MNIST data hyper-cleaning test | test accuracy: 90.34% ± 0.17% -> 90.4% with a variance of 0.0429% | Helped |
| Use TSP instead of MEHA | MNIST data hyper-cleaning · MNIST data hyper-cleaning | F1 score: 92.38% ± 0.12% -> 92.4% with a variance of 0.100% | Helped |
Surprising findings
- MEHA's test accuracy drops rapidly as training proceeds, which the authors attribute to penalty parameter growth causing LL overfitting.
Limitations
- Convergence analysis relies on bounded-noise and bounded-iterate assumptions, with a high-probability argument for boundedness of gradients and dual variable.
- Experiments are limited to small MNIST-based bilevel problems and small step-size grid searches.
- Rates depend on step-size choices of order O(1/sqrt(T)) and a penalty-like parameter p chosen as O(lambda).
Experimental setup
Datasets: MNIST
Benchmarks: MNIST data hyper-cleaning MNIST multi-head meta-learning
Metrics: test accuracy F1 score train accuracy convergence vs iterations
Baselines: BOME PBGD MEHA ANIL
Builds on: Moreau envelope bilevel reformulation (Gao et al., 2023) smoothed Lagrangian method (Zhang & Luo, 2020) MEHA (Liu et al., 2024a) PBGD (Shen & Chen, 2023)
Closest papers by meaning
- A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (ICML 2024 · similarity 0.91)
- An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (NeurIPS 2024 · similarity 0.91)
- Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.91)
- Generalized Smooth Bilevel Optimization with Nonconvex Lower-Level (ICML 2025 · similarity 0.91)
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.91)
- Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization (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.