Abstract. Simple bi-level problems are optimization problems in which we seek an optimal solution to an inner problem that minimizes an outer objective function. Such problems appear in many machine learning and signal processing applications as a way to eliminate undesirable solutions. However, since these problems do not satisfy regularity conditions, they are often hard to solve exactly and are usually solved via iterative regularization. Several algorithms were proposed to solve these bi-level problems directly assuming that the outer function is either smooth or strongly convex, and in some cases these methods also provide a rate for obtaining feasibility. In our work, we suggest a new approach that is designed for bi-level problems with simple outer functions, such as the ℓ1 norm, which are not required to be either smooth or strongly convex. In our new Iterative Approximation and Level-set Expansion (ITALEX) approach, we alternate between expanding the level-set of the outer function and approximately optimizing the inner function over this level-set. ITALEX uses standard first-order methods to optimize the inner function resulting in a feasibility convergence rate of o(1/√k), which is a rate only shown to be obtained for strongly convex outer functions. Moreover, contrary to existing work that only guarantees asymptotic optimality, ITALEX also provides a o(1/√k) rate of convergence on the optimality of the outer function. We demonstrate the versality of ITALEX through numerical experiments.

This talk is based on Joint work with Lior Doron.