我们提出了一种算法，可以计算矩阵 $A \in \mathbb{R}^{m \times n}$ 的 $\ell_p$-Lewis 权重的 $\epsilon$-估计值，适用于 $p \geq 4$，其计算复杂度为 $O(p^2 \log(m/\epsilon))$ 轮杠杆分数计算。这一结果优于 Fazel 等人（2022）提出的 $O(p^3 \log(m/\epsilon))$ 的轮复杂性。我们的成果来源于对 $\ell_p$-Lewis 权重优化问题的原始和对偶形式巧妙地应用相对平滑梯度下降的局部变体，并提供了在不同近似 $\ell_p$-Lewis 权重概念之间转换的工具。
博主点评： 本文提出的算法通过降低计算复杂度，极大地提高了计算 Lewis 权重的效率，适用于更高维度的矩阵。相对平滑梯度下降的应用展示了优化算法在实际问题中的强大潜力。