A Barrier-Metric First-Order Method for Linearly Constrained Bilevel Optimization

Authors: Tenglong Hong, Paul Grigas

arXiv · PDF

Summary

The authors tackle bilevel optimization problems where the lower-level problem has fixed polyhedral constraints (think optimizing over a polyhedron). The core trick is to smooth the constraints using a logarithmic barrier, turning a non-smooth optimization into a smoother one, then run a gradient-based method that only needs first-order information (no expensive second-order matrix inversions). They develop convergence guarantees using a "barrier-aware" geometry that adapts to how close iterates get to constraint boundaries.

Main takeaways:

• Barrier smoothing makes constrained bilevel problems differentiable, avoiding expensive Hessian inversions or linear solves that standard methods require.
• The algorithm uses only gradients of the upper and lower objectives, plus the explicit barrier Hessian from the fixed constraints.
• They prove convergence rates of roughly K^(-2/3) in the deterministic case and K^(-2/5) with stochastic noise after K iterations.
• The "Dikin geometry" adapts the step-size schedule to keep iterates in well-behaved regions near constraint boundaries.
• Barrier parameter can be decreased with quantitative control on the approximation error.

Relevance

Not directly related to my persona/midtraining work — this is a constrained optimization paper for bilevel problems, which doesn't connect to prompt-based behavioral installation or fine-tuning dynamics in language models.

Threat model

Potential threat/caveat for clean result "Fine-tuning one persona on a two-marker chunk and another on the start marker plants the end marker at every donor answer's end, not chained to the start (LOW confidence)": this item discusses bias.

Abstract

arXiv:2605.11476v1 Announce Type: cross Abstract: We study bilevel optimization with a fixed polyhedral lower feasible set. Such problems are challenging for two reasons: active-set changes can make the upper objective nonsmooth, and existing hypergradient methods typically require lower-Hessian inversions or equivalent linear solves, which are computationally expensive. To address these issues, we adopt a logarithmic barrier smoothing of the lower problem to obtain a differentiable approximation of the constrained bilevel objective, and develop a proxy-gradient algorithm for the resulting barrier-smoothed surrogate. The algorithm uses only gradients of the upper and lower objectives; its only second-order object is the explicit logarithmic barrier Hessian determined by the fixed polyhedral constraints. Barrier smoothing restores differentiability, but Euclidean smoothness constants are not uniformly bounded near the boundary. We therefore develop a local Dikin-geometry analysis in which the barrier-metric provides an oracle-free curvature scale near the moving lower centers. This leads to barrier-aware schedules that keep the iterates inside locally well-behaved regions. For the barrier-smoothed objective, we prove stationarity rates of $\widetilde{O}(K^{-2/3})$ in the deterministic setting and $\widetilde{O}(K^{-2/5})$ under upper-level-only bounded stochastic noise after $K$ outer iterations, together with quantitative bias control as the barrier parameter decreases.