python - LBFGS 在 pytorch 中永远不会在大维度上收敛

Question

我正在研究 Wolfram 元胞自动机的规则 110。给定一行零和一，您可以使用以下规则计算下一行:

从 00000000....1 开始，最后你得到这个序列:

出于好奇，我决定用多项式来近似这些规则，这样单元格不仅可以是 0 和 1，还可以是介于两者之间的灰色:

def triangle(x,y,z,v0):
    v=(y + y * y + y * y * y - 3. * (1. + x) * y * z + z * (1. + z + z * z)) / 3.
    return (v-v0)*(v-v0)

因此，如果 x、y、z 和 v0 与表中的任何规则匹配，它将返回 0，否则返回正非零值。

接下来，我将所有可能的 4 个邻居组添加到单个总和中，对于整数解，该总和为零:

def eval():
    s = 0.
    for i in range(W - 1):
        for j in range(1, W + 1):
            xx = x[i, (j - 1) % W]
            yy = x[i, j % W]
            zz = x[i, (j + 1) % W]
            r = x[i + 1, j % W]
            s += triangle(xx, yy, zz, r)
    for j in range(W - 1): s += x[0, j] * x[0, j]
    s += (1 - x[0, W - 1]) * (1 - x[0, W - 1])
    return torch.sqrt(s)

还在这个函数的底部，我为第一行添加了普通条件，这样除了最后一个元素(即 1)之外，所有元素均为 0。最后，我决定使用 pytorch 最小化 W*W 矩阵上的平方和:

x = Variable(torch.DoubleTensor(W,W).zero_(), requires_grad=True)
opt = torch.optim.LBFGS([x],lr=.1)
for i in range(15500):
    def closure():
        opt.zero_grad()
        s=eval()
        s.backward()
        return s
    opt.step(closure)

这里是full code ，你可以自己尝试一下。问题是，对于 10*10，它会在大约 20 步内收敛到正确的解决方案:

但是如果我采用 15*15 板，它永远不会完成收敛:

右图显示了平方和如何随着下一次迭代而变化，您可以看到它永远不会达到零。我的问题是为什么会发生这种情况以及如何解决这个问题。尝试了不同的 pytorch 优化器，但它们的性能都比 LBFGS 差。尝试了不同的学习率。有什么想法为什么会发生这种情况以及我如何在优化过程中达到最终点吗？

UPD:改进的收敛图，SOS 日志:

UPD2:我也尝试使用 dlib 在 C++ 中做同样的事情，而且我没有任何收敛问题，它在更短的时间内进行得更深入:

我使用此代码在 C++ 中进行优化:

find_min_using_approximate_derivatives(bfgs_search_strategy(),
        objective_delta_stop_strategy(1e-87),
        s, x, -1)

Answer 1

您在这里尝试做的是非凸优化，这是一个众所周知的难题。一旦您思考一下，就会发现这是有道理的，因为几乎任何实际的数学问题都可以表述为优化问题。

<强>1。前奏
因此，在提示您在哪里找到特定问题的解决方案之前，我想说明一下为什么某些优化问题很容易解决。

我将从讨论凸问题开始。即使在受约束的情况下，这些问题也很容易解决，其原因是，当您计算梯度时，您实际上会获得大量关于最小值不可能在哪里的信息(凸函数 f 的泰勒展开始终是一个低估 f)，此外只有一个最小值并且没有鞍点。如果您有兴趣了解有关凸优化的更多信息，我建议您在 YouTube 上查看 Stephen Boyd 的凸优化类(class)。

既然非凸优化如此困难，我们为何能够在深度学习中解决它呢？答案很简单，我们在深度学习中最小化的非凸函数非常好，如Henaff et al所示。 .

因此，机器学习从业者必须认识到，深度学习中使用的运算程序在处理其他非凸问题时，如果一开始就收敛到最小值，很可能不会产生良好的最小值。

<强>2。回答你的问题
现在来回答你的问题，你可能不会找到快速的解决方案，因为非凸优化是 NP 完成的。但不用担心，SciPy 有一些全局优化算法可供选择。 Here是另一个堆栈溢出线程的链接，它很好地回答了您的问题。

<强>3。这个故事的寓意
最后，我想提醒您，收敛保证很重要，忘记它会导致 oil rig collapsing .

PS。请原谅拼写错误，我正在使用手机

更新: 至于为什么 BFGS 与 dlib 配合使用，可能有两个原因，首先，BFGS 比 L-BFGS 更擅长使用曲率信息，其次，它使用线搜索来查找曲率信息。最佳步长。我建议检查 PyTorch 是否允许行搜索，如果不允许，则设置递减的步长(或者只是非常低的步长)。