转载自知乎专栏：FOLLOW THE REGULARIZED LEADER (FTRL) 算法总结
之前主要关注FTRL，没有仔细的看过FTRL之前的文章，这里简单记一下，以后翻出来看也方便。
FTRL是Google从2010到2013护的坑，从理论到工程实现，对处理如Logistic Regression之类的带非光滑正则项的凸优化问题上性能出色(L1范数，控制模型复杂度和稀疏化)。
Oblivious Transfer notes
Oblivious Transfer: 不经意传输
OT是混淆电路(GC)等许多MPC方案的的基石，一种基础的安全多方计算协议。
来看一个例子：假设某旅行社拥有N个景点的旅游资料，小淘想去其中的A景点游玩，希望向旅行社购买相关资料做好出游功课。但是小淘非常在意自己的隐私，不希望向旅行社泄露自己的目的地是哪里。因此双方希望这笔交易能够满足以下隐私条件：
- 小淘不希望向旅行社泄露“我准备去A景点”这一信息；
- 旅行社只希望出售小淘出钱购买的那份资料，而不泄露小淘未购买的N-1份资料；
粗看起来这种隐私条件似乎是无法满足的：旅行社只要把景点A的资料给到小淘，就必然了解了“小淘正在关注A景点”这一信息；除非旅行社把所有N份资料都给出，但是这又违背了旅行社的利益；
但是神奇的OT可以让交易在这种“不可能的条件”下达成。简而言之，在OT协议中，旅行社把他拥有的N份资料使用某种双方协商同意的加密算法和参数进行加密，然后发送给小淘；小淘可以从密文中解密出A的资料，而无法解密出其他N-1份资料。
SecureML 阅读
Mohassel P, Zhang Y. Secureml: A system for scalable privacy-preserving machine learning[C]//2017 IEEE Symposium on Security and Privacy (SP). IEEE, 2017: 19-38.
Abstract
本论文在特定计算场景下实现了安全多方计算的优化。针对线性回归、逻辑回归、神经网络训练问题，本论文给出了优化方案，并通过理论证明和实际验证说明了方案的可行性。
在两个不会合作的server模型上实现的协议。
Our protocols fall in the two-server model where data owners distribute their private data among two non-colluding servers who train various models on the joint data using secure two-party computation. We develop new techniques to support secure arithmetic operations on shared decimal numbers, and propose MPC-friendly alternatives to non-linear functions such as sigmoid and softmax that are superior to prior work.
Differentially Private Contextual Linear Bandits notes
Shariff R, Sheffet O. Differentially Private Contextual Linear Bandits[C]//Advances in Neural Information Processing Systems. 2018: 4296-4306.
Abstract
We first show that using the standard definition of differential privacy results in linear regret. So instead, we adopt the notion of joint differential privacy, where we assume that the action chosen on day t is only revealed to user t and thus needn’t be kept private that day, only on following days. We give a general scheme converting the classic linear-UCB algorithm into a joint differentially private algorithm using the tree-based algorithm. We then apply either Gaussian noise or Wishart noise to achieve joint-differentially private algorithms and bound the resulting algorithms’ regrets. In addition, we give the first lower bound on the additional regret any private algorithms for the MAB problem must incur.
用标准的DP可以得到线性的regret bound。因此采用了联合DP(joint differential privacy)，假设第t天选择的action只有用户t知道，所以不需要在当天进行保护，只需要保护接下来的日子。
用基于树的算法将linUCB算法转化为符合JDP的算法。加入了高斯噪声或者Wishart噪声。