提出加速Frank-Wolfe算法，实现稀疏解的高效优化。
Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity
- 基于互补条件设计新算法，利用解的稀疏性提升效率。
- 对多面体问题，复杂度仅与解的稀疏度相关，不依赖维度。
- 适合大规模稀疏优化，尤其低秩矩阵问题，如推荐系统。
我们为在紧凸集上最小化光滑凸函数发展了新的加速一阶算法，聚焦两类典型约束：(1) 多面体和(2) 矩阵域（如谱半球和单位核范数球）。关键技术是刻画解稀疏性的互补条件——多面体对应面维数，矩阵对应秩。提出两种算法：(1) 仅需线性优化预言机（LOO）的纯方法，具有最优最坏情况一阶预言机复杂度，除去有限预热阶段并忽略对数因子后，其复杂度随 $r/\ oot{2}ε$ 变化，其中 $ε$ 为目标精度，$r$ 为解稀疏度（独立于环境维度）；(2) 混合方案结合FW与稀疏投影预言机（如低秩SVD），同样具有最优一阶复杂度，预热后仅需 $O(1/\ oot{2}ε)$ 次稀疏投影与LOO调用（独立于环境维度及最优解秩）。该工作填补了近期线性收敛FW算法加速在强凸优化中的空白，且无需付出维度代价。
原文摘要 · Abstract (English)
We develop new accelerated first-order algorithms in the Frank-Wolfe (FW) family for minimizing smooth convex functions over compact convex sets, with a focus on two prominent constraint classes: (1) polytopes and (2) matrix domains given by the spectrahedron and the unit nuclear-norm ball. A key technical ingredient is a complementarity condition that captures solution sparsity -- face dimension for polytopes and rank for matrices. We present two algorithms: (1) a purely linear optimization oracle (LOO) method for polytopes that has optimal worst-case first-order (FO) oracle complexity and, aside of a finite \emph{burn-in} phase and up to a logarithmic factor, has LOO complexity that scales with $r/\sqrtε$, where $ε$ is the target accuracy and $r$ is the solution sparsity $r$ (independently of the ambient dimension), and (2) a hybrid scheme that combines FW with a sparse projection oracle (e.g., low-rank SVDs for matrix domains with low-rank solutions), which also has optimal FO oracle complexity, and after a finite burn-in phase, only requires $O(1/\sqrtε)$ sparse projections and LOO calls (independently of both the ambient dimension and the rank of optimal solutions). Our results close a gap on how to accelerate recent advancements in linearly-converging FW algorithms for strongly convex optimization, without paying the price of the dimension.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。