Convex Bi-Level Optimization Problems with Non-smooth Outer Objective Function
This provides a first-order method for a specific class of optimization problems, representing an incremental advancement in optimization algorithms.
The authors tackled convex bi-level optimization problems with non-smooth outer objective functions by proposing the Bi-Sub-Gradient (Bi-SG) method, achieving sub-linear convergence rates for both inner and outer objectives under mild assumptions, with linear rates possible when the outer function is strongly convex.
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.