Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms
Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
A. Camuto;George Deligiannidis;Murat A. Erdogdu;Mert Gurbuzbalaban;Umut cSimcsekli;Lingjiong Zhu
中科院分区：
文献类型：
--
作者：
A. Camuto;George Deligiannidis;Murat A. Erdogdu;Mert Gurbuzbalaban;Umut cSimcsekli;Lingjiong Zhu
过去十年来，理解深度学习的泛化一直是统计学习理论的主要挑战之一。虽然最近的工作表明必须考虑数据集和训练算法才能获得有意义的泛化界限，但理论上仍不清楚数据和算法的哪些属性决定泛化性能。在本研究中，我们从动力系统理论的角度来解决这个问题，并将随机优化算法表示为随机迭代函数系统（IFS）。在动力系统文献中经过充分研究，在温和的假设下，这种 IFS 可以被证明是遍历的，并且具有不变测度，而该不变测度通常在具有分形结构的集合上得到支持。作为我们的主要贡献，我们证明了随机优化算法的泛化误差可以基于其不变测度之下的分形结构的“复杂性”来限制。利用动力系统理论的结果，我们表明泛化误差可以与算法的选择（例如随机梯度下降 - SGD）、算法超参数（例如步长、批量大小）和问题的几何形状（例如损失的 Hessian 矩阵）明确相关。我们进一步将我们的结果专门针对特定问题（例如，线性/逻辑回归、一个隐藏层神经网络）和算法（例如，SGD 和预处理变体），并获得对我们的边界的分析估计。对于现代神经网络，我们开发了一种有效的算法来计算开发的边界，并通过神经网络上的各种实验来支持我们的理论。
Understanding generalization in deep learning has been one of the major challenges in statistical learning theory over the last decade. While recent work has illustrated that the dataset and the training algorithm must be taken into account in order to obtain meaningful generalization bounds, it is still theoretically not clear which properties of the data and the algorithm determine the generalization performance. In this study, we approach this problem from a dynamical systems theory perspective and represent stochastic optimization algorithms as random iterated function systems (IFS). Well studied in the dynamical systems literature, under mild assumptions, such IFSs can be shown to be ergodic with an invariant measure that is often supported on sets with a fractal structure. As our main contribution, we prove that the generalization error of a stochastic optimization algorithm can be bounded based on the `complexity' of the fractal structure that underlies its invariant measure. Leveraging results from dynamical systems theory, we show that the generalization error can be explicitly linked to the choice of the algorithm (e.g., stochastic gradient descent -- SGD), algorithm hyperparameters (e.g., step-size, batch-size), and the geometry of the problem (e.g., Hessian of the loss). We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden-layered neural networks) and algorithms (e.g., SGD and preconditioned variants), and obtain analytical estimates for our bound.For modern neural networks, we develop an efficient algorithm to compute the developed bound and support our theory with various experiments on neural networks.