Privacy-Preserving Prediction Techniques in Machine Learning
Explore privacy-preserving prediction methods in machine learning, including differential privacy, trade-offs in linear regression, black-box attacks, label aggregation, and classification via aggregation. Understand the importance of prediction accuracy and privacy trade-offs, differentially private learning algorithms, and stability in predictions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Privacy-preserving Prediction Vitaly Feldman Brain with Cynthia Dwork
Privacy-preserving learning Input: dataset ? = (?1,?1), ,(??,??) Goal: given ? predict ? ? Model Differentially private learning algorithm ? ?(?) ?(? ) 2
Trade-offs Linear regression in ? ? ? more data With ?-DP needs factor [Bassily,Smith,Thakurta 14] Learning a linear classifier over {0,1}? ? ? more data Needs factor [Feldman,Xiao 13] MNIST accuracy ??% with small ?,? vs 99.8% without privacy [AbadiCGMMTZ 16] 3
Prediction Users need predictions not models ?1 ? ?2 ?2 ?2 ? ?? ?? Prediction API Users DP Fits many existing systems 4
Attacks Black-box membership inference with high accuracy [Shokri,Stronati,Song,Shmatikov 17; LongBWBWTGC 18; SalemZFHB 18] 5
Learning with DP prediction Accuracy-privacy trade-off Single prediction query Differentially private prediction : ?: ? ?? ? ? is ?-DP prediction algorithm if for every ? ?, ?(?,?) is ?-DP private w.r.t. ? 6
Label aggregation [HCB 16; PAEGT 17; PSMRTE 18; BTT 18] ? ?1 ?2 ?3 ?? ? = ?? (non-DP) learning algo ? ? ? ? ? ? ? ? 2 ? 1 1 2 ? 3 ?(?) ? 1(?) 2(?) ? ? 2(?) 1(?) 3(?) Differentially private aggregation ? e.g. exponential mechanism ? ?? | ? ?? =?}|/2 7
Classification via aggregation PAC model: Let ? be a class of function over ? For all distributions ? over ? {0,1} output such that w.h.p. ?? (?,?) ? ? ? Opt?? + ? ?-DP prediction ?-DP model Non-private VCdim ? ? VCdim ? ?? Rdim ? ?? ? Realizable case: Rdim ? ?? 1/3 + VCdim ? ?? VCdim ? ? ? Agnostic: Representation dimension [Beimel,Nissim,Stemmer 13] VCdim ? Rdim ? VCdim ? log|?|[KLNRS 08] For many classes Rdim ? = (VCdim ? log ? )[F.,Xiao 13] 8
Prediction stability la [Bousquet,Elisseeff 02]: ?: ? ?? ? is uniformly ?-stable algorithm if for every, neighboring ?,? and ? ?, ? ?,? ? ? ,? ? Convex regression: given ? = ? ?,? For ? over ? ?, minimize: ? ? ?? = (?,?) ?[ (? ?,? ,?)] ? over convex ? ?, where (? ?,? ,?) is convex in ? for all ?,? Convex 1-Lipschitz regression over 2 ball of radius 1: ?-DP prediction ?-DP model Non-private 1 1 ?? 1 ?+? Excess loss: ? ?? ? 9
Beyond aggregation Threshold functions on a line 1 ? Excess error for agnostic learning ?-DP prediction ?-DP model Non-private 1 1 1 1 ?+log? ?+ ?? ? ?? 10
Conclusions Natural setting for learning with privacy Better accuracy-privacy trade-off Paper (COLT 2018): https://arxiv.org/abs/1803.10266 Open problems: o General agnostic learning o Other general approaches o Handling of multiple queries [BTT 18] 11
