提出在高维乘积多面体上实现弗兰克-沃尔夫算法线性收敛的新条件。
Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes
- 基于组件多面体的条件数，定义乘积多面体的锥宽与顶点-面距离。
- 对满足μ-Polyak-Łojasiewicz条件的目标函数，给出线性收敛速率。
- 适用于高维多面体交集的可行解近似，实测效率优越。
研究弗兰克-沃尔夫算法在乘积多面体上的线性收敛性。基于各组件多面体的条件数，分析乘积多面体的两个条件数：锥宽与顶点-面距离。对于满足μ-Polyak-Łojasiewicz条件的凸目标函数，证明了以所得条件数为参数的线性收敛速率。将结果应用于高维多面体交集中近似求解可行点的问题，并通过实验验证了算法的实际效率。
原文摘要 · Abstract (English)
We study the linear convergence of Frank-Wolfe algorithms over product polytopes. We analyze two condition numbers for the product polytope, namely the \emph{pyramidal width} and the \emph{vertex-facet distance}, based on the condition numbers of individual polytope components. As a result, for convex objectives that are $μ$-Polyak-Łojasiewicz, we show linear convergence rates quantified in terms of the resulting condition numbers. We apply our results to the problem of approximately finding a feasible point in a polytope intersection in high-dimensions, and demonstrate the practical efficiency of our algorithms through empirical results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。