An accelerated proximal algorithm for regularized nonconvex and nonsmooth bi-level optimization

From MaRDI portal
Publication:6161202

DOI10.1007/S10994-023-06329-6arXiv2203.16615OpenAlexW4362697005MaRDI QIDQ6161202FDOQ6161202


Authors: Ziyi Chen, Bhavya Kailkhura, Yi Zhou Edit this on Wikidata


Publication date: 27 June 2023

Published in: Machine Learning (Search for Journal in Brave)

Abstract: 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 mathcalO(kappa3.5epsilon2) 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.


Full work available at URL: https://arxiv.org/abs/2203.16615




Recommendations




Cites Work


Cited In (5)





This page was built for publication: An accelerated proximal algorithm for regularized nonconvex and nonsmooth bi-level optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161202)