算法稳定性驱动的机器学习去加工化
机器遗忘问题中设计高效算法的形式化,包括线性和前缀和查询类的高效遗忘算法以及其在随机凸优化问题和广义线性模型中的应用,提供了不同情况下的遗忘风险和查询复杂度。
Jul, 2023
将 “被遗忘的权利” 作为用户数据隐私的法律保证变得日益重要。机器遗忘旨在高效地从训练模型参数中去除特定数据点的影响,以便与从头开始重新训练模型时近似相同。本文提出了基于噪声随机梯度下降(SGD)的随机梯度 Langevin 遗忘框架,为凸性假设下的近似遗忘问题提供了带有隐私保证的第一个遗忘方法。我们的研究结果表明,与全批次更新相比,小批次梯度更新提供了更好的隐私 - 复杂性权衡。我们的遗忘方法具有许多算法上的优势,包括与重新训练相比的复杂性节省,以及支持顺序和批次遗忘。为了研究我们方法的隐私 - 效用 - 复杂性权衡,我们在基准数据集上进行了实验,与之前的工作进行了比较。相比于小批次和全批次设置下基于梯度的近似遗忘方法,我们的方法在相同隐私限制条件下使用了 2% 和 10% 的梯度计算,同时达到了类似的效用。
Mar, 2024
本文通过建立黑盒稳定性结果,仅依赖于学习算法的收敛和损失函数最小值周围的几何形态,为收敛到全局最小值的学习算法建立新的泛化界限,适用于满足 Polyak-Lojasiewicz(PL)和二次增长(QG)条件的非凸损失函数以及一些具有线性激活的神经网络,并使用黑盒结果来证明 SGD、GD、RCD 和 SVRG 等优化算法的稳定性在 PL 和强凸设置中具有可拓展性,同时指出存在简单的具有多个局部最小值的神经网络,在 PL 设置下 SGD 稳定,但 GD 不稳定。
Oct, 2017
基于噪声梯度下降的兰格文反训练为近似反训练问题提供隐私保证,将 DP 学习过程与隐私认证的反训练过程统一,具有多种算法优势,包括非凸问题的近似认证的反训练、与重新训练相比的复杂性节约、用于多个反训练请求的顺序和批量反训练。通过在基准数据集上进行实验验证了兰格文反训练的实用性和隐私 - 效用 - 复杂性的权衡,并展示了其相对于基于梯度下降加输出扰动的近似反训练的优越性。
Jan, 2024
探讨了算法稳定性作为分析学习算法泛化误差的可行框架的概念。引入了学习算法训练稳定性的新概念,并证明在一般情况下它足以得到泛化误差的好界。在 PAC 设置中,训练稳定性在可学习性上既是必要的也是充分的。基于训练稳定性的方法不涉及 VC 维或 VC 熵,不需要证明一致收敛,而广义 McDiarmid 不等式可直接限制泛化误差。因此,它可能使我们处理比经验风险最小化更广泛的学习算法类。还探讨了 VC 维、泛化误差和各种稳定性概念之间的关系,并考虑了几个学习算法的例子。
Dec, 2012
本文研究了在已训练好的模型中删除数据点的相关问题,特别是在凸损失的情况下提供了一个算法来取消学习的样本数,与差分隐私学习相比,演示了差分隐私和机器遗忘之间的新颖区别。
Mar, 2021
本文研究如何通过减少 verification error 和限制权重变化来实现近似机器遗忘,特别是在深度学习模型训练中使用随机梯度下降算法(SGD),以此来提高模型的整体性能。
Sep, 2021
本文讨论如何通过总变差(TV)距离度量学习规则的输出相似性,提出了 TV 不可辨认性的信息论等价性和统计学放大以及提升算法,并研究了基于 TV 不可辨认性的假设类可学习性。
May, 2023
本文提出了一种新的稳定对抗学习(SAL)算法,该算法利用异质数据源构建了更实用的不确定性集,并根据协变量与目标的稳定性进行差异化的鲁棒性优化,理论上表明我们的方法适用于随机梯度下降优化,并为我们的方法提供了性能保证。在模拟和实际数据集上的实证研究验证了我们的方法在未知分布转移方面的均匀优秀性能。
Jun, 2021
大规模机器学习问题中,通过松散提示参数信息,提出了能够自动调整的 “无需调参” 的算法,能够与最优调参优化算法在多对数因子上实现性能匹配,特别是对于有界优化领域,证明了这种匹配是可能的,并且多个现有算法已经实现了该特性。然而,在无界领域中,证明了无需调参优化是不可能的,但在噪声分布足够良好的情况下,通过一些算法如 DoG 和 DoWG,可以满足无需调参的条件。对于查找光滑且可能非凸函数的稳定点,提出了一种改进的随机梯度下降(SGD)变体,以仅有多对数成本匹配调参 SGD 的最佳已知高概率收敛率,然而,也证明了任何算法都不可能满足与调参 SGD 高概率收敛率相匹配的最优期望收敛率。
Feb, 2024