2025/11/13 by C.S. Phan, Kai Wang, Phan, Cac +1
Computer Science · Decision Sciences · #Bilevel optimization #Bridging (networking) #Convergence (economics) #FOS: Computer and information sciences #FOS: Mathematics #Hessian matrix #Linear programming #Machine Learning (stat.ML) #Methodology (stat.ME) #Optimization and Control (math.OC) #Optimization and Variational Analysis #Optimization problem #Risk and Portfolio Optimization #Stochastic Gradient Optimization Techniques #Stochastic approximation #Stochastic optimization #Stochastic programming
paper · pdf · doi:10.48550/arxiv.2511.09845
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2025/11/13 · openalex created_date 2025/11/15 · openalex updated_date 2026/07/28
This work provides the first finite-time convergence guarantees for linearly constrained stochastic bilevel optimization using only first-order methods, requiring solely gradient information without any Hessian computations or second-order derivatives. We address the unprecedented challenge of simultaneously handling linear constraints, stochastic noise, and finite-time analysis in bilevel optimization, a combination that has remained theoretically intractable until now. While existing approaches either require second-order information, handle only unconstrained stochastic problems, or provide merely asymptotic convergence results, our method achieves finite-time guarantees using gradient-based techniques alone. We develop a novel framework that constructs hypergradient approximations via smoothed penalty functions, using approximate primal and dual solutions to overcome the fundamental challenges posed by the interaction between linear constraints and stochastic noise. Our theoretical analysis provides explicit finite-time bounds on the bias and variance of the hypergradient estimator, demonstrating how approximation errors interact with stochastic perturbations. We prove that our first-order algorithm converges to (δ, ε)-Goldstein stationary points using Θ(δ-1ε-5) stochastic gradient evaluations, establishing the first finite-time complexity result for this challenging problem class and representing a significant theoretical breakthrough in constrained stochastic bilevel optimization.