Revisiting the approximate Caratheodory problem via the Frank-Wolfe algorithm

• 成果类型: Article
• 署名作者: Combettes, Cyrille W.; Pokutta, Sebastian
• 署名单位: University System of Georgia; Georgia Institute of Technology; Technical University of Berlin; Zuse Institute Berlin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01735-x
• 发表日期: 2023
• 页码: 191-214
• 关键词: descent methods; minimization; CONVERGENCE; nonconvex

摘要

The approximate Caratheodory theorem states that given a compact convex set C subset of R-n and p is an element of[2,+infinity[, each point x*is an element of C can be approximated to epsilon-accuracy in the l(p)-norm as the convex combination of O(pD(p)(2)/epsilon(2)) vertices of C, where D-p is the diameter of C in the 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 Caratheodory 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* is in the interior of C, when x* is the convex combination of a subset of vertices with small diameter, or when C is uniformly convex. We also propose cardinality bounds when p is an element of[1,2[boolean OR{+infinity} via a nonsmooth variant of the algorithm. Lastly, we address the problem of finding sparse approximate projections onto C in the l(p)-norm, p is an element of[1,+infinity].