Learner-Private Convex Optimization
- 5 September 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 69 (1) , 528-547
Abstract
Convex optimization with feedback is a framework where a learner relies on iterative queries and feedback to arrive at the minimizer of a convex function. It has gained considerable popularity thanks to its scalability in large-scale optimization and machine learning. The repeated interactions, however, expose the learner to privacy risks from eavesdropping adversaries that observe the submitted queries. In this paper, we study how to optimally obfuscate the learner’s queries in convex optimization with first-order feedback, so that their learned optimal value is provably difficult to estimate for an eavesdropping adversary. We consider two formulations of learner privacy: a Bayesian formulation in which the convex function is drawn randomly, and a maximin formulation in which the function is fixed and the adversary’s probability of error is measured with respect to a minimax criterion. Suppose that the learner wishes to ensure the adversary cannot estimate accurately with probability greater than 1/ L for some L > 0. Our main results show that the query complexity overhead is additive in L in the maximin formulation, but multiplicative in L in the Bayesian formulation. Compared to existing learner-private sequential learning models with binary feedback, our results apply to the significantly richer family of general convex functions with full-gradient feedback. Our proofs rely on tools from the theory of Dirichlet processes, as well as a novel strategy designed for measuring information leakage under a full-gradient oracle.Keywords
All Related Versions
Funding Information
- NSF (IIS-1838124, CCF-1850743, CCF-1856424)
- NSF CAREER Award (CCF-2144593)
This publication has 32 references indexed in Scilit:
- Stochastic Convex Optimization with Bandit FeedbackSIAM Journal on Optimization, 2013
- Separable Convex Optimization Problems with Linear Ascending ConstraintsSIAM Journal on Optimization, 2010
- Bayesian Nonparametric Estimation of Continuous Monotone Functions with Applications to Dose–Response AnalysisBiometrics, 2009
- Differential Privacy: A Survey of Results2008
- Bayesian Isotonic Regression and Trend AnalysisBiometrics, 2004
- Private information retrieval2002
- On some inequalities for the gamma and psi functionsMathematics of Computation, 1997
- A nonparametric Bayes method for isotonic regressionJournal of Statistical Planning and Inference, 1995
- Nonparametric Bayesian bioassay with prior constraints on the shape of the potency curveBiometrika, 1993
- On hiding information from an oracleJournal of Computer and System Sciences, 1989