提出分客户端框架,让二阶优化更快更省时。
A Split-Client Approach to Second-Order Optimization
- 将梯度与曲率计算并行处理,自动适应延迟。
- 实测比传统方法快800倍,且无需调参。
- 适合大规模机器学习训练中的高效优化。
二阶优化方法虽收敛速度快,但常受海森矩阵计算与分解的耗时限制。在中等维度下,矩阵分解的 $/mathcal{O}(d^3)$ 复杂度远超梯度计算的 $/mathcal{O}(nd)$,形成同步瓶颈,抵消了迭代优势。本文提出 extit{Split-Client} 框架,将优化解耦为并行的梯度与曲率过程。相比懒惰海森方法(其复杂度分析忽略分解时间且需调参),本方法完全 extbf{延迟自适应}:其实际运行时间随平均延迟 $ar{τ}$ 变化,且达到最优懒惰方法的 $/mathcal{O}(\varepsilon^{-3/2}ar{ au})$ 收敛率而无需调参。针对持续的曲率误差,设计噪声自适应调度,实现 $ ilde{/mathcal{O}}(T^{-3/4})$ 的收敛速率(关于 $E[ orm{ abla f}]^{3/2}$),无需冗余正则化即可恢复已有结果。在可验证的子空间对齐条件下,基于 L-BFGS 的割线条件进行结构化分析,获得更快的 $/mathcal{O}(T^{-1})$ 速率,并提供两种情形间的平滑插值定理。将框架扩展至采样立方牛顿法,支持自适应批量大小与线性于 $T$ 的总采样预算。在两个非凸问题上的实验表明,在强分解主导场景下,相比原始方法提速高达800倍,相比懒惰方法提速30倍。
原文摘要 · Abstract (English)
Second-order optimization methods offer superior convergence rates but are often bottlenecked by the wall-clock cost of Hessian computation and factorization. In the moderate-dimensional regime where the full Hessian fits in memory, factorization $\mathcal{O}(d^3)$ typically dominates gradient evaluation $\mathcal{O}(nd)$, creating a synchronization barrier that negates the per-iteration progress of classical second-order methods. We propose the \emph{Split-Client} framework, which decouples optimization into parallel gradient and curvature processes. Unlike Lazy Hessian approaches, whose arithmetic-complexity analysis does not charge factorization time and whose optimal reuse frequency requires tuning, our method is fully \textbf{delay-adaptive}: its wall-clock complexity scales with the \emph{average} delay $\Barτ$, and it matches the optimally-tuned Lazy rate of $\mathcal{O}(\eps^{-3/2}\sqrt{\Barτ})$ without any tuning. For persistent curvature error, we provide a noise-adaptive schedule with $\widetilde{\mathcal{O}}(T^{-3/4})$ rate (on $E[\|\nabla f\|]^{3/2}$), recovering the rate that uniform-error analyses such as Kamzolov et al (2023) achieve via inflated regularization. Under a verifiable subspace-alignment condition, an additional \emph{structured} analysis based on the secant condition of L-BFGS gives a faster $\mathcal{O}(T^{-1})$ rate, with a hybrid theorem interpolating smoothly between the two regimes. We extend the framework to Subsampled Cubic Newton with adaptive batch sizes and an aggregate sampling budget linear in $T$. Experiments on two non-convex problems show wall-clock speedups of up to $800\times$ over Vanilla and $30\times$ over Lazy in the strongly factorization-dominated regime.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。