Kavli Affiliate: Yi Zhou
| First 5 Authors: Ziyi Chen, Bhavya Kailkhura, Yi Zhou, ,
| Summary:
Many important machine learning applications involve regularized nonconvex
bi-level optimization. However, the existing gradient-based bi-level
optimization algorithms cannot handle nonconvex or nonsmooth regularizers, and
they suffer from a high computation complexity in nonconvex bi-level
optimization. In this work, we study a proximal gradient-type algorithm that
adopts the approximate implicit differentiation (AID) scheme for nonconvex
bi-level optimization with possibly nonconvex and nonsmooth regularizers. In
particular, the algorithm applies the Nesterov’s momentum to accelerate the
computation of the implicit gradient involved in AID. We provide a
comprehensive analysis of the global convergence properties of this algorithm
through identifying its intrinsic potential function. In particular, we
formally establish the convergence of the model parameters to a critical point
of the bi-level problem, and obtain an improved computation complexity
$mathcal{O}(kappa^{3.5}epsilon^{-2})$ over the state-of-the-art result.
Moreover, we analyze the asymptotic convergence rates of this algorithm under a
class of local nonconvex geometries characterized by a {L}ojasiewicz-type
gradient inequality. Experiment on hyper-parameter optimization demonstrates
the effectiveness of our algorithm.
| Search Query: ArXiv Query: search_query=au:”Yi Zhou”&id_list=&start=0&max_results=10