# On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 55 references that are in the map.
- First posted on arXiv 16 Jun 2022.

## Builds on (most cited first, 30 of 31)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Online Learning: A Comprehensive Survey](https://mlsanity.com/paper/1802.02871/) (2018)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning](https://mlsanity.com/paper/1503.04269/) (2015)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2010.11082/) (2020)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Provably Optimal Algorithms for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/1703.00048/) (2017)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling](https://mlsanity.com/paper/2006.04012/) (2020)
- [Generalized Linear Bandits with Local Differential Privacy](https://mlsanity.com/paper/2106.03365/) (2021)
- [Privacy-Preserving Dynamic Personalized Pricing with Demand Learning](https://mlsanity.com/paper/2009.12920/) (2020)
- [Efficient Projection-Free Online Methods with Stochastic Recursive Gradient](https://mlsanity.com/paper/1910.09396/) (2019)
- [Differential Privacy in Personalized Pricing with Nonparametric Demand Models](https://mlsanity.com/paper/2109.04615/) (2021)
- [On the Online Frank-Wolfe Algorithms for Convex and Non-convex Optimizations](https://mlsanity.com/paper/1510.01171/) (2015)

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

- [Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisited](https://mlsanity.com/paper/2303.18047/) (2023)

## Abstract (arXiv)

Differentially private (DP) stochastic convex optimization (SCO) is ubiquitous in trustworthy machine learning algorithm design. This paper studies the DP-SCO problem with streaming data sampled from a distribution and arrives sequentially. We also consider the continual release model where parameters related to private information are updated and released upon each new data, often known as the online algorithms. Despite that numerous algorithms have been developed to achieve the optimal excess risks in different ℓp norm geometries, yet none of the existing ones can be adapted to the streaming and continual release setting. To address such a challenge as the online convex optimization with privacy protection, we propose a private variant of online Frank-Wolfe algorithm with recursive gradients for variance reduction to update and reveal the parameters upon each data. Combined with the adaptive differential privacy analysis, our online algorithm achieves in linear time the optimal excess risk when 1<p≤ 2 and the state-of-the-art excess risk meeting the non-private lower ones when 2<p≤∞. Our algorithm can also be extended to the case p=1 to achieve nearly dimension-independent excess risk. While previous variance reduction results on recursive gradient have theoretical guarantee only in the independent and identically distributed sample setting, we establish such a guarantee in a non-stationary setting. To demonstrate the virtues of our method, we design the first DP algorithm for high-dimensional generalized linear bandits with logarithmic regret. Comparative experiments with a variety of DP-SCO and DP-Bandit algorithms exhibit the efficacy and utility of the proposed algorithms.