Convex Bi-Level Optimization Problems with Non-smooth Outer Objective Function
Abstract
In this paper, we propose the Bi-Sub-Gradient (Bi-SG) method, which is a generalization of the classical sub-gradient method to the setting of convex bi-level optimization problems. This is a first-order method that is very easy to implement in the sense that it requires only a computation of the associated proximal mapping or a sub-gradient of the outer non-smooth objective function, in addition to a proximal gradient step on the inner optimization problem. We show, under very mild assumptions, that Bi-SG tackles bi-level optimization problems and achieves sub-linear rates both in terms of the inner and outer objective functions. Moreover, if the outer objective function is additionally strongly convex (still could be non-smooth), the outer rate can be improved to a linear rate. Last, we prove that the distance of the generated sequence to the set of optimal solutions of the bi-level problem converges to zero.
1 Introduction
Bi-level optimization problems consist, in a hierarchical sense, of two optimization problems referred to as inner and outer problems. This class of problems is a very active area of research with practical applications in many different areas (for instance, in the field of machine learning). For a recent comprehensive review of bi-level optimization problems and applications, see [DZ2020] and references therein. We also refer interested readers to the following recent papers [AY2019, F2021, SNK2022] that discuss various interesting applications, which fit to the setting of this paper.
In this paper, we are interested in a specific class of what is often called simple bi-level optimization problems. More precisely, following the terminology of inner and outer problems, we are interested in the following bi-level optimization problems. The