随机子空间方法让二阶优化更快更省，尤其适合低秩函数。
Random Subspace Cubic-Regularization Methods, with Applications to Low-Rank Functions
- 在随机子空间内做局部模型优化，只用投影梯度与海森矩阵。
- 收敛速度达到最优，且在低秩函数上计算量显著降低。
- 自适应调整子空间大小，无需预先知道函数真实秩。
我们提出并分析了二阶自适应立方正则化（ARC）算法的随机子空间变体。这些方法在迭代中将搜索空间限制在参数的某个随机子空间内，仅在该子空间内构建并最小化局部模型。因此，所提方法只需访问一阶和二阶导数的小维投影，并以低成本计算缩减步长。在适当假设下，其保持了全维立方正则化方法的最优一阶与二阶全局收敛速率，同时在理论和数值上均展现出更好的可扩展性，特别是在处理低秩函数时。应用于低秩函数时，我们的自适应变体能自动根据函数真实秩调整子空间大小，而无需事先知晓该秩。
原文摘要 · Abstract (English)
We propose and analyze random subspace variants of the second-order Adaptive Regularization using Cubics (ARC) algorithm. These methods iteratively restrict the search space to some random subspace of the parameters, constructing and minimizing a local model only within this subspace. Thus, our variants only require access to (small-dimensional) projections of first- and second-order problem derivatives and calculate a reduced step inexpensively. Under suitable assumptions, the ensuing methods maintain the optimal first-order, and second-order, global rates of convergence of (full-dimensional) cubic regularization, while showing improved scalability both theoretically and numerically, particularly when applied to low-rank functions. When applied to the latter, our adaptive variant naturally adapts the subspace size to the true rank of the function, without knowing it a priori.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。