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.