Lin X, Zhang W, Zhang M, et al. Online compact convexified factorization machine[C]//Proceedings of the 2018 World Wide Web Conference. 2018: 1633-1642.

Factorization Machine不能直接用于online learning的场景。最初的挑战是，没有任何先前的FM公式可以直接满足在线凸优化（OCO）的要求（OCO是在线学习算法设计的最重要框架）。为此，本文提出了一种新的凸化方案，该方案导致了紧凑型凸面FM（Compact Convexified FM），可以无缝满足OCO的要求。

但是在在线学习的场景下，绝大部分现有的算法需要承受昂贵的映射操作。因此，本文遵循在线条件梯度（Online Conditional Gradient）的通用的免投影算法框架，并提出了一种在线紧凑型凸因子分解机（OCCFM）算法，该算法通过有效的线性优化步骤来避免投影操作。

同时，给出了OCCFM的理论bound，可以达到次线性。

在6个真实数据集上进行了在线分类和在线回归的实验对比，结果比online FM强。

Sesh Kumar K S, Deisenroth M P. Differentially Private Empirical Risk Minimization with Sparsity-Inducing Norms[J]. arXiv preprint arXiv:1905.04873, 2019.

本文考虑DPERM with regularizers thath induce structured sparsity。这些正则项是凸的，但常常不可微。本文分析了标准的DP算法，比如输出扰动(output perturbation)，Frank-Wolfe和目标扰动(objective perturbation)。

输出扰动在强凸的条件下表现较好。之前的工作导出的risk bound不依赖于维度。这篇文章我们假设一类特殊的凸但不平滑的正则项为广义线性模型引入结构化的稀疏性和损失函数。

同样考虑了用DP-FW算法来优化risk minimization问题的对偶。给出了这些算法的risk bounds。bounds依赖于对偶范数的单位球的高斯宽度。

还表明了目标扰动和对偶优化问题的输出扰动是等价的。

是第一个考虑DP下ERM的对偶优化问题的工作。

Talwar K, Thakurta A G, Zhang L. Nearly optimal private lasso[C]//Advances in Neural Information Processing Systems. 2015: 3025-3033.

提出DP-LASSO。可以保护每个训练样本。假设训练样本是$l_{\infin}$范数的，与non-private版本的算法相比，本文提出算法的excess risk可以达到$\tilde{O}(\frac{1}{n^{2/3}})$。在不对design matrix做任何假设的情况下，首次得到不多项式依赖于p的bound。同时表明，在所有DP算法中，该误差范围几乎是最佳的。

Wang D, Chen C, Xu J. Differentially private empirical risk minimization with non-convex loss functions[C]//International Conference on Machine Learning. 2019: 6526-6535.

本文研究了DP-ERM with (smooth) non-convex loss function问题。我们首先研究预期的过量经验（或总体）风险，该风险主要用作衡量凸损失函数质量的工具。

We first study the expected excess empirical (or population) risk, which was primarily used as the utility to measure the quality for convex loss functions.

在$(\epsilon,\delta)$-DP中，上述risk的上界是$\tilde{O}(\frac{d \log(1/\delta)}{\log n\epsilon^2})$，n是数据总数，d是空间的维度。通过对时间平均误差的高度平凡的分析，$\frac{1}{\log n}$项可以进一步提高到$\frac{1}{n^{\Omega(1)}}$（当d维常数的时候）。

为了得到更有效的解决方案，考虑了DP和近似local最小值的联系。特别地，当n足够大时，存在$(\epsilon,\delta)$-DP算法，可以在约束和非约束条件下大概率找到经验风险的近似局部最小值。

Chaudhuri K, Monteleoni C, Sarwate A D. Differentially private empirical risk minimization[J]. Journal of Machine Learning Research, 2011, 12(Mar): 1069-1109.

这篇是Chaudhuri大佬08年nips那篇的扩展期刊版本，介绍输出扰动和目标扰动两种方法。当损失函数和正则项满足一定的凸和可微条件时，理论上证明了可以保护隐私，并且为linear and nonlinear kernals提供了通用的bounds。接下来提出一种保护隐私的调参方法。

Biswas C, Ganguly D, Roy D, et al. Privacy Preserving Approximate K-means Clustering[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management. 2019: 1321-1330.

CIKM 19

Abstract

保护隐私的计算在云计算环境中十分重要，因为客户端需要上传数据到不可信的网络中，网络如果被窃听或者服务器上的恶意软件都会造成信息的泄露。为了防止这种事情，本文提出把输入数据编码以达到两个要求：编码后的数据很难被解码回去；计算结果要和使用原始数据的差别不大。本文针对的K-means聚类算法在数据挖掘中很常用，提出的方案将只需要二进制编码数据，不允许在计算的其他阶段有任何介入。在计算的中间阶段，可以有效的处理具有不完整信息的输入，以寻求产生相对接近于完整信息（未编码）的输出。 实验结果表明在图像聚类(MNIST-8M dataset)上可以达到与标准K-means差不多的效果，在文本聚类(ODPtweets dataset)上比标准K-means还好。