2024/02/08 by Jiulin Wang, Xu Shi, Wang, Jiulin +3 · 2 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.2402.05415
openalex publication_date 2024/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies a class of simple bilevel optimization problems where we minimize a composite convex function at the upper-level subject to a composite convex lower-level problem. Existing methods either provide asymptotic guarantees for the upper-level objective or attain slow sublinear convergence rates. We propose a bisection algorithm to find a solution that is εf-optimal for the upper-level objective and εg-optimal for the lower-level objective. In each iteration, the binary search narrows the interval by assessing inequality system feasibility. Under mild conditions, the total operation complexity of our method is O(max\√Lf1/εf,√Lg1/εg \ ). Here, a unit operation can be a function evaluation, gradient evaluation, or the invocation of the proximal mapping, Lf1 and Lg1 are the Lipschitz constants of the upper- and lower-level objectives' smooth components, and O hides logarithmic terms. Our approach achieves a near-optimal rate, matching the optimal rate in unconstrained smooth or composite convex optimization when disregarding logarithmic terms. Numerical experiments demonstrate the effectiveness of our method.