AAAISep, 2022

从理解 NSGA-II 的种群动力学到首个已证明的下界

PDF
TL;DR通过第一次对 NSGA-II 人口动态的数学理解，我们证明了适当的人口规模的 NSGA-II 需要 O（Nnlogn）函数评估来查找 OneMinMax 问题的 Pareto 前沿，并且需要 O（Nn^k）个评估来解决带跳跃大小为 k 的 OneJumpZeroJump 问题，这些界限与以前显示的上界相一致，并且表明即使在并行运行时间（迭代次数）方面，NSGA-II 在较大的种群大小上也不会获益。
nsga-iipopulation dynamicspareto frontfunction evaluationsonejumpzerojump
发现论文，激发创造
  • 极小极大优化的近似最优算法

    本文提出了一种基于加速的近端点方法和最小值近端步求解器的算法，其梯度复杂度为 O（kappa_x kappa_y^0.5），匹配了已有的最优下界，可用于解决强凸强凹、凸凹、非凸强凹和非凸凹函数的问题。

    Feb, 2020

  • 关于平滑非凸有限和优化的下界

    本文研究了平滑的非凸有限和优化的下界，并证明了在不同设置下找到 ε- 次优点和 ε- 近似稳定点的复杂度的严格下界，以及一些现有算法的最佳增量一阶预测器（IFO）复杂度。

    Jan, 2019

  • 约束条件下的随机优化：非渐近函解析

    通过分析局部最小值下界与扰动问题解的关系，我们证明了方差减小的近端梯度算法在样本数量趋向无穷大时达到了局部最小值下界，除了普适常数和对数因子的样本大小外。

    Mar, 2024

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

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

    Mar, 2015

  • 用一范数的最速下降法分析和改善对等约束优化的贪心 2 - 坐标更新

    通过在 L1 范数下的等式约束最速下降方法，考虑了考虑最小化一个带有一种约束并且有界约束的平滑函数的问题，提出了一种比随机选择更快的产生收敛的贪婪选择的收敛率，同时给出了支持向量机双重问题的规则。

    Jul, 2023

  • 基于 Polyak-Łojasiewicz 条件的极小化极大优化的更快随机算法

    基于 Polyak-Lojasiewicz 条件，本文提出了用于解决 minimax 优化问题的随机一阶算法 SPIDER-GDA，该算法在有限和的情况下达到了更好的优化效果，并降低了计算成本。

    Jul, 2023

  • 非凸强凹极小 - 极大优化的复杂性

    本文研究非凸强凹（NC-SC）平滑极小值问题的近似稳定点的复杂度，在一般和平均平滑有限和设置中建立了非平凡的较低复杂度下界。我们提出了一种通用的加速方案，使用现有的基于梯度的方法来解决一系列的精心制作的强凸 - 强凹子问题，进而缩小了复杂度差距，尤其是在一般情况下，我们提出的算法的复杂度几乎与下界相当。

    Mar, 2021

  • 有限和平凡导数光滑优化的复杂性研究

    本文研究了一种优化问题，在多项式朗托泽维奇条件下，通过梯度方法在分布式环境中找到次优解，提出了一个去中心化一阶方法，并给出了相应的下界。

    Feb, 2024

  • 优化有限和的下界

    本文提出了优化 n 个 L-smooth、强凸函数总和的下界，并将其与先前的方法进行比较。在随机数据情况下，我们将这些复杂度结果与用于直接优化总和的最优一阶方法进行对比。研究发现需要谨慎进行准确比较，并确定新方法在机器学习场景中的帮助计算能力。

    Oct, 2014

  • 利用二阶信息提高统计模型的计算复杂度

    通过使用二阶信息的标准化梯度下降法（NormGD）来解决参数估计问题，可以在样本量 n 的对数数量级内收敛，从而实现了达到最终统计半径的最优总体计算复杂度 O (n)。

    Feb, 2022