Convex Bi-level Optimization Problems with Nonsmooth Outer Objective Function
提出Bi-Sub-Gradient方法，将经典次梯度法推广到凸双层优化，仅需计算近端映射或外部非光滑目标函数的次梯度，在温和假设下内外目标函数均达到次线性速率，外部强凸时可提升为线性速率。
.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 nonsmooth 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 sublinear rates in terms of both the inner and outer objective functions. Moreover, if the outer objective function is additionally strongly convex (still could be nonsmooth), 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.Keywordsbi-level optimizationconvex problemsnonsmooth optimizationproximal mappingMSC codes65K1090C0590C2590C3090C52