On a Frank-Wolfe Approach for Abs-smooth Functions

Submission Status:under review
  • We propose an algorithm which appears to be the first bridge between the fields of conditional gradient methods and abs-smooth optimization. Our nonsmooth nonconvex problem setting is motivated by machine learning, since the broad class of abs-smooth functions includes, for instance, the squared $\ell_2$-error of a neural network with ReLU or hinge Loss activation. To overcome the nonsmoothness in our problem, we propose a generalization to the traditional Frank-Wolfe gap and prove that first-order minimality is achieved when it vanishes. We derive a convergence rate for our algorithm which is identical to the smooth case. Although our algorithm necessitates the solution of a subproblem which is more challenging than the smooth case, we provide an efficient numerical method for its partial solution, and we identify several applications where our approach fully solves the subproblem. Numerical and theoretical convergence is demonstrated, yielding several conjectures.
Metadaten
Author:Timo Kreimeier, Sebastian Pokutta, Andrea Walther, Zev Woodstock
Document Type:Preprint
Language:English
Date of Publication (online):2022/09/02
Release Date:2022/09/03
Tag:Active Signature Method; Frank-Wolfe algorithm; abs-smooth functions; convergence rate; nonsmooth optimization
Institutes:Humboldt-Universität zu Berlin
Zuse-Institut Berlin (ZIB)
Technische Universität Berlin
Subprojects:A05
B10
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International