A Proximal Newton Framework with Local Superlinear Convergence for Simple Bilevel Optimization
Abstract
In this paper, we study a penalty method for simple bilevel optimization in which the lower-level objective has a convex composite structure. Our approach is based on a vanishing-penalty reformulation, which gives rise to a sequence of penalized problems as the penalty parameter decreases. A key difficulty is that metric subregularity of the lower-level optimality mapping does not, in general, yield a uniform error bound for the penalized problems as the penalty parameter vanishes, preventing a direct application of standard proximal Newton theory. To address this difficulty, we first analyze a regularized proximal Newton step by exploiting the specific structure of simple bilevel problems, and establish the local estimates that underpin superlinear convergence. Building on this local analysis, we propose SiB-Newton, which incorporates the proximal Newton step into a globalization strategy. We establish convergence guarantees for SiB-Newton and show that, under suitable local conditions, Newton steps are eventually accepted and the iterates converge at a superlinear rate. Numerical experiments on synthetic examples verify the predicted local superlinear convergence rate.
Related
- Linear convergence rate analysis of Proximal-Tracking for nonsmooth distributed optimization
- A Sharper Theory of Ball-Proximal Optimization: Convergence and Radius Selection
- The Convergence Rate of Accelerated Proximal Gradient Methods with General Inertia Term for Convex Composite Multiobjective Optimization
- Counterexamples to R-superlinear convergence of cyclic steepest descent
- Superlinear Convergence of Cyclic Gradient Methods with Historical Ritz Step Sizes
BibTeX
@misc{bai2026proximal,
title = {{A Proximal Newton Framework with Local Superlinear Convergence for Simple Bilevel Optimization}},
author = {Xiaoning Bai and Boris S. Mordukhovich and Shangzhi Zeng and Jin Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.08297},
eprint = {2611.08297},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.08297},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Proximal Newton Framework with Local Superlinear Convergence for Simple Bilevel Optimization
AU - Xiaoning Bai
AU - Boris S. Mordukhovich
AU - Shangzhi Zeng
AU - Jin Zhang
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.08297
UR - https://arxiv.org/abs/2611.08297
AB - In this paper, we study a penalty method for simple bilevel optimization in which the lower-level objective has a convex composite structure. Our approach is based on a vanishing-penalty reformulation, which gives rise to a sequence of penalized problems as the penalty parameter decreases. A key difficulty is that metric subregularity of the lower-level optimality mapping does not, in general, yield a uniform error bound for the penalized problems as the penalty parameter vanishes, preventing a direct application of standard proximal Newton theory. To address this difficulty, we first analyze a regularized proximal Newton step by exploiting the specific structure of simple bilevel problems, and establish the local estimates that underpin superlinear convergence. Building on this local analysis, we propose SiB-Newton, which incorporates the proximal Newton step into a globalization strategy. We establish convergence guarantees for SiB-Newton and show that, under suitable local conditions, Newton steps are eventually accepted and the iterates converge at a superlinear rate. Numerical experiments on synthetic examples verify the predicted local superlinear convergence rate.
ER -