Jun, 2023

从 $O (\sqrt {n})$ 到 $O (\log n)$ 的二次规划算法优化

PDF
TL;DR该论文介绍了一个新的优化算法，通过严密的理论证明证明存在一个算法复杂度 O (log (n))，并且将平滑二次规划 (QP) 和非平滑 Lasso 重构为 Box-QP。通过计算得到算法的迭代次数为（log (3.125n/ε) /log (1.5625)）.
numerical optimization theoryiteration complexitybox-qplassoalgorithm
发现论文，激发创造
  • 随机目标和约束下非线性规划的单循环算法复杂性

    分析具有函数等式约束的非凸优化问题的单环二次罚函数和增广 Lagrange 算法的复杂性，通过三个不同情况的考虑得出具体复杂度，使用方差减少技术改进复杂度，这些算法为第一种和第三种情况的首个 “单环” 类型算法并且仍然具有最佳已知复杂度保证。

    Nov, 2023

  • 关于平滑和强凸优化问题的下限和上限

    我们开发了一个新的框架来研究光滑和强凸优化算法，特别是针对二次函数，我们能够将优化算法作为线性运算的递归应用程序来检查，这揭示了一种强大的联系，即一类优化算法与多项式的分析理论之间的联系，从而导出了新的下界和上界，同时我们还以多项式相关的最优解的形式表达它，从而对 Nesterov 著名的加速梯度下降方法进行了新的系统推导。

    Mar, 2015

  • 论忘却式一阶优化算法的迭代复杂度

    考虑基于常数步长的广泛一阶优化算法，其中任何该类算法对于 L - 平滑的凸函数的迭代复杂度下界为 Ω(根 (L/ε))。

    May, 2016

  • 一种用于结构化支持向量机的近线性时间算法

    本文提出了第一个解决具有低秩因子或低树宽度和少量线性约束的二次规划的近似线性时间算法，并暗示了具有低树宽度或低秩的支持向量机的近似线性时间算法。

    Jul, 2023

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

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

    Jun, 2019

  • 使用优化获得宽度无关、并行、简单、更快的正定半定规划求解器

    本文针对包装和覆盖半正定程序（或正半定规划）的近似求解，研究了多对数深度算法的设计，并提出了一种基于优化框架的简单算法，其正确性基于 Lieb-Thirring 不等式的新矩阵不等式和梯度截断技术的随机变体。

    Jul, 2015

  • 基于线性优化预言机的大规模凸优化问题的复杂性

    本文探讨了一类名为线性优化型凸规划算法的迭代优化算法，证明了它们解决一系列滑顺、非滑顺和某些鞍点问题的低复杂度下界； 验证了在大规模情况下，条件梯度法及其变种求解不同类别的凸规划问题的理论最优性或接近最优性； 推出了几种新的最优 LCP 方法，并通过修改 Nesterov 的加速梯度方法，证明了它们在解决一些大规模凸规划问题的特定类别时的优势。

    Sep, 2013

  • 通过积分二次约束分析优化算法：非强凸问题

    本文提出了一个统一的框架，能够证明广泛使用的迭代一阶优化算法的指数收敛和次指数收敛速率，并展示了该框架对梯度法、近端算法及其加速变体的实用性，同时开发了连续时间对应物，能够分析梯度流和 Nesterov 加速法的连续时间极限。

    May, 2017

  • SQRT-Lasso 优化问题中近端算法的快速收敛：无需担心其非光滑损失函数

    本研究针对机器学习中使用的 Square-root-Lasso（SQRT-Lasso）回归问题，发现通过研究建模结构，这种方法可以同时获得效率和准确性，同时提出使用 proximal 算法（如 proximal gradient descent，proximal Newton 和 proximal quasi-Newton）进一步地提高效率。

    May, 2016

  • 一种更快的切平面方法及其对组合优化和凸优化的影响

    通过使用标准约减和新技术的混合方法，我们改进了查找凸集中点的运行时间，同时提高了在连续和组合优化中的算法性能，特别是子模规划和半定规划问题。

    Aug, 2015