让稀疏优化更快：用稀疏更新实现更优收敛速度
First-Order Sparse Convex Optimization: Better Rates with Sparse Updates
- 设计仅需稀疏更新的一阶算法，提升高维问题效率
- 收敛速率依赖改进的混合范数条件数，与稀疏度相关
- 实现简单，适合大规模稀疏优化场景
近期研究表明，对于具有稀疏最优解（如逐元素稀疏或矩阵低秩）的凸优化问题，可设计一阶方法实现线性收敛率，其收敛速度依赖于改进的混合范数条件数 $\frac{β_1 s}{α_2}$，其中 $β_1$ 为梯度的 $\ell_1$-Lipschitz 常数，$α_2$ 为 $\ell_2$-二次增长常数，$s$ 为最优解稀疏度。然而，这些方法虽有更优收敛率，却无法利用最优解的稀疏性降低每步迭代时间，对高维问题仍可能过慢。本文证明，通过仅使用稀疏更新，即可获得依赖该改进条件数的线性收敛率，从而显著提升整体运行效率。此外，所提方法实现更为简便。
原文摘要 · Abstract (English)
It was recently established that for convex optimization problems with sparse optimal solutions (be it entry-wise sparsity or matrix rank-wise sparsity) it is possible to design first-order methods with linear convergence rates that depend on an improved mixed-norm condition number of the form $\frac{β_1{}s}{α_2}$, where $β_1$ is the $\ell_1$-Lipschitz continuity constant of the gradient, $α_2$ is the $\ell_2$-quadratic growth constant, and $s$ is the sparsity of optimal solutions. However, beyond the improved convergence rate, these methods are unable to leverage the sparsity of optimal solutions towards improving the runtime of each iteration as well, which may still be prohibitively high for high-dimensional problems. In this work, we establish that linear convergence rates which depend on this improved condition number can be obtained using only sparse updates, which may result in overall significantly improved running times. Moreover, our methods are considerably easier to implement.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。