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.

本文提出了一种一阶 Bi-Sub-Gradient 方法，它被广泛应用于凸性双层优化问题中，具有易于实现、内外两个目标函数均能取得亚线性收敛速度等特点，并且证明了所生成的序列与双层问题最优解的距离趋于零。