Research map / Optimization / Optimizers
Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-Loop and Hessian-Free Solution Strategy
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 MEHA, a single-loop, Hessian-free first-order algorithm for nonconvex-nonconvex bi-level optimization based on a Moreau envelope reformulation of the lower-level problem, with non-asymptotic convergence guarantees.
Problem
Bi-level optimization with nonconvex (and possibly nonsmooth) lower-level problems, where existing methods are either Hessian-based, double-loop, or require PL conditions and lack non-asymptotic guarantees.
Approach
Reformulates BLO via the Moreau envelope of the lower-level problem (penalizing value-function gap), and solves the penalized approximation with a single-loop alternating proximal gradient scheme where the Moreau envelope gradient is approximated by one proximal gradient step on a proximal lower-level problem, avoiding Hessians.
Key results
- On 10-way Omniglot few-shot, MEHA reaches 91.17% accuracy in 130.81 s versus 180.48 s for BAMM and 557.71 s for RHG.
- On the NAS task, MEHA achieves 96.07% test accuracy versus 95.57% for DARTS and 95.84% for IAPTT, with 1.524M params.
- On the LL-nonsmooth lasso toy with dimension 1000, MEHA takes 22.83 s versus 2244.44 s for TPE and 700.74 s for random search.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Single-loop Hessian-free MEHA versus BOME, IAPTT, BVFIM | LL non-convex synthetic problem, dim 1000 · LL non-convex synthetic | Time (S): 47.45 vs 68.65 (BOME), 3537.19 (IAPTT) | Helped |
| MEHA versus grid, random, TPE search for lasso hyperparameters | LL non-smooth lasso, dim 1000 · Lasso hyperparameter selection | Time (S): 22.83 vs 2244.44 (TPE) | Helped |
| MEHA versus VF-iDCA and IGJO on group lasso | Group lasso hyperparameter selection · Synthetic, m=1200 and m=3600 | Test Err.: 84.3 vs 85.2 (m=1200); 89.5 vs 90.0 (m=3600); gains small and within std | Mixed |
| MEHA versus BAMM on few-shot learning | Omniglot 10-way 1-shot · Few-shot 10-way | Time (S): 130.81 vs 180.48 (BAMM), at 91.17% accuracy | Helped |
| MEHA versus BAMM and others on 20-way few-shot | Omniglot 20-way 1-shot · Few-shot 20-way | Acc. (%): 89.96 vs 90.13 (BAMM), 90.17 (RHG) | No clear effect |
| MEHA versus BOME, VPBGD on data hyper-cleaning | FashionMNIST and MNIST hyper-cleaning · Data hyper-cleaning | Acc. (%): 83.19 vs 82.16 (BOME, FashionMNIST); 89.55 vs 89.10 (VPBGD, MNIST) | Helped |
| MEHA versus DARTS, P-DARTS, IAPTT on NAS | CIFAR-10 differentiable NAS · NAS test top-1 | Top-1 acc (%): 96.070 vs 95.809 (IAPTT), 95.710 (P-DARTS), 95.569 (DARTS) | Helped |
| Smooth Swish activation search space versus non-smooth activations in NAS (ablation) | MEHA NAS · NAS CIFAR-10 | Test Top-1 acc (%): 95.870 (smooth) vs 96.070 (non-smooth) | Hurt |
| MEHA versus BAMM, NS, CG, RHG on LL strong-convex synthetic | LL strong-convex synthetic, dim 10000 · Synthetic strong convex | Time (S): 1.973 vs 5.890 (BAMM), 36.97 (CG) | Helped |
| Increasing outer penalty exponent p from 0.05 to 0.49 (sensitivity, lasso dim 1000) (ablation) | MEHA · Lasso LL non-smooth dim 1000 | Steps: 956 steps at p=0.05 vs 97 steps at p=0.49 | Helped |
| Larger step size alpha (0.1 to 0.8) for x update (ablation) | MEHA · Lasso LL non-smooth dim 1000 sensitivity | Time (S): 9.65 at alpha=0.8 vs 22.83 original | Helped |
| Smaller eta (0.01 vs 0.1) for theta proximal step (ablation) | MEHA · Lasso LL non-smooth dim 1000 sensitivity | Time (S): 51.99 vs 22.83 original | Hurt |
Surprising findings
- MEHA's reported NAS test accuracy (96.07%) is higher than the DARTS baseline that the paper's search space follows, yet the parameter count is larger than DARTS (1.277M)
- Several baselines (e.g., some methods) fail to converge to the correct solution on the LL-merely-convex toy problem, while MEHA converges.
Limitations
- Theory requires weak convexity/smoothness assumptions and step-size conditions (penalty c_k growth, gamma bounds) that are hard to verify in practice
- Stochastic extension (variance reduction, momentum) left to future work
- Hyperparameter sensitivity: convergence depends on alpha, beta, eta, gamma, c, p choices
Experimental setup
Datasets: Omniglot MNIST FashionMNIST CIFAR-10 synthetic data
Benchmarks: Omniglot MNIST FashionMNIST CIFAR-10 synthetic BLO toy problems
Metrics: accuracy F1 score running time relative error ||x-x*||/||x*|| test error top-1 accuracy parameter count
Baselines: IAPTT BOME BVFIM RHG BDA CG BAMM IGJO VF-iDCA VPBGD TPE DARTS
Builds on: value function reformulation of BLO Moreau envelope BLO reformulation (inexact proximal DC algorithm) DARTS BOME IAPTT
Closest papers by meaning
- Constrained Bi-Level Optimization: Proximal Lagrangian Value Function Approach and Hessian-free Algorithm (ICLR 2024 · similarity 0.88)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.88)
- Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions (ICML 2024 · similarity 0.87)
- qNBO: quasi-Newton Meets Bilevel Optimization (ICLR 2025 · similarity 0.87)
- A Bregman Proximal Stochastic Gradient Method with Extrapolation for Nonconvex Nonsmooth Problems (AAAI 2024 · similarity 0.87)
- Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization (ICML 2024 · similarity 0.86)
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.