🔥 今日值得一读
逐坐标精度翻倍！新算法破解随机草图回归难题，近线性速度碾压旧方法
Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee
👨💼 主理人解读 · 为什么值得关注
用于大规模回归问题，通过草图技术降低计算复杂度，同时确保解向量的坐标级准确性，适合高维数据场景。
📖 AI 总结
本文研究超定最小二乘回归（ℓ₂回归）的随机草图化加速算法，重点解决解向量的坐标级精度保证问题。标准子空间嵌入方法仅能保持回归代价近似，而本文目标是在ℓ∞范数下保证解向量接近最优解。此前Price等人提出的SRHT方法需要O(ε⁻²d^(1+Θ(√(loglogn/logd))))行，Song等人声称改进至O(ε⁻²dlog³n)行，但其证明依赖不成立的独立性假设，本文给出了反例。为此，作者提出一种新的快速稠密随机变换，结合Hadamard展平、随机置换和平衡不相交高斯池化，在Hadamard与置换阶段后，草图化问题成为精确高斯回归，噪声与整个草图设计独立，弥补了先前论证的缺陷。该方法仅需m=O(ε⁻²dlogd)行，内部维度N=Õ(n+ε⁻²d³)，计算复杂度为Õ(nd+ε⁻²d⁴)，实现了接近线性于d的行数目标，为大规模回归问题提供了更高效的坐标级精度保证方案。
🔑 关键词速览
| Hadamard Flattening | 一种利用 Hadamard 变换将矩阵展平以改善其几何性质的随机化技术。 |
| Gaussian Pooling | 一种通过将多个高斯随机投影组合成池化块来构造草图矩阵的方法，旨在平衡误差和计算效率。 |
| Subsampled Randomized Hadamard Transform (SRHT) | 一种经典的随机投影方法，通过对 Hadamard 变换后的矩阵进行行采样来降低维度。 |
| Coordinate-wise Guarantee | 指对解向量的每个坐标提供误差保证，通常以 $\ell_\infty$ 范数衡量。 |
| Sketch-and-Solve | 一种通过随机草图压缩原问题，然后在小规模问题上求解以加速计算的算法框架。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅