高维统计估计中，自适应步长算法更高效
Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation
- 基于受限光滑性设计新步长规则
- 在高维下迭代次数显著减少
- 适合高维稀疏统计估计问题
我们提出并研究了Sparse Polyak，一种Polyak自适应步长的变体，用于解决维度远超样本量的高维统计估计问题。在此类场景中，标准Polyak步长表现不佳，即使问题条件良好且精度不随维度增长而下降，仍需越来越多的迭代才能达到最优统计精度。我们发现这一局限源于光滑性度量的不匹配：在高维情况下，估计Lipschitz光滑常数不再有效。相反，应估计与问题相关方向上的受限光滑性常数（restricted Lipschitz smoothness constant）。Sparse Polyak通过修改步长以估计该受限常数，克服了这一问题。理论分析和数值实验均验证了其性能提升。
原文摘要 · Abstract (English)
We propose and study Sparse Polyak, a variant of Polyak's adaptive step size, designed to solve high-dimensional statistical estimation problems where the problem dimension is allowed to grow much faster than the sample size. In such settings, the standard Polyak step size performs poorly, requiring an increasing number of iterations to achieve optimal statistical precision-even when, the problem remains well conditioned and/or the achievable precision itself does not degrade with problem size. We trace this limitation to a mismatch in how smoothness is measured: in high dimensions, it is no longer effective to estimate the Lipschitz smoothness constant. Instead, it is more appropriate to estimate the smoothness restricted to specific directions relevant to the problem (restricted Lipschitz smoothness constant). Sparse Polyak overcomes this issue by modifying the step size to estimate the restricted Lipschitz smoothness constant. We support our approach with both theoretical analysis and numerical experiments, demonstrating its improved performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。