Jan, 2024

符号扰动求和识别方法的样本复杂性：标量情况

PDF
TL;DRSign-Perturbed Sum (SPS) 是一种强大的有限样本系统辨识算法，可以为任何有限样本大小的真实数据生成系统构造具有确切覆盖概率的置信区间。本论文旨在填补这一研究空白，首次提供了关于 SPS 样本复杂度的结果，以及对于标量线性回归问题中 SPS 置信区间行为的研究，提供了基于三组不同假设条件的高概率上界，表明如果观测误差是亚高斯分布，那么 SPS 置信区间的大小将以几何速率收敛于真实参数，并且同样的界限适用于先前提出的置信区域外估计，最后，我们通过模拟实验证明了理论和经验的收敛速度。
sign-perturbed sumsystem identificationconfidence intervalssample complexitylinear regression
发现论文，激发创造
  • 基于数据相关充分统计扰动的私有回归

    采用后处理方法以私密发布边际导数为基础的数据依赖 SSP，在线性回归和逻辑回归中优于现有的数据无关 SSP，同时与合成数据的训练有关，机制的整体效用取决于对线性查询的回答情况。

    May, 2024

  • Guided-SPSA: 运用参数偏移规则辅助的同时扰动随机近似优化

    我们引入了一种新的梯度估计方法，称为 Guided-SPSA，它有意地结合了参数漂移规则和基于 SPSA 的梯度近似，能够在训练过程中减少所需的电路评估数量 15% 到 25％，并取得与参数漂移规则相比类似或更好的优化结果。Guided-SPSA 在所有情况下都优于标准 SPSA，并在参数子优化初始化等情况下优于参数漂移规则。我们通过数值实验展示了 Guided-SPSA 在量子机器学习的不同范式（如回归，分类和强化学习）上的性能。

    Apr, 2024

  • 稀疏主成分分析的平方和下界

    本文研究使用凸松弛法解决高维机器学习问题时，统计与计算的权衡。对稀疏主成分分析（Sparse PCA）问题和 Sum-of-Squares（即 Lasserre / Parillo）凸松弛法进行了探究。通过研究发现基于次数 - 4 的 SoS 算法不能改善计算次数为 k² 的情况，为这种强大的凸松弛算法族中的一部分问题建立了平均情况下的下限，说明它们存在困难问题。

    Jul, 2015

  • 稀疏系统辨识问题的样本复杂度

    本研究提出了一种稀疏系统辨识方法，使用一个稀少的输入 - 状态数据样本来确定系统的动力学，并确保仅仅需要多项式阶数数量的样本即可精准还原系统的稀疏结构。这一方法已经在多个实验中证明了其效用。

    Mar, 2018

  • 随机鞍点问题的泛化界

    本文研究了随机鞍点问题的经验鞍点解的泛化界，证明了在具有 Lipschitz 连续和强凸强凹的目标函数的情况下，可以使用统一稳定性论证来建立一个 O（1/n）的泛化界，并在没有强凸性和没有有界域的情况下提供了泛化界。在马尔可夫决策过程中的批量策略学习和用于随机博弈的混合策略纳什均衡估计的两个示例中，我们展示了正则化 ESP 解具有接近最优样本复杂度。

    Jun, 2020

  • 重新审视 Nystrom 方法以改进大规模机器学习

    本篇研究论文旨在重新考虑随机算法用于对称半正定矩阵的低秩逼近，通过实证评估了样本抽样和投影方法的性能质量和运行时间，证明了它们的互补性，在相对误差较低前提下表明了不同采样方法之间的重要区别，并为随机抽样和随机投影方法提供最坏情况的理论边界。

    Mar, 2013

  • 自适应 Polyak 步长和线性搜索的 SGD 算法：稳健收敛和方差降低

    该研究提出了两种新的变体的随机 Polyak 步长和随机线性搜索算法，名为 AdaSPS 和 AdaSLS，它们保证了在非插值设置下的收敛，并在训练超参数化模型时维持凸函数和强凸函数的次线性和线性收敛速度。此外，通过引入方差缩减技术，这些算法能够在次优情况下进行梯度评估，达到 O（ε）次优性，从而改进了非插值区域 AdaSPS 和 AdaSLS 的较慢 O（1/ε^2）收敛速度。实验验证了算法的理论有效性和稳健性。

    Aug, 2023

  • 平衡子集稳定预测

    本文提出基于分数阶因式设计理论的平衡子采样稳定预测算法 (BSSP)，可减少由分布偏移引起的干扰效应，提高参数估计的准确性和预测稳定性，并在合成和真实数据集上取得了显著的优于基线方法的结果。

    Jun, 2020

  • 通过列选择进行 SPSD 矩阵近似：理论、算法和扩展

    本文针对正半定矩阵逼近的问题进行研究，提出了一个原型模型并建立了相应的错误边界，该模型具有更高的可扩展性和有效性。同时，本文提出了新的理论分析、高效算法和更为精确的扩展方法，并通过降低误差边界、改进现有的列选择算法，开发一种简单的选择算法，以及提出了一种谱移动模型来提高逼近的精度。

    Jun, 2014

  • SGD 的随机 Polyak 步长：快速收敛的自适应学习率

    本文介绍了一种新颖的随机 Polyak 步长方法，称为 SPS，它可以有效地用于随机梯度下降，特别是在训练超参数化模型时表现良好，并且在不需要任何与问题相关的常数或额外计算开销的情况下收敛速度快，并且与其他优化方法相比表现出色。

    Feb, 2020