Hyper-Gradient Methods for Bilevel Optimization with Manifold Lower-level Solution Set

Minima Selection in Stochastic Optimization: A Long-Time, Small-Stepsize Perspective

Efficient Hessian-Free Methods for Multi-Objective Bilevel Optimization with Nonconvex Lower Level

This work proposes a class of Multi-Objective Moreau Envelope based Hessian-free Algorithms (MOMEHA) to solve the multi-objective bilevel learning problems with nonconvex lower level and proposes a momentum-based variant of MOMEHA (i.e., MB-MOMEHA) method to solve the stochastic multi-objective bilevel learning problems.

Convergence Analysis of Decentralized Hessian-/Jacobian-Free Algorithm for Nonconvex Stochastic Bi-Level Optimization

A Minimal-Gradient Subspace Method for Unconstrained Optimization

Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization

We study stochastic simple bilevel optimization with smooth, possibly nonconvex upper- and lower-level objectives accessed only through stochastic gradient oracles. A key challenge is that the dual multiplier induced by the lower-level constraint may become unbounded near lower-level stationary points, invalidating bounded-dual analyses and destabilizing stochastic gradient estimates. To address this, we propose \emph{Stochastic Dynamic Barrier Perturbed Gradient} (SDBPG), a single-loop method that adaptively perturbs the dual formulation to regularize this degeneracy. The perturbation stabilizes the multiplier and yields controlled bias and variance even near the lower-level stationarity region. Under a rare-visit assumption governed by a parameter $\delta \in (0, \tfrac{1}{2}]$, SDBPG finds an $(\epsilon, \epsilon)$-stationary point in $\mathcal{O}(\epsilon^{-1/\delta})$ iterations, with sample gradient complexities $\mathcal{O}(\epsilon^{-2/\delta})$ and $\mathcal{O}(\epsilon^{-3/\delta})$ for the upper- and lower-level objectives, where larger $\delta$ corresponds to rarer visits to the bad region describing the negative alignment between the two objectives when the lower-level gradient is small. We further develop PR-SDBPG, a penalty-regularized variant that eliminates the rare-visit assumption, and VR-PR-SDBPG, which improves the resulting sample complexities entirely through variance reduction. To our knowledge, these are the first explicit $(\epsilon_f,\epsilon_g)$-stationarity guarantees for stochastic nonconvex-nonconvex simple bilevel optimization.

First-Order Methods for Distributionally Robust Constrained Optimization

We consider constrained optimization problems in which input data are affected by estimation errors. In such settings, Wasserstein distributionally robust optimization provides a principled framework to mitigate model risk by optimizing against worst-case distributions within Wasserstein ambiguity sets. However, the numerical resolution of the resulting problems remains challenging, especially in constrained and combinatorial settings. In this paper, we propose a tractable stochastic approach based on two key ingredients: (i) an entropic regularization of the distributionally robust value function, which makes it possible to compute stochastic gradient estimators, and (ii) the combination of these estimators with a stochastic Frank-Wolfe algorithm, allowing us to optimize the regularized robust objective while naturally handling constraints. We illustrate the method, and its interests against empirical risk minimization, on two classical optimization problems, the minimum quadratic spanning tree and the traffic assignment problems. Our approach provides a general, practical way to address Wasserstein distributionally robust formulations in the presence of constraints.