mlsanityData to 7 Oct 2026

A Fast and Convergent Proximal Algorithm for Regularized Nonconvex and Nonsmooth Bi-level Optimization

arXiv 2203.16615 ↗First posted 30 Mar 2022cs.LG math.OCcited by 7

Not on the map. Why?

Abstract (arXiv)

Many important machine learning applications involve regularized nonconvex bi-level optimization. However, the existing gradient-based bi-level optimization algorithms cannot handle nonconvex or nonsmooth regularizers, and they suffer from a high computation complexity in nonconvex bi-level optimization. In this work, we study a proximal gradient-type algorithm that adopts the approximate implicit differentiation (AID) scheme for nonconvex bi-level optimization with possibly nonconvex and nonsmooth regularizers. In particular, the algorithm applies the Nesterov's momentum to accelerate the computation of the implicit gradient involved in AID. We provide a comprehensive analysis of the global convergence properties of this algorithm through identifying its intrinsic potential function. In particular, we formally establish the convergence of the model parameters to a critical point of the bi-level problem, and obtain an improved computation complexity O(kappa3.5ε-2) over the state-of-the-art result. Moreover, we analyze the asymptotic convergence rates of this algorithm under a class of local nonconvex geometries characterized by a Lojasiewicz-type gradient inequality. Experiment on hyper-parameter optimization demonstrates the effectiveness of our algorithm.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 37 of its 62 references that are in the map. First posted on arXiv 30 Mar 2022.

Builds on

37 of 62 references.

References · 37

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  2. 2017Prototypical Networks for Few-shot Learningcited by 3,001
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  5. 2019Meta-Learning with Implicit Gradientscited by 523
  6. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  7. 2018Meta-learning with differentiable closed-form solverscited by 395
  8. 2019Rapid Learning or Feature Reuse? Towards Understanding the Effectiveness of MAMLcited by 359
  9. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 357
  10. 2019Optimizing Millions of Hyperparameters by Implicit Differentiationcited by 303
  11. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  12. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
25 more
  1. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 232
  2. 2016Hyperparameter optimization with approximate gradientcited by 231
  3. 2018Approximation Methods for Bilevel Programmingcited by 231
  4. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 219
  5. 2018Truncated Back-propagation for Bilevel Optimizationcited by 187
  6. 2020On the Iteration Complexity of Hypergradient Computationcited by 154
  7. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
  8. 2019On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithmscited by 132
  9. 2016On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimizationcited by 108
  10. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  11. 2020A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singletoncited by 78
  12. 2018Reviving and Improving Recurrent Back-Propagationcited by 69
  13. 2020Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameterscited by 65
  14. 2021Lower Bounds and Accelerated Algorithms for Bilevel Optimizationcited by 46
  15. 2020Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learningcited by 28
  16. 2021Enhanced Bilevel Optimization via Bregman Distancecited by 28
  17. 2020Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guaranteecited by 27
  18. 2014Splitting methods with variable metric for KL functionscited by 26
  19. 2017Convergence Analysis of Proximal Gradient with Momentum for Nonconvex Optimizationcited by 18
  20. 2021Proximal Gradient Descent-Ascent: Variable Convergence under KL Geometrycited by 17
  21. 2020How Robust are Randomized Smoothing based Defenses to Data Poisoning?cited by 15
  22. 2017Distributed Proximal Gradient Algorithm for Partially Asynchronous Computer Clusterscited by 10
  23. 2018Convergence of Cubic Regularization for Nonconvex Optimization under KL Propertycited by 8
  24. 2021Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysiscited by 5
  25. 2020Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart for Nonconvex Optimizationcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 1; 2024: 3; 2025: 1; 2026: 1.

7 papers.

  1. 2024Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithmcited by 16
  2. 2024Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategycited by 15
  3. 2022Alternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimizationcited by 10
  4. 2024A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraintscited by 7
  5. 2023Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimizationcited by 6
  6. 2025Bilevel ZOFO: Efficient LLM Fine-Tuning and Meta-Trainingcited by 5
  7. 2026Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problemscited by 1