- 通过更强的符号保持游戏改进校准的界限
在线校准预测二进制序列的基本问题的关键是应用推理,游戏理论和算法研究序列预测的校准性能,本研究通过引入新的游戏,加强和改进了现有算法,并提出了新的下界,从而改善以前的上界。
- 静态和动态遗憾最小化之间的等价关系
动态遗憾最小化在在线凸优化中是一个重要问题。本文提出了一个新的统一框架来分析和设计这些算法,证明了适应任意比较序列的动态遗憾达到 O (根号下 T 总和的局部平滑化平方路径长度) 的算法是可行的,并且提供了一个替代路径长度计算方式的新概念来 - 非光滑凸分散时间变网络优化的下界与最优算法
在时间变化的网络上,解决非光滑凸分布式优化问题时,本文首次确定了通信和子梯度计算复杂性的下界,并发展了与下界匹配且在理论性能方面明显优于现有技术的最优算法。
- 基于间歇通信的分布异构学习中局部 SGD 的局限性与潜力
本文利用现有的一阶数据异质性假设,为本地 SGD 提供了新的下界,显示了这些假设不足以证明本地更新步骤的有效性。此外,在相同的假设下,我们证明了加速小批量 SGD 的极小 - 极大优化性质,完全解决了几个问题类的分布式优化。我们的结果强调了 - 关于 UCT、AlphaGo 及其变种的超指数遗憾
改进 Coquelin 和 Munos(2007)的证明,证明了在 D 链环境上,UCT 算法可能导致指数级(D 的指数次)的遗憾,且具有与指数 2 的指数 2 减去 O (log D) 成正比的多项式的 UCT 变体在相同环境上也可能导致 - 非先知性调度与部分预测
非全知调度问题的学习增强算法中具备预测但没有质量保证,通过对只有部分作业大小的预测进行研究,建立了近似最优下界和算法,并呈现了在预测数量受限情况下一种新的一致性和平滑性之间的权衡关系。
- 高斯协方差矩阵私密估计在合理参数范围下的下界
我们通过使用 Stein-Haff 恒等式,对于高斯分布的协方差矩阵进行私密估计所需的样本数量给出了下限。我们的下限与已知参数设置下的上限相匹配。
- Adam 在非均匀平滑性条件下的收敛性:从 SGDM 到更进一步的分离性
本文旨在清楚地区分随机梯度下降法和带动量的 Adam 算法在收敛速度方面的差异。我们证明了在非均匀有界平滑性条件下,Adam 算法相对于随机梯度下降法具有更快的收敛速度。我们的发现表明:(1)在确定性环境中,Adam 算法可以达到确定性一阶 - 关于差分隐私在线学习中错误增长的下界透视
对差分隐私在线学习算法提供了下界,表明广泛类别的(ε, δ)- 差分隐私在线算法 — 当满足 log T≤O (1/δ) 时,算法产生的错误数量的期望呈 Ω(log (T/δ)) 增长,与非隐私在线学习不同,其中错误数量与 T 无关。据我们 - 学习半空间交集的改进难度结果
通过与半空间和所谓的并行煎饼分布的新颖联系,我们以统一的方式获得了较强(而且令人惊讶地简单)的在不适当的情况下学习半空间交集的下界,这是过去几年强大的高维统计学中许多下界构造的核心,我们还给出了统计查询框架下的无条件难度结果。
- 自适应一阶优化方法的收敛性:近端梯度和交替最小化算法
基于最近的无线搜索自适应近端梯度方法,本文提出了 AdaPG^rπ 框架,通过提供更大的步长策略和改进的下界,统一和扩展了现有的结果。讨论了参数 π 和 r 的不同选择,并通过数值模拟证明了所得方法的有效性。为了更好地理解基本理论,还建立了 - 一种关于连续随机变量右尾概率的新型上下界
该研究提出了一种全新类型的上限和下限,用于表示具有无界或左半无界支持的连续随机变量的右尾概率。这些新的上限和下限只依赖于概率密度函数(PDF)、其一阶导数和两个用于收紧边界的参数,并在特定条件下成立。通过数值示例,证明了这些尾部边界对于广泛 - 在轻松平滑条件下的参数无关优化
通过理论和实验证明,Normalized Stochastic Gradient Descent with Momentum 算法在没有先验知识的情况下可以实现(接近)最优复杂度,但复杂度中引入了一个依赖于 (L_1) 的指数项,这是不可避 - 入项变换矩阵乘积的低秩逼近难度
在输入转换设置中,我们研究低秩逼近,给出了该问题的条件时间难度结果和运行时下界,同时证明了这些下界是紧致的,并提供了使用基于张量的草图的相对误差逼近算法。
- 具有固定预算的局部最优最佳臂鉴别
通过实验设计和策略分析,本研究旨在在固定的实验轮数下,识别具有最高预期结果的最佳治疗方案,以及减少误判的概率和通过计算概率下界来设计最优策略。
- 利用填充和置换指纹码的差分隐私算法平滑下界
本论文提出了一种简单的方法来生成困难实例,并利用该方法在不同情境下提供了新的差分隐私(DP)下界,其中主要的技术是将 padding-and-permuting 变换应用于 fingerprinting code。
- 亚线性复杂度下非凸非光滑约束组合问题的一阶优化方法:下界复杂度与近似最优方法
本文针对一个类别的复合非凸非光滑优化问题,通过使用两个不同的一阶预言机,在最优性公差 ϵ>0 的情况下建立 FOMs 的下界复杂性界,并提出一个非精确近端梯度法来解决该问题。所提出的 IPG 方法的预言机复杂度与我们建立的下界匹配。
- 关于在群检测中检测某些缺陷品的研究
本研究探讨了使用不同的群组检测算法来识别不同数量的不良元素的问题,提出了自适应和非自适应算法的上下界,并讨论了是否有先验知识或估计确切数量的情况下的检测数量的限制。
- 关于含噪计算的最优界限
本研究重新审视了来自 Feige 等人的 1994 年的噪声信息计算问题,改进其上下界以更好地描述查询复杂性,并考虑了自适应采样和非自适应采样这两种情况。
- 平衡对抗模型下的自适应数据分析
本文研究了在自适应数据分析中使用受限制的对手模型,证明了使用标准公钥加密假设的更强的困难性假设是不可避免的,并提高了以前的下界质量。