Document in text mode:

TightonBudget?TightBoundsforr-FoldApproximateDifferentialPrivacySebastianMeiser1,EsfandiarMohammadi21UniversityCollegeLondon,UnitedKingdom,e-mail:[email protected],Switzerland,e-mail:[email protected]sequallycontributedtothiswork.September5,2018AbstractManyapplications,suchasanonymouscommunicationsystems,privacy-enhancingdatabasequeries,orprivacy-enhancingmachine-learningmethods,requirerobustguaranteesunderthousandsandsome-timesmillionsofobservations.Thenotionofr-foldapproximatedifferentialprivacy(ADP)offersawell-establishedframeworkwithaprecisecharacterizationofthedegreeofprivacyafterrobservationsofanattacker.However,existingboundsforr-foldADParelooseand,ifusedforestimatingtherequireddegreeofnoiseforanapplication,canleadtoover-cautiouschoicesforperturbationrandomnessandthustosuboptimalutilityoroverlyhighcosts.Wepresentanumericalandwidelyapplicablemethodforcapturingtheprivacylossofdifferentiallyprivatemechanismsundercomposition,whic...