论文标题
基于梯度的算法的连续时间下限
Continuous-time Lower Bounds for Gradient-based Algorithms
论文作者
论文摘要
本文在基于连续时梯度的优化算法的收敛速率上得出了下限。算法受到时间归一化约束，该算法避免了时间的重新训练，以便对连续时间收敛率进行讨论有意义。我们将多维问题减少到单个维度，从离散时间设置中恢复众所周知的下限，并提供有关这些下限为什么发生的洞察力。我们提出可以实现所提出的下限的算法，即使所考虑的函数类别包括某些非convex函数。
This article derives lower bounds on the convergence rate of continuous-time gradient-based optimization algorithms. The algorithms are subjected to a time-normalization constraint that avoids a reparametrization of time in order to make the discussion of continuous-time convergence rates meaningful. We reduce the multi-dimensional problem to a single dimension, recover well-known lower bounds from the discrete-time setting, and provide insight into why these lower bounds occur. We present algorithms that achieve the proposed lower bounds, even when the function class under consideration includes certain nonconvex functions.
