Revisiting the Approximate Carath\'eodory Problem via the Frank-Wolfe Algorithm

DOI10.1007/S10107-021-01735-XMaRDI QIDQ6328955arXivFDO

Authors Cyrille W. Combettes, Sebastian Pokutta

Publication date 11 November 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/S10107-021-01735-X

Mathematics Subject Classification ID

Approximation algorithms (68W25) Convex programming (90C25)

arXiv classification

cs.DScs.LGmath.OC

Abstract: The approximate Carath'eodory theorem states that given a compact convex set $mathcalCsubsetmathbb{R}^n$ and $pinleft[2,+inftyight[$, each point $x^{\ast }inmathcalC$ can be approximated to $epsilon$-accuracy in the $el{l}_p$-norm as the convex combination of $mathcalO(p{D}_p^2/epsilo{n}^2)$ vertices of $mathcalC$, where $D_p$ is the diameter of $mathcalC$ in the $el{l}_p$-norm. A solution satisfying these properties can be built using probabilistic arguments or by applying mirror descent to the dual problem. We revisit the approximate Carath'eodory problem by solving the primal problem via the Frank-Wolfe algorithm, providing a simplified analysis and leading to an efficient practical method. Furthermore, improved cardinality bounds are derived naturally using existing convergence rates of the Frank-Wolfe algorithm in different scenarios, when $x^{\ast }$ is in the interior of $mathcalC$, when $x^{\ast }$ is the convex combination of a subset of vertices with small diameter, or when $mathcalC$ is uniformly convex. We also propose cardinality bounds when $pinleft[1,2ight[cup+infty$ via a nonsmooth variant of the algorithm. Lastly, we address the problem of finding sparse approximate projections onto $mathcalC$ in the $el{l}_p$-norm, $pinleft[1,+inftyight]$.

This page was built for publication: Revisiting the Approximate Carath\'eodory Problem via the Frank-Wolfe Algorithm

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