Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient
Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Ankit Pensia;Shashank Rajput;Alliot Nagle;Harit Vishwakarma;Dimitris Papailiopoulos
中科院分区：
文献类型：
--
作者：
Ankit Pensia;Shashank Rajput;Alliot Nagle;Harit Vishwakarma;Dimitris Papailiopoulos
强彩票假设（LTH）假设人们可以通过修剪充分过参数化的随机网络的权重来近似任何目标神经网络。Malach等人最近的一项工作。Cite{MalachEtAl 20}建立了强LTH的第一个理论分析：通过修剪一个宽为$O（d^4l^2）$且深为$l$的随机神经网络，可以证明近似宽度$d$和深度$l$的神经网络。这种多项式过度参数化的要求与最近的实验研究不一致，这些研究通过比目标宽一个小因子的网络实现了良好的近似。在这项工作中，我们关闭的差距，并提供了一个指数级的改进，以参数化的要求存在的彩票。我们证明，任何目标网络的宽度$d$和深度$l$可以近似修剪一个随机网络，是一个因素$O（\log（dl））$宽和两倍深。我们的分析在很大程度上依赖于将修剪随机ReLU网络连接到\textsc{SubsetSum}问题的随机实例。然后，我们证明了这种对数过参数化对于恒定深度网络基本上是最优的。最后，我们用实验验证了我们的一些理论见解。
The strong {\it lottery ticket hypothesis} (LTH) postulates that one can approximate any target neural network by only pruning the weights of a sufficiently over-parameterized random network. A recent work by Malach et al.~\cite{MalachEtAl20} establishes the first theoretical analysis for the strong LTH: one can provably approximate a neural network of width $d$ and depth $l$, by pruning a random one that is a factor $O(d^4l^2)$ wider and twice as deep. This polynomial over-parameterization requirement is at odds with recent experimental research that achieves good approximation with networks that are a small factor wider than the target. In this work, we close the gap and offer an exponential improvement to the over-parameterization requirement for the existence of lottery tickets. We show that any target network of width $d$ and depth $l$ can be approximated by pruning a random network that is a factor $O(\log(dl))$ wider and twice as deep. Our analysis heavily relies on connecting pruning random ReLU networks to random instances of the \textsc{SubsetSum} problem. We then show that this logarithmic over-parameterization is essentially optimal for constant depth networks. Finally, we verify several of our theoretical insights with experiments.