人们通常可以想到机器学习中的两种硬度结果：统计学习背景下的信息论硬度（即，为学习所需的最小示例数量提供下限）和算法硬度（即，错误的算法选择意味着优化变得不可能）。

在深度学习的背景下，讨论硬度是很棘手的，因为我们实际上对理论上深度学习的工作原理知之甚少。（回想一下：在深度学习中解决的优化问题是最小化一个高维高度非凸函数，并且通常被认为是 NP-hard。即，不能保证达到全局最小值。然而在实践中，从业者已经使用 SGD 的变体很好地解决了许多问题。最近在给出合理答案方面取得了一些进展，说明为什么会这样，但这超出了您的问题范围。）

深度学习中算法难度的一个很好的例子是尝试学习梯度无信息的问题。深度学习目前使用某种形式的 SGD 来更新网络的权重。例如，小批量 GD 计算成本函数在个示例的随机样本上的梯度，参数为 ：$b$$\theta$

$\theta_{t+1} = \theta_t - \alpha_t \cdot \nabla_\theta J(\theta; x^{(i:i+b)},y^{(i:i+b)})$

换句话说，DL优化是试图 通过使用局部梯度信息来全局优化一个函数；这表明，如果一个学习问题的特征是非信息梯度，那么任何深度学习架构都无法学习它。

学习随机奇偶校验是以下学习问题：

选择向量后，目标是训练预测映射 到 ，其中一致分散式。换句话说，我们试图学习一个映射来确定（由 表示）的某个坐标子集中的 1 的数量是偶数还是奇数。$\boldsymbol{v^*} > \in \left\{ 0,1\right\}^d$$\boldsymbol{x\in}\left\{ 0,1\right\} ^{d}$$y=\left(-1\right)^{\left\langle \boldsymbol{x,v^{*}}\right\rangle }$$\boldsymbol{x}$$\boldsymbol{x}$$\boldsymbol{v^*}$

在“Failures of Gradient-Based Deep Learning”（Shamir，2017）中，作者证明了这个问题（更一般地说，每个由周期性函数组成的线性函数）都存在非信息梯度，因此使优化问题变得困难.

他们还通过测量不同输入维度的训练迭代次数函数的准确性来实证证明这一点。

这里使用的网络是一个宽度为的具有 ReLU 激活的全连接层，以及一个具有线性激活和单个单元的全连接输出层。（选择宽度以确保所需的奇偶校验功能确实由这样的网络实现）$10d$

问：为什么学习平价只有在左右才变得困难？$d=30$

如果您没有对问题施加正确的结构，它就会失败。卷积神经网络之所以有效，是因为它们假设彼此接近的像素是相关的，因此将空间卷积应用于您的特征是有意义的。在这样做的过程中，您大大减少了假设搜索空间，这意味着深度学习更有可能达到最佳解决方案。

如果您将深度学习应用于特征不适合空间/时间卷积的问题，那么深度学习将失败，因为总结某些特征并将函数应用于求和是没有意义的，这就是神经网络可以。

如果有人能想到一个例子，说明深度学习已成功应用于不是图像或音频（或空间/时间数据）的数据，我会很高兴收回这个答案。