# Learner-Private Convex Optimization

arXiv: https://arxiv.org/abs/2102.11976 · HTML: https://mlsanity.com/paper/2102.11976/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 60 references that are in the map.
- First posted on arXiv 23 Feb 2021.

## Builds on (most cited first, 19 of 19)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Exploiting Unintended Feature Leakage in Collaborative Learning](https://mlsanity.com/paper/1805.04049/) (2018)
- [Threats to Federated Learning: A Survey](https://mlsanity.com/paper/2003.02133/) (2020)
- [PRADA: Protecting against DNN Model Stealing Attacks](https://mlsanity.com/paper/1805.02628/) (2018)
- [cpSGD: Communication-efficient and differentially-private distributed SGD](https://mlsanity.com/paper/1805.10559/) (2018)
- [LDP-Fed: Federated Learning with Local Differential Privacy](https://mlsanity.com/paper/2006.03637/) (2020)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates](https://mlsanity.com/paper/1302.3203/) (2013)
- [Regression Equilibrium](https://mlsanity.com/paper/1905.02576/) (2019)
- [Improving Generalization of Reinforcement Learning with Minimax Distributional Soft Actor-Critic](https://mlsanity.com/paper/2002.05502/) (2020)
- [Competing Bandits: The Perils of Exploration Under Competition](https://mlsanity.com/paper/2007.10144/) (2020)
- [Competing Bandits: Learning under Competition](https://mlsanity.com/paper/1702.08533/) (2017)
- [Private Sequential Learning](https://mlsanity.com/paper/1805.02136/) (2018)
- [Private Function Retrieval](https://mlsanity.com/paper/1711.04677/) (2017)
- [Query Complexity of Bayesian Private Learning](https://mlsanity.com/paper/1911.06903/) (2019)
- [Infection Spreading and Source Identification: A Hide and Seek Game](https://mlsanity.com/paper/1504.04796/) (2015)
- [Anonymous Stochastic Routing](https://mlsanity.com/paper/1911.08875/) (2019)

## Built on by (most cited first, 2 of 2)

- [Controlling Federated Learning for Covertness](https://mlsanity.com/paper/2308.08825/) (2023)
- [Structured Reinforcement Learning for Incentivized Stochastic Covert Optimization](https://mlsanity.com/paper/2405.07415/) (2024)

## Abstract (arXiv)

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 minimax 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 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 learn on tools from the theory of Dirichlet processes, as well as a novel strategy designed for measuring information leakage under a full-gradient oracle.