学习算法的统计不可区分性
我们提出了一种实用的方法,使用一个未在训练中暴露给模型的小规模保留数据集来审计差分隐私(DP)保证。我们的方法利用得分函数(如训练期间使用的损失函数)估计使用训练数据子集和保留数据集获得的得分之间的总变差(TV)距离,在了解底层 DP 训练算法的一些元信息的情况下,这些 TV 距离值可以转换为任意 δ 的(𝜖, δ)保证。我们表明,这些得分分布渐近地为底层训练算法的 DP 保证提供下界,但基于实用性的原因,我们对其进行了一次估计。我们指定导致高概率下界 DP 保证的条件。为了估计得分分布之间的 TV 距离,我们使用了基于直方图的简单密度估计方法。我们表明,TV 距离提供了一个非常接近最优鲁棒估计器,并具有一个误差率𝒪(k^(−1/3)),其中 k 是总样本数。基准数据集上的数值实验说明了我们方法的有效性,并展示了对于黑盒审计的改进。
Jun, 2024
本文基于判别性方法提出了一种评估生成数据保真度的方法,利用总变差距离作为有效的度量。通过定量地表征两个分布分类的贝叶斯风险和它们的总变差距离的关系,实现了总变差距离的估计。特别地,本文建立了关于两个高斯分布总变差距离估计误差收敛速率的理论结果。通过选择特定的分类假设类,能够实现总变差距离的快速收敛速率。当两个高斯分布之间的分离度越大时,估计总变差距离的准确性越高,这一现象也通过广泛的模拟得到了实证验证。最后,我们将该判别性估计方法应用于使用 MNIST 数据集的合成图像数据的保真度排序。
May, 2024
本文研究机器遗忘问题,并确定算法稳定性的概念 —— 总变差(TV)稳定性,通过噪声随机梯度下降(SGD)设计基于 TV 稳定算法的高效遗忘算法,为了了解准确性与遗忘效率之间的权衡,本文对凸风险最小化的 TV 稳定算法进行了上下界分析,该技术可以推广到任意非凸函数,而且算法具有差分隐私保护。
Feb, 2021
研究了在高维高斯混合假设下,少量数据受到对手损坏的情况下的高效可学习性,提出了一种多项式算法并证明了在成分经过配对后在总变异距离上分离时,该问题是可多项式学习的;这种算法是第一个可处理 $k=2$ 的高斯混合问题的多项式时间算法,并使用基于 Sum-of-Squares 证明算法的技术,提出了一种新的用于高斯混合的鲁棒可辨识性证明方法和使用 SoS 可证明的反集中方法和新的特征距离度量组来解决问题。
May, 2020
提供了可靠与高效的算法来测试本地化的差异距离,进一步扩展了 TDS 学习模型并改进了之前相关的工作,同时提供了针对常数深度电路的指数级改进,与低维凸集的首个正面结果。
Jun, 2024
我们展示了学习理论文献中的许多稳定性定义是等价的,我们区分了两个稳定性定义家族:依赖于分布的稳定性和独立于分布的贝叶斯稳定性。在每个家族中,我们建立了各种定义之间的等价性,涵盖了近似差分隐私、纯差分隐私、可复制性、全局稳定性、完美泛化、TV 稳定性、互信息稳定性、KL 散度稳定性和 Renyi 散度稳定性。通过这个过程,我们证明了一些提升结果,可以增强学习规则的稳定性。这项工作是朝着更系统的稳定性概念分类法迈出的一步,可以促进稳定性概念的清晰性和我们对近年来涌现的各种稳定性概念的理解的提升。
Oct, 2023
探讨强化学习领域中复制性的数学研究,提出了基于生成模型下的可复制性 RL 算法,其中包括一个有效的 $ ho$-replicable 算法和一个可计算的近似可复制的算法。
May, 2023
该研究提出了一种简单有效的方法,将概率分布嵌入再应用岭回归 算法来解决分布回归问题,同时证明该方法的稳定性和收敛速度,回答了 15 年来未解决的开放性问题,并涵盖了一系列相关的概率分布问题。
Feb, 2014