具有单调对手的对决优化
通过噪声、凸性和零阶优化等概念,研究在有界凸集合中的一类函数的优化问题,我们提出了一个基于质心方法的改进算法,证明其相对于最小值的差距的阶数小于 d^2/√n,且比现有文献中已知的 d^{2.5}/√n 的速度更快,并且更简化。
Jun, 2024
本文研究具有随机约束的在线凸优化问题,提出了一种新的原始 - 对偶镜像下降算法,其可以在不需要 Slater 条件的情况下达到与先前的方法相似的性能并允许等式约束。
Aug, 2019
本文研究一种在线优化过程,其中目标函数不是凸函数(也不是凹函数),而是属于广泛的连续次模函数类。我们提出了一种 Frank-Wolfe 算法的变体,它可以访问目标函数的全梯度,并证明它对未来最佳可行解的(1-1/e)- 近似具有 O(T 的平方根)的遗憾界。对于只能获得梯度的无偏估计的情况,我们还提出了在线随机梯度上升算法,并证明它也具有 O(T 的平方根)的遗憾界,但只能对未来最佳可行解的 1/2 的近似度。我们还将结果推广到 γ- 弱次模函数,并证明相同的次线性遗憾界。最后,在几个问题实例上演示了算法的效率,包括非凸 / 非凹二次规划,子模集函数的多线性扩展和 D - 最佳设计。
Feb, 2018
研究了具有健壮性约束的基数约束单调次模函数最大化问题,提出了逼近算法,并在限制相对较小的情况下,得到了相对较好的逼近结果,并应用结果解决了更普遍的独立性约束下的最大化问题。
Jul, 2015
通过 von Neumann 最小极大定理,我们研究了在线凸优化游戏的最优策略的遗憾。我们证明了,在这种对抗性环境中,最优策略的遗憾与随机进程设置中经验最小化算法的行为密切相关:它等于最小期望损失的总和与最小经验损失之间的差的最大值。我们展示了最优策略的遗憾具有自然的几何解释,因为它可以被视为一个上凸函数的 Jensen 不等式中的差距。利用此表达式,我们对各种在线学习问题的最优策略给出了上下界限制。我们的方法提供了无需构建学习算法的上界,而提供了对抗者的明确最优策略的下界。
Mar, 2009
该论文介绍了统一的无投影 Frank-Wolfe 类型算法,用于对抗性连续 DR - 次模优化,跨越了全信息和(半)助手反馈、单调和非单调函数、不同约束和类型的随机查询等情景。在非单调设置中,所提出的算法要么是第一个经过证明具有亚线性 α- 遗憾界的算法,要么具有优于现有技术的 α- 遗憾界,其中 α 是离线设置中的相应逼近界。在单调设置中,所提出的方法在 8 个考虑的情况中,在 7 个情况中给出了投影免费算法的最新亚线性 α- 遗憾界,同时与其余情况的结果相匹配。此外,本文还研究了对抗性 DR - 次模优化中的半助手反馈和助手反馈,推动了对这一优化领域的理解。
Mar, 2024
本文提出了一种基于随机赌博反馈模型的新型优化算法,采用椭球算法的泛化形式,对凸紧致集上的凸利普希茨(Lipschitz)函数最小化问题进行求解,证明其性能在满足一定条件下与时间步数 T 为 O(d^3/2)同阶,并获得了泛化性能的高阶乘性加速,表现出良好的应用前景和性能优势。
Jul, 2011
本论文提出了第一个适用于单调布尔函数的无偏、高效、正确的学习算法,并使用凸优化步骤增进了不正确学习算法。同时,该工作还给出了估计未知函数到单调性的距离的算法,这两个算法的运行时间及假设评估时间为 2^(Õ(√n/ε))
Apr, 2023
通过提供一种具有与最佳近似算法(在已知分布下)相对于平方根的 T 乘以 log T 束缚的通用在线学习算法,在半探测器环境中解决了在一大类 “单调” 随机问题中对于未知分布是否能够获得良好(近似)算法进行学习的问题。我们的框架适用于随机优化的若干基本问题,如先知不等式、潘多拉盒、随机背包、随机匹配和随机次模优化。
Dec, 2023
本文研究了无约束在线线性优化博弈中最小化后悔的算法,其中对于一个有界比较器集合,得到了该博弈的解及其渐进行为,同时针对更宽松的惩罚函数提出了相应的算法并得到了渐进解。
Feb, 2013