  Online convex optimization is a framework where a learner sequentially
queries an external data source in order to arrive at the optimal solution of a
convex function. The paradigm has gained significant popularity recently thanks
to its scalability in large-scale optimization and machine learning. The
repeated interactions, however, expose the learner to privacy risks from
eavesdropping adversary that observe the submitted queries. In this paper, we
study how to optimally obfuscate the learner's queries in first-order online
convex optimization, so that their learned optimal value is provably difficult
to estimate for the eavesdropping adversary. We consider two formulations of
learner privacy: a Bayesian formulation in which the convex function is drawn
randomly, and a minimax formulation in which the function is fixed and the
adversary's probability of error is measured with respect to a minimax
criterion. We show that, if the learner wants to ensure the probability of
accurate prediction by the adversary be kept below $1/L$, then the overhead in
query complexity is additive in $L$ in the minimax 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 are largely enabled by tools from the theory
of Dirichlet processes, as well as more sophisticated lines of analysis aimed
at measuring the amount of information leakage under a full-gradient oracle.
