Privacy-Preserving Frank-Wolfe on Shuffle Model

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.