Privacy-Preserving Frank-Wolfe on Shuffle Model  

作　　者：Ling-jie ZHANG Shi-song WU Hai ZHANG 

机构地区：[1]School of Mathematics,Northwest University,Xi’an 710127,China [2]School of Mathematics and Information Science,Baoji University of Arts and Sciences,Baoji 721013,China [3]China Southern Power Grid Artificial Intelligence Technology Company Limited,Guangzhou 510700,China

出　　处：《Acta Mathematicae Applicatae Sinica》2024年第4期887-907,共21页应用数学学报（英文版）

基　　金：supported by the National Natural Science Foundation of China(No.U1811461,12326615)。

摘　　要：In this paper,we design the differentially private variants of the classical Frank-Wolfe algorithm with shuffle model in the optimization of machine learning.Under weak assumptions and the generalized linear loss(GLL)structure,we propose a noisy Frank-Wolfe with shuffle model algorithm(NoisyFWS)and a noisy variance-reduced Frank-Wolfe with the shuffle model algorithm(NoisyVRFWS)by adding calibrated laplace noise under shuffling scheme in thel_(p)(p∈[1,2])-case,and study their privacy as well as utility guarantees for the H?lder smoothness GLL.In particular,the privacy guarantees are mainly achieved by using advanced composition and privacy amplification by shuffling.The utility bounds of the Noisy FWS and NoisyVRFWS are analyzed and obtained the optimal excess population risksO(n-(1+α/4α+log(d)√log(1/δ)/n∈and O(n-1+α/4α+log(d)√log1(+δ)/n^(2)∈with gradient complexity O(n(1+α)^(2)/4α^(2)forα∈[1/√3,1].It turns out that the risk rates under shuffling scheme are a nearly-dimension independent rate,which is consistent with the previous work in some cases.In addition,there is a vital tradeoff between(α,L)-Holder smoothness GLL and the gradient complexity.The linear gradient complexity O(n)is showed by the parameterα=1.

关 键 词：differential privacy Frank-Wolfe algorithm privacy amplification shuffle model 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程] TP309[自动化与计算机技术—控制科学与工程]