Oct, 2010

凸编程中基于信息的复杂性、反馈和动态

PDF
TL;DR通过反馈信息理论的视角，研究序列凸优化的内在限制。我们证明了，在优化算法中，为了获得最优解，算法必须能够积累关于目标的充分信息，这对于特定的假设和反馈类型限制了优化速度。我们的技术类似于统计学文献中用于估计程序风险的极小界，但不同之处是优化算法可以以受控方式收集观测数据。特别地，我们证明了优化算法常常遵循收益不高于成本的规律。我们利用这种方法推导了一类主动学习问题的基本下限，进一步实现了优化、实验设计、估计和主动学习中信息和量化信息之间的联系。
sequential convex optimizationfeedback information theoryoracle modelminimax lower boundsactive learning problem
发现论文，激发创造
  • 随机凸优化的预言机复杂度信息论下界

    本文研究使用计算机预测的随机凸优化的复杂性，提出了改善已知结果的方法，并获得了各种函数类的紧致极小复杂度估计。

    Sep, 2010

  • 主动学习与随机凸优化之间的算法联系

    该论文探讨了近年来关于主动学习和随机凸优化之间的理论相关性，并提出了两种算法，分别适用于一维阈值和 d 维凸优化的场景，旨在实现对这两个领域的最优控制，支持适应所有未知的凸性和平滑参数。

    May, 2015

  • 随机优化的购买信息

    本文研究如何以在线学习问题的形式购买信息来帮助随机优化问题，提出了一个 $2$-competitive 算法和一个 $e/(e-1)$-competitive 随机化算法，特别应用于 Min-Sum Set Cover 优化问题。

    Jun, 2023

  • 基于数据驱动的带不完美信息的反优化

    本研究着重于解决不完美信息下的数据驱动逆向优化问题，将其形式化为分布鲁棒规划，最小化预测决策与真实响应之间的最坏情况风险，并证明了该方法比现有方法更为有效。

    Dec, 2015

  • Tsybakov 噪声条件下一阶随机凸优化的最优速率

    本文研究了利用随机一阶预测器在凸集上最小化凸函数的问题，证明了函数在最小值点 $x_{f, S}^*$ 附近增长的速率是最优学习率的决定因素，并得到了关于学习率和复杂度的结论结果。

    Jul, 2012

  • 分布式凸优化的通信复杂度

    研究了分布式方法在凸学习与优化中所需要的通信效率的根本限制，在不同信息假设和函数类型条件下找到了现有算法已达到最坏复杂度的情况，同时也指出了仍有改进的余地，说明了当本地目标函数没有相似之处时（由于统计数据相似或其他原因），即使设备具有无限计算能力，也可能需要多次通信往返。

    Jun, 2015

  • 多信息源优化

    针对黑盒函数优化问题，本文提出了一种新算法，通过价值信息分析决策，处理了由模型差异和噪音观测所带来的不确定性，并在实验中验证了其相对其他先进技术具有更高的目标价值和更少的探索成本。

    Mar, 2016

  • (有偏) 带噪声梯度预言的凸优化

    提出了一种新的框架用抽象的预言家代替了具体的梯度估计方法，并统一了以前的工作，同时表明为了实现最优的根号 - n 速率，这种方法还需要进一步的研究。

    Sep, 2016

  • 高平滑度的零阶在线优化

    本文探讨了利用仅包含部分和嘈杂信息的凸函数最小化问题，特别着重于高度平滑问题的凸优化问题，包括逻辑回归等。研究表明，相对于基于梯度的算法，高阶平滑性可用于改善估计速率，并精确地依赖于平滑度的程度，同时提出了此类算法可行性的上限。最后，作者还在在线优化设置中取得了类似的结果。

    May, 2016

  • 主动顺序假设检验

    本文提出了两种启发式策略，通过动态规划建立了最优总成本的下界，研究了信息获取率和可靠性的极限，证明了第一个启发式方法的渐近最优性，同时分析了第二个启发式方法在有噪声动态搜索问题中的性能。

    Mar, 2012