357 在算法中排名

每月 73 次下载

MIT/Apache

70KB
946 行

多线程随机梯度下降

本包提供了某些随机梯度算法的 Rust 实现。

这里实现的算法致力于最小化由多个函数的均值表示的（凸）目标函数，这些函数在各种统计和学习环境中出现。

实现的算法包括

由李磊和 M.I Jordan 的两篇论文描述和分析的所谓 SCSG 算法。
- "基于随机梯度的优化适应性" (2019,2020) SCSG-1
- "少于单次遍历：随机控制的随机梯度" (2019) SCSG-2
由 R. Johnson 和 T. Zhang 的论文描述的 SVRG 算法 "使用预测方差减少加速随机梯度下降" (2013)。
神经网络信息处理系统进展，第 315–323 页，2013
由 M.Schmidt, N.LeRoux, F.Bach 描述的随机平均梯度下降 (SAG)，如论文：“使用随机平均梯度最小化有限和” (2013, 2016)。

这些算法通过以下表达式最小化函数

    f(x) = 1/n ∑ fᵢ(x) where fᵢ is a convex function.

算法交替进行某种形式的大批量计算（计算和的许多项的梯度）和小批量（计算少量项，可能只有一项，的梯度）并更新位置，通过结合这些全局和局部梯度来完成。

示例和测试

小型测试包括一个来自优化包的线性拟合问题。

示例基于逻辑回归应用于 MNIST 数据库（如 SCSG 的第二篇论文）。
数据文件可以从 MNIST 下载。

使用 3 种算法测试了具有 10 个类别的逻辑回归，并提供了比较结果的注释。

运行时间是在 i9-13900HX (32 个线程) 上获得的。我们给出了系统时间和最小化器中花费的 CPU 时间。

关于参数 B_0 和 m_O 的含义，请参阅 SCSG 文档。所有运行中 b_0 都设置为 1。

以下是一些结果

迭代次数	B_0	m_0	步长_0	误差	时间(s)	CPU 时间(s)
50	0.015	0.004	0.1	0.285	2.9	14.8
50	0.015	0.006	0.1	0.279	6.8	19
100	0.02	0.004	0.1	0.266	7.89	32.5
50	0.02	0.004	0.1	0.289	3.89	16
150	0.02	0.004	0.1	0.257	12	50
150	0.02	0.002	0.1	0.269	6.5	45

迭代次数	B_0	m_0	步长_0	误差	时间(s)	CPU 时间(s)
50	0.015	0.004	0.1	0.274	4.7	17
50	0.02	0.004	0.1	0.277	3.7	16.5
50	0.02	0.006	0.1	0.267	5.5	18
100	0.02	0.004	0.1	0.260	7.6	33

增加参数以降低minibatch数量来提高并行度。
从零图像初始化的收敛似乎比使用恒定的0.5像素稍微容易一些。

迭代次数	nb迷你批处理	步骤	误差	时间(s)	CPU 时间(s)
100	1000	0.02	0.269	10.5	159
25	1000	0.05	0.288	2.6	40
50	1000	0.05	0.263	5.	81
100	1000	0.05	0.249	10.2	160

迭代次数	nb迷你批处理	步骤	误差	时间(s)	CPU 时间(s)
50	1000	0.05	0.258	5.3	80
50	2000	0.05	0.247	7.5	81
100	1000	0.05	0.247	10	161

迭代次数	批大小	步骤	误差	时间(s)	CPU 时间(s)
1000	1000	0.2	0.47	17	272
1000	1000	0.5	0.35	17	273
1000	2000	0.5	0.34	17.6	262
2000	1000	0.5	0.297	34.6	546

测试表明，在正确初始化和远离解的情况下，SCSG在等效精度下CPU时间比SVRG高1.5倍。SVRG明显优于SAG。
SCSG在达到良好的近似值（约0.28）方面非常快，尽管在这个实现中它从未运行在整个（十分之一）。SCSG需要更大的问题才能从多线程中受益。

这个crate借鉴了crate 优化，在其中我保留了经过各种修改后定义用户界面的Function和Summation特质，这些修改在文件types.rs中详细说明。

根据您的选择，许可如下：

。

~5MB
~90K SLoC