arXiv Machine Learning

To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity

arXiv:2609. 30501v1 Announce Type: new Abstract: Although bilevel optimization (BLO) has emerged as a powerful framework for addressing many complex and nested machine learning problems in recent years, most existing studies are confined to the lower-level strongly convex (LLSC) or lower-level generally convex (LLGC) settings (i.

arXiv Machine Learning
1d ago

Simultaneous Learning and Optimization via Misspecified Saddle Point Problems

The paper introduces a framework for misspecified saddle point problems where the objective depends on an unknown parameter that must be learned simultaneously from data. Two accelerated primal-dual algorithms are proposed: a naive extension that substitutes evolving parameter estimates, and a learning‑aware variant that adjusts momentum updates to account for parameter dynamics. Both achieve an ≥O(log K/K) convergence rate, with the learning‑aware method offering a tighter constant and adaptive step‑size, and an extended version handles multiple optimal solutions with an O(1/√K) rate, demonstrated on a portfolio optimization task.

By Mohammad Mahdi Ahmadi, Erfan Yazdandoost Hamedani
arXiv Machine Learning
Oct 3

Optimal Stochastic Bilevel Optimization with First-Order Oracles

The paper investigates nonconvex–strongly-convex bilevel optimization using a stochastic first-order oracle. It introduces MRT‑FD, a single-loop first‑order algorithm that tracks the upper-level variable, the lower-level solution, and an auxiliary response from implicit differentiation, updating all variables in each iteration and approximating second‑order derivative actions via order‑p finite differences. For any fixed finite smoothness order p ≥ 1, MRT‑FD achieves an ε‑stationary point with O(ε^{‑4‑2/p}) stochastic gradient queries, and the authors prove a matching Ω(ε^{‑4‑2/p}) lower bound, thereby closing the complexity gap in this setting.

By Linxuan Pan, Junchi Yang
arXiv Machine Learning
Nov 5

Bilevel Learning via Strategically Inexact Stochastic Gradient Descent

arXiv:2511. 06774v2 Announce Type: replace-cross Abstract: Bilevel optimization is a central tool in computational imaging for high-dimensional hyperparameter tuning; prominent applications include learning data-adaptive regularizers and optimizing forward operators in variational regularization.

By Mohammad Sadegh Salehi, Subhadip Mukherjee, Lindon Roberts, Matthias J. Ehrhardt