Research map / Optimization / Nonconvex and smooth optimization
Double Momentum Method for Lower-Level Constrained 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 DMLCBO, a single-loop single-timescale double-momentum method for lower-level constrained bilevel optimization that uses a randomized-smoothing, Neumann-series hypergradient, with a (δ,ε)-stationarity guarantee of Õ(d₂²ε⁻⁴) iterations.
Problem
Bilevel optimization where the lower-level problem has convex constraints, so the upper-level objective is nonsmooth and existing hypergradient methods need restrictive differentiability/invertibility assumptions and lack convergence-rate guarantees or are double-loop.
Approach
Derives a generalized (nonsmooth implicit function theorem) hypergradient for LCBO, smooths the projection operator by randomized smoothing, approximates the inverse Hessian-like term with a Neumann series and randomized truncation, and runs a single-loop single-timescale double-momentum update with adaptive step sizes.
Key results
- On data hyper-cleaning, DMLCBO reports the highest test accuracy on all four datasets (e.g., 94.24% on MNIST 6vs9 vs 93.53% for V-PBGD).
- On meta-learning, DMLCBO reports 85.25% on FC100 5-way 5-shot vs 84.75% for RMD-PCD and 86.93% on FC100 10-way 5-shot vs 81.18% for RMD-PCD.
- Theory: returns a (δ,ε)-stationary point with Õ(d₂²ε⁻⁴) iterations under the stated assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DMLCBO instead of V-PBGD | Data hyper-cleaning · CodRNA | test accuracy (%): 80.32 ± 0.09 -> 80.42 ± 0.05 | Helped |
| use DMLCBO instead of V-PBGD | Data hyper-cleaning · MNIST 6vs9 | test accuracy (%): 93.53 ± 0.34 -> 94.24 ± 0.01 | Helped |
| use DMLCBO instead of Approx | Data hyper-cleaning · Madelon | test accuracy (%): 54.75 ± 1.08 -> 56.33 ± 1.83 | Helped |
| use DMLCBO instead of RMD-PCD | Data hyper-cleaning · FashionMNIST 1vs7 | test accuracy (%): 88.93 ± 0.68 -> 88.85 ± 0.60 | Hurt |
| use DMLCBO instead of RMD-PCD | Meta-learning · Omniglot 5 way 5 shot | test accuracy (%): 99.69 ± 0.37 -> 99.97 ± 0.04 | Helped |
| use DMLCBO instead of Approx | Meta-learning · Omniglot 10 way 5 shot | test accuracy (%): 99.57 ± 0.17 -> 99.81 ± 0.19 | Helped |
| use DMLCBO instead of RMD-PCD | Meta-learning · FC100 5 way 5 shot | test accuracy (%): 84.75 ± 0.65 -> 85.25 ± 0.01 | Helped |
| use DMLCBO instead of RMD-PCD | Meta-learning · FC100 10 way 5 shot | test accuracy (%): 81.18 ± 0.39 -> 86.93 ± 0.89 | Helped |
| set Q=1 instead of Q=3 (ablation) | DMLCBO · Data hyper-cleaning benchmarks | test accuracy (%): CodRNA: 80.42 ± 0.05 -> 80.25 ± 0.07; MNIST 6vs9: 94.24± 0.01 -> 93.65 ± 0.01; Madelon: 56.33 ± 1.83 -> 55.23 ± 1.22; Fa | Hurt |
| set Q=5 instead of Q=3 (ablation) | DMLCBO · Data hyper-cleaning benchmarks | test accuracy (%): CodRNA: 80.42 ± 0.05 -> 80.55 ± 0.03; MNIST 6vs9: 94.24± 0.01 -> 94.15 ± 0.01; Madelon: 56.33 ± 1.83 -> 56.67 ± 1.24; Fa | Mixed |
| set Q=7 instead of Q=3 (ablation) | DMLCBO · Data hyper-cleaning benchmarks | test accuracy (%): CodRNA: 80.42 ± 0.05 -> 80.56 ± 0.04; MNIST 6vs9: 94.24± 0.01 -> 94.35 ± 0.01; Madelon: 56.33 ± 1.83 -> 56.23 ± 1.56; Fa | Mixed |
| set η=0.1 instead of η=0.5 (ablation) | DMLCBO · Data hyper-cleaning benchmarks | test accuracy (%): CodRNA: 80.42 ± 0.05 -> 80.45 ± 0.04; MNIST 6vs9: 94.24± 0.01 -> 94.65 ± 0.01; Madelon: 56.33 ± 1.83 -> 56.23 ± 1.14; Fa | Mixed |
Surprising findings
- On Omniglot 5-way 5-shot, the Approx baseline (99.41%) and RMD-PCD (99.69%) are close to or above DMLCBO on some settings in the meta-learning table's neighbors, and DMLCBO is not best across all rows in ablations (e.g., Q=7 vs Q=5 differences are small).
Limitations
- Convergence guarantee is for (δ,ε)-stationarity rather than standard Clarke stationarity; the iteration complexity depends on d2 (dimension of lower-level variable).
- Experiments are limited to two applications with small-scale problems (data hyper-cleaning and meta-learning with SVM base learner).
- Hyperparameter choices (Q, eta, step sizes) require tuning; ablations show sensitivity.
Experimental setup
Datasets: MNIST FashionMNIST CodRNA Madelon Omniglot FC100
Benchmarks: data hyper-cleaning (CodRNA, MNIST 6vs9, Madelon, FashionMNIST 1vs7) meta-learning (Omniglot 5-way 5-shot, 10-way 5-shot, FC100 5-way 5-shot, 10-way 5-shot)
Metrics: test accuracy (%) test accuracy vs training time
Baselines: V-PBGD RMD-PCD Approx JaxOpt
Builds on: double-momentum method (MRBO/VRBO-style) adaptive step size (Adam-style) Goldstein subdifferential Jacobian chain rule for generalized gradients
Closest papers by meaning
- A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization (NeurIPS 2025 · similarity 0.92)
- Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis (ICLR 2025 · similarity 0.90)
- Generalized Smooth Bilevel Optimization with Nonconvex Lower-Level (ICML 2025 · similarity 0.90)
- A Single-Loop Gradient Algorithm for Pessimistic Bilevel Optimization via Smooth Approximation (NeurIPS 2025 · similarity 0.90)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.90)
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 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.