ICMLJul, 2012

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

PDF
TL;DR本文研究了利用随机一阶预测器在凸集上最小化凸函数的问题，证明了函数在最小值点 $x_{f, S}^*$ 附近增长的速率是最优学习率的决定因素，并得到了关于学习率和复杂度的结论结果。
convex functionstochastic oracletsybakov-like noise conditionlearning rateactive learning
发现论文，激发创造
  • 随机凸优化的预言机复杂度信息论下界

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

    Sep, 2010

  • 强凸性和利普希茨 Hessian 下的随机零阶优化：极小 - 最大样本复杂度

    在在线学习中，优化随机零阶反馈下的凸函数一直是一个主要而具有挑战性的问题。本文考虑了仅能对目标函数进行噪声评估的情况下，对二阶平滑和强凸函数进行优化的问题；通过提出匹配的上下界，第一次对最小化最大简单后悔的速率进行了紧密的刻画。我们提出了一种算法，结合了启动阶段和镜像下降阶段。我们的主要技术创新包括对高阶平滑性条件下球形采样梯度估计器的尖锐刻画，从而使算法能够在偏差 - 方差权衡方面达到最优平衡，以及一种用于启动阶段的新的迭代方法，它能够保持无界 Hessian 的性能。

    Jun, 2024

  • 平滑强凸函数的随机逼近：超越 $O (1/T)$ 收敛速度

    利用凸性和平滑性同时优化了随机逼近的收敛速度，并构建了高效的随机算法来达到风险界限。

    Jan, 2019

  • 带有强盗反馈的随机凸优化

    本文提出了一种基于随机赌博反馈模型的新型优化算法，采用椭球算法的泛化形式，对凸紧致集上的凸利普希茨（Lipschitz）函数最小化问题进行求解，证明其性能在满足一定条件下与时间步数 T 为 O（d^3/2）同阶，并获得了泛化性能的高阶乘性加速，表现出良好的应用前景和性能优势。

    Jul, 2011

  • 噪声凸型零阶优化的简化改进算法

    通过噪声、凸性和零阶优化等概念，研究在有界凸集合中的一类函数的优化问题，我们提出了一个基于质心方法的改进算法，证明其相对于最小值的差距的阶数小于 d^2/√n，且比现有文献中已知的 d^{2.5}/√n 的速度更快，并且更简化。

    Jun, 2024

  • 私有优化中的功能困难和生长条件适应

    本文提出了一种适应目标函数难度的私有随机凸优化算法，对于具有 ' 增长 ' 趋势的函数，可以实现更快的隐私速率，而不需要知道增长常数 κ，算法基于反敏感机制和隐私优化中的本地化技术，并具有匹配的下界。

    Aug, 2021

  • 基于随机模型的弱凸函数最小化

    本文提出一族算法通过简单的随机模型样本和优化方法，成功的减少了目标函数。我们展示出，合理的近似质量和模型的正则性下，此类算法将自然的稳定度衡量推向 0，该衰减速度为 O (k^(-1/4))，基于此原理，我们为随机的近端子梯度法，近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。

    Mar, 2018

  • 非强凸平稳随机逼近，收敛速率 O (1/n)

    本篇论文研究了关于随机逼近问题的现有算法，提出了两种新型随机梯度算法，并在回归和逻辑分类两种经典的监督学习问题上进行了测试，得到了较好的优化效果。

    Jun, 2013

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

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

    Oct, 2010

  • 鲁棒线性回归：多项式时间内的最优速率

    本文提出了一种在数据为超收缩分布、存在不可避免的敌对噪声情况下，基于平方和框架的线性模型学习算法，该算法的收敛速度与扰动的比例成幂率关系，能达到理论最优收敛速度且在先前研究中未被发现。

    Jun, 2020