Skip to content
Preprint

A Proximal Newton Framework with Local Superlinear Convergence for Simple Bilevel Optimization

Nov 2026 · 0 citations · 48 references
Mathematics

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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.