Apr, 2024

梯度下降在可行性问题的 Oracle 复杂度和内存权衡中是帕累托最优的

PDF
TL;DR在这篇文章中，我们使用具有访问分离预言机的内存受限算法提供了解决给定集合中的点的 Oracle 复杂性下界，其中集合包含单位 d 维球体并且含有已知半径 ε 的球体。我们证明了对于准确度 ε≥e^(-d^(o (1))) 的可行性问题，任何确定性算法要么使用 d^(1+δ) bits 的内存，要么至少需要进行 1/(d^(0.01δ)ε^(2 ((1-δ)/(1+1.01δ))-o (1))) 次预言机查询，其中 δ∈[0,1]。此外，我们还证明了对于随机算法，要么使用 d^(1+δ) 的内存，要么至少需要进行 1/(d^(2δ)ε^(2 (1-4δ)-o (1))) 次查询，其中 δ∈[0,1/4]。由于梯度下降算法仅使用线性的内存 O (dln (1/ε))，但进行 Ω(1/ε^2) 次查询，我们的结果表明它在 Oracle 复杂性 / 内存权衡中是帕累托最优的。此外，我们的结果表明，如果算法在 d 维中具有小于二次的内存，则确定性算法的 Oracle 复杂性总是多项式级别的 1/ε。这揭示了一个明显的相变，因为对于二次的 O (d^2ln (1/ε)) 内存，割平面方法仅需要 O (dln (1/ε)) 的查询次数。
oracle complexityfeasibility problemsmemory-constrained algorithmdeterministic algorithmsquadratic memory
发现论文，激发创造
  • 基于递归割平面法的内存受限凸优化算法

    我们提出了一系列递归割平面算法，用于解决具有受限内存的可行性问题，这些算法可以用于一阶凸优化。

    Jun, 2023

  • 随机凸优化的内存 - 查询权衡

    该研究表明，任何随机第一阶段算法在单位球上最小化 $d$ 维、1-Lipschitz 凸函数时，必须使用 $Ω(d^{2−δ})$ 位内存或进行 $Ω(d^{1+δ/6−o (1)})$ 次查询，否则凸优化的最优查询复杂度需要使用四次方内存。

    Jun, 2023

  • 高度并行非光滑凸优化的复杂性

    研究在高度并行的梯度预言下，非光滑凸优化问题中梯度下降算法的优化次数上限，证明了仅当算法经过～(d)^(1/2) 轮的交互，梯度下降才是最优算法，并提出一种思路更优的算法。

    Jun, 2019

  • 随机优化中梯度压缩的限制

    研究了在 $\ell_p$ 空间内使用一阶 oracle 进行随机优化的问题，找到了保持无限制收敛速率所需的最小精度，通过导出信息论下界来表征这种精度，设计了实现简便的量化器，并对 $p=2$ 和 $p=\infty$ 的情况得出了最小精度分别为 $\Theta (d)$ 和 $\Theta (\log d)$ 的结论，后者的结果令人惊讶，因为恢复梯度向量需要 $\Omega (d)$ 比特。

    Jan, 2020

  • 无梯度下降：高维零阶优化

    该论文提出了两种简单但强大的无梯度估计的梯度下降（GLD）算法，并从一种新的几何视角进行分析，展示了其具有收敛性的优势，并且能够在保证单调变换不变的情况下，利用低的潜在维数来实现优化，对 BBOB 和 MuJoCo 基准测试产生了良好的实证效果。

    Nov, 2019

  • 随机凸优化中梯度变小的复杂性

    本文探讨了在随机凸优化问题中寻找近似驻点的 oracle 复杂度问题和其和全局 oracle 模型的关系，并提出了一种扩展的递归正则化算法以实现接近最优率，并揭示了 stochastic optimization 和 learning 的复杂度之间的一些惊人区别。

    Feb, 2019

  • 基于梯度滑动方法的少数据神经网络分布式随机约束优化

    现代分散应用中，通信效率和用户隐私是关键挑战。为了训练机器学习模型，算法必须与数据中心进行通信并对其梯度计算进行采样，从而暴露数据并增加通信成本。为了解决这个问题，我们提出了一种分散优化算法，它在通信效率上高效，并通过最优梯度复杂性达到了一个 ε- 近似解，对于凸和强凸的设置分别为 O (1/√ε+σ²/ε²) 和 O (log (1/ε)+σ²/ε)，对于两种设置都具有 O (1/ε²) 的 LO (线性优化) 复杂性，给定方差 σ² 的随机梯度预言。与之前的工作相比，我们的框架放宽了最优解是可行集的严格内点的假设，并在使用随机梯度预言进行大规模训练时具有更广泛的适用性。我们还通过各种数值实验证明了我们算法的效率。

    Apr, 2024

  • 非凸随机优化下的下限界

    采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界，使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型，证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型，我们证明了 ε^ -3 个查询的下界，建立了最近提出的方差缩减技术的最优性。

    Dec, 2019

  • 使用随机初始化的梯度下降：非凸相位恢复的快速全局收敛

    本文研究了使用梯度下降法（Wirtinger flow）求解二次方程组的问题，特别是相位恢复问题，证明了在高斯设计下，使用基本的梯度下降法可在 O (log n+log (1/ε)) 次迭代中给出接近最小化采样复杂度的 Epsilon - 精确解，而不需要特别设计的初始值、采样分裂或复杂的鞍点逃逸方案。

    Mar, 2018

  • 统计学习的一阶方法与通用预言机的泛化误差

    我们提供了一种新的分析框架，用于分析统计学习中基于一阶优化算法的泛化误差，当只能通过一个 oracle 提供的部分观测来获取梯度。我们的分析依赖于梯度相对于数据样本的正则性，并且允许为多个学习问题，包括监督学习、迁移学习、鲁棒学习、分布式学习和使用梯度量化的通信高效学习推导出接近配对的上下界的泛化误差。这些结果适用于平滑和强凸优化问题，以及满足 Polyak-Lojasiewicz 假设的平滑非凸优化问题。我们的上下界依赖于一个新颖的量，它扩展了条件标准差的概念，并衡量了通过访问 oracle 获取梯度的程度。因此，我们的分析为优化统计学习目标的优化提供了精确的含义，即统计学习目标的优化与其梯度估计一样困难。最后，我们证明，在标准监督学习的情况下，批梯度下降法随着批次大小的增加和热启动可以达到近似最优的泛化误差，从而激励我们在实际应用中使用这种优化方案。

    Jul, 2023