论文标题
具有迭代性非梯度算法的Relu Gate的可证明培训
Provable Training of a ReLU Gate with an Iterative Non-Gradient Algorithm
论文作者
论文摘要
在这项工作中，我们证明了在迄今未探索的政权中对单个Relu Gate进行培训的可证明的保证。我们给出了一种简单的迭代随机算法，该算法可以在线性时间内在可实现的设置中训练一个relu门，同时比以前的结果在数据分布上使用明显较小的条件。 利用某些额外的时刻假设，我们还显示了对真实标签的True Laber生成参数的首个近似恢复，同时通过相同的算法训练Relu Gate。我们的保证在最坏的情况下几乎是最佳的，并且它可以随着攻击的概率及其幅度的增加而恢复真正的重量的准确性。 对于上面概述的可实现的和不可交流的情况，我们的分析允许微型批量构成，并计算收敛时间如何用迷你批量的大小缩放。我们通过模拟结果证实了我们的定理，这也揭示了我们算法和流行的S.G.D.之间的轨迹的惊人相似性。算法 - 对于此处，与此相似的保证仍然未知。
In this work, we demonstrate provable guarantees on the training of a single ReLU gate in hitherto unexplored regimes. We give a simple iterative stochastic algorithm that can train a ReLU gate in the realizable setting in linear time while using significantly milder conditions on the data distribution than previous such results. Leveraging certain additional moment assumptions, we also show a first-of-its-kind approximate recovery of the true label generating parameters under an (online) data-poisoning attack on the true labels, while training a ReLU gate by the same algorithm. Our guarantee is shown to be nearly optimal in the worst case and its accuracy of recovering the true weight degrades gracefully with increasing probability of attack and its magnitude. For both the realizable and the non-realizable cases as outlined above, our analysis allows for mini-batching and computes how the convergence time scales with the mini-batch size. We corroborate our theorems with simulation results which also bring to light a striking similarity in trajectories between our algorithm and the popular S.G.D. algorithm - for which similar guarantees as here are still unknown.
