2025-11-11T21:07:14.953280

Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation

Qiao, Maros

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.

academic

Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation

基本信息

论文ID: 2509.09802
标题: Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation
作者: Tianqi Qiao (Texas A&M University), Marie Maros (Texas A&M University)
分类: math.OC cs.LG stat.ML
发表时间/会议: 39th Conference on Neural Information Processing Systems (NeurIPS 2025)
论文链接: https://arxiv.org/abs/2509.09802

摘要

本文提出并研究了Sparse Polyak，这是Polyak自适应步长的一个变体，专门设计用于解决高维统计估计问题，其中问题维度增长远快于样本大小。在这种设置下，标准的Polyak步长表现不佳，需要越来越多的迭代来达到最优统计精度——即使问题保持良好条件和/或可达到的精度本身不随问题规模退化。本文将这一局限性归因于平滑度测量方式的不匹配：在高维中，估计Lipschitz平滑常数不再有效。相反，更适合估计限制在问题相关特定方向上的平滑度（限制Lipschitz平滑常数）。Sparse Polyak通过修改步长来估计限制Lipschitz平滑常数来克服这个问题。

研究背景与动机

问题定义

本文研究高维统计估计问题：

min_{θ∈R^d: ||θ||_0≤s} f(θ) = (1/n) Σ_{i=1}^n ℓ(z_i, θ)

其中维度d相对于样本大小n增长很快，即d/n → ∞。

核心问题

高维挑战：在高维设置下，传统的Lipschitz平滑常数估计失效，导致步长选择过于保守
性能退化：标准Polyak步长随问题维度增加而性能显著下降，即使问题条件数保持不变
速率不变性缺失：现有方法无法保持与固定步长IHT相同的收敛保证

研究动机

迭代硬阈值(IHT)算法在高维稀疏恢复中表现优异，但需要知道限制Lipschitz平滑(RSS)常数L̄
现有自适应步长方法在高维设置下缺乏理论保证和实际性能
需要一种既能自适应调整步长又能保持速率不变性的方法

核心贡献

首个高维自适应步长规则：提出了第一个在高维设置下表现良好并保持速率不变性的自适应步长规则
理论创新：识别出高维中平滑度测量的根本问题，提出估计限制Lipschitz平滑常数而非全局常数
收敛性保证：建立了与已知最优固定步长相当的线性收敛速率，达到最优统计精度
广泛适用性：为多种统计模型（逻辑回归、线性回归、矩阵回归等）提供了理论保证
支持恢复：在信噪比条件下提供支持恢复保证

方法详解

任务定义

考虑约束优化问题：

min_{θ∈R^d: ||θ||_0≤s} f(θ) = (1/n) Σ_{i=1}^n ℓ(z_i, θ)

其中：

θ是d维参数向量，约束为最多s个非零元素
f(θ)是经验风险函数
目标是在高维设置(d/n → ∞)下高效求解

核心算法：Sparse Polyak步长

Algorithm 1: IHT with Sparse Polyak Step-Size

输入：函数f，目标函数值f̂，稀疏参数s，迭代次数T
初始化：θ_0 ∈ R^d，||θ_0||_0 ≤ s
for t = 0 to T-1 do:
    计算步长：γ_t = max{f(θ_t) - f̂, 0} / (5||HT_s(∇f(θ_t))||²)
    更新：θ_{t+1} = HT_s(θ_t - γ_t∇f(θ_t))
end for

关键创新点

修改的步长公式：
- 传统Polyak：γ_t = (f(θ_t) - f̂) / ||∇f(θ_t)||²
- Sparse Polyak：γ_t = (f(θ_t) - f̂) / ||HT_s(∇f(θ_t))||²
硬阈值算子：HT_s保留s个最大幅度分量，其余设为零
理论基础：
- 利用限制强凸性(RSC)和限制平滑性(RSS)条件
- L̄ = L + 3τs，μ̄ = μ - 3τs，κ̄ = L̄/μ̄

技术创新点

维度无关的步长：通过使用||HT_s(∇f(θ_t))||²而非||∇f(θ_t)||²，避免了与维度d相关的缩放
限制方向估计：专注于稀疏方向上的平滑性，而非全空间
双循环算法：提供Algorithm 2处理未知目标值的情况

理论分析

主要定理

Theorem 1（主要收敛结果）：在RSC和RSS假设下，当s ≥ (240κ̄)²s*时：

线性收敛：||θ_{t+1} - θ̂||² ≤ (1 - 1/(80κ̄))||θ_t - θ̂||²
最终精度：O(||HT_s(∇f(θ̂))||²/μ̄²)

Corollary 1（支持恢复）：在信噪比条件|θ̂|_min ≥ 7||HT_s(∇f(θ̂))||/μ̄下，算法能准确恢复支持集。

统计模型保证

稀疏逻辑回归（Corollary 2）：

收敛速率：(1 - 1/(80κ̄))
统计精度：O(s log d / n)
概率保证：至少1 - e^{-c_0 n} - 2/d

矩阵回归（Corollary 3）：

适用于低秩矩阵恢复
类似的收敛保证和统计精度

实验设置

合成数据实验

维度设置：d ∈ {5000, 10000, 20000}
稀疏度：s* = 300
样本大小：n = ⌈α s log d⌉，α = 5
设计矩阵：时间序列结构，相关性参数ω = 0.5
噪声设置：线性回归σ² = 0.25，逻辑回归按模型(4)生成

真实数据实验

线性回归：Large-scale Wave Energy Farm数据集(120样本，149特征)
逻辑回归：Molecule Musk数据集(120样本，166特征)
稀疏度：s = 20

对比方法

IHT with固定步长γ = 2/(3L̄)
经典Polyak步长
网格搜索优化的固定步长

实验结果

主要结果

速率不变性验证：
- Sparse Polyak在不同维度d下保持一致的收敛行为
- 经典Polyak随维度增加性能显著退化
- 当log(d)/n保持常数时，迭代次数基本不变
收敛速度比较：
- 相比固定步长，Sparse Polyak通常收敛更快
- 在逻辑回归中优势更明显（由于局部曲率适应）
- 目标值f̂的选择直接影响可达精度
真实数据性能：
- 逻辑回归任务：Sparse Polyak > 固定步长 > 经典Polyak
- 线性回归任务：最优固定步长略优，但Sparse Polyak仍优于经典Polyak