Lezhi ZHANG, an undergraduate student of the 2021 class in the Department of Mathematics at Southern University of Science and Technology (SUSTech), together with his advisor Jin ZHANG and collaborators, made significant research progress in the field of bilevel optimization algorithms. The related results were published in the top international journal in mathematical optimization, SIAM Journal on Optimization, under the title “Alternating Gradient-Type Algorithm for Bilevel Optimization with Inexact Lower-Level Solutions via Moreau Envelope-based Reformulation.”

Bilevel optimization problems have received increasing attention in machine learning research. Among them, the value function-based reformulation approach has gained wide attention because it can effectively avoid the computation of second-order information at the lower level. Existing algorithms mostly adopt a double-loop structure, which often brings a high computational burden. To reduce the cost introduced by the exact solution of the lower-level problem, current research often relies on strong structural assumptions to ensure that the approximation error is controllable. However, in large-scale and complex application tasks, how to establish effective theoretical metrics and control the inexactness of lower-level solutions remains a key issue that urgently needs to be addressed in this field.

This challenge has attracted the interest of several prestigious scholars, including Professor Stephen Wright, a Dantzig Prize winner, member of the US National Academy of Engineering, and one-hour plenary speaker at the International Congress of Mathematicians. In a paper published at ICML 2024, Professor Wright and his co-authors highlighted that developing algorithms to address lower-level inexactness is an open research direction in current bilevel optimization research.

To address these challenges, the mathematical optimization research team at SUSTech has proposed a novel algorithm utilizing a Moreau envelope value function reformulation. By introducing strongly convex subproblems related to auxiliary variables into the algorithm, they successfully transformed the lower-level approximation errors, which were originally difficult to control directly, into computable and verifiable error terms. This systematically constructed a new algorithm design and theoretical analysis framework aimed at inexact lower-level solutions. The research, for the first time, theoretically achieved the quantification and controllable propagation of lower-level approximation errors, providing new ideas and methodological support for the efficient application of bilevel optimization in large-scale machine learning, particularly for solving hyperparameter learning problems.

The SIAM Journal on Optimization is a high-quality and highly reputable journal published by the Society for Industrial and Applied Mathematics (SIAM) in the United States, recognized as a top international journal in the field of mathematical optimization.

The paper is co-authored by PhD student Xiaoning BAI from Professor Jin ZHANG’s research group, Associate Professor Shangzhi ZENG from National Center for Applied Mathematics Shenzhen, Jin ZHANG, and Lezhi ZHANG, with Jin ZHANG as the corresponding author. SUSTech is the first affiliation listed for the paper.

Article Link: https://doi.org/10.1137/24M1721049