Research map / Optimization / Nonconvex and smooth optimization
Generalized Smooth Bilevel Optimization with Nonconvex Lower-Level
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 PNGBiO and S-PNGBiO, Hessian/Jacobian-free single-loop penalty normalized-gradient methods for bilevel optimization where both upper- and lower-level objectives are generalized-smooth and the lower level is nonconvex.
Problem
Bilevel optimization in which both upper- and lower-level objectives violate standard smoothness (generalized smoothness) and the lower-level problem is nonconvex, so the usual closed-form hypergradient does not apply.
Approach
Solves a Moreau-envelope penalty reformulation of the bilevel problem with normalized gradient steps on x and y and an auxiliary variable theta approximating the proximal lower-level solution, using only first-order gradients and assuming generalized smoothness for both levels with weak convexity of the lower level.
Key results
- PNGBiO achieves O(1/T^{1/4}) stationarity convergence rate in the deterministic setting, i.e., gradient complexity O(eps^-4).
- S-PNGBiO achieves O(1/T^{1/6}) stationarity rate in the stochastic setting, with stated gradient complexity O(eps^-9).
- On data hyper-cleaning and hyper-parameter learning (MNIST, FashionMNIST), PNGBiO reports higher test accuracy and lower loss than baselines, though slower than F2SA; S-PNGBiO converges faster than baselines on CIFAR10 meta learning under equal runtime.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PNGBiO instead of the compared methods | Data hyper-cleaning · MNIST | test accuracy | Helped |
| Use PNGBiO instead of the compared methods | Data hyper-cleaning · FashionMNIST | test accuracy | Helped |
| Use PNGBiO instead of the compared methods | Data hyper-cleaning · MNIST | test loss | Helped |
| Use PNGBiO instead of the compared methods | Data hyper-cleaning · FashionMNIST | test loss | Helped |
| Use PNGBiO instead of F2SA | Data hyper-cleaning · MNIST and FashionMNIST | convergence speed | Hurt |
| Use PNGBiO instead of the compared methods | Hyper-parameter learning · MNIST | test accuracy | Helped |
| Use PNGBiO instead of the compared methods | Hyper-parameter learning · FashionMNIST | test accuracy | Helped |
| Use PNGBiO instead of the compared methods | Hyper-parameter learning · MNIST and FashionMNIST | test loss | Helped |
| Use PNGBiO instead of F2SA | Hyper-parameter learning · MNIST and FashionMNIST | convergence speed | Hurt |
| Use S-PNGBiO instead of the compared methods | Meta learning · CIFAR10 | test accuracy | Helped |
| Use S-PNGBiO instead of the compared methods | Meta learning · CIFAR10 | test loss | Helped |
| Use S-PNGBiO instead of the compared methods | Meta learning · CIFAR10 | convergence speed | Helped |
Surprising findings
- PNGBiO converges more slowly than F2SA in the hyper-cleaning and hyper-parameter learning experiments, which the authors attribute to F2SA's momentum acceleration.
Limitations
- Convergence rates (T^{-1/4} deterministic, T^{-1/6} stochastic) are slower than standard smooth bilevel results.
- Empirical convergence is slower than F2SA on hyper-cleaning and hyper-parameter tasks due to lack of momentum.
- Requires batch size growing with T (B_t = O(T^{1/2})) in the stochastic setting and assumes a generalized-smoothness exponent rho in [0,1].
Experimental setup
Datasets: MNIST FashionMNIST CIFAR10
Benchmarks: MNIST FashionMNIST CIFAR10
Metrics: test accuracy test loss convergence rate gradient complexity
Baselines: BOME F2SA PBGD MEHA SLIP
Builds on: Moreau envelope bilevel formulation (MEHA) penalty-based bilevel methods generalized smoothness (Chen et al., 2023) normalized gradient descent
Closest papers by meaning
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.91)
- Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization (ICML 2024 · similarity 0.91)
- A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (ICML 2024 · similarity 0.90)
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.90)
- Double Momentum Method for Lower-Level Constrained Bilevel Optimization (ICML 2024 · similarity 0.90)
- Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis (ICLR 2024 · 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.