Private Streaming SCO in $\ell_p$ geometry with Applications in High Dimensional Online Decision Making

ICML 2022

TL;DR

This paper introduces a novel differentially private streaming algorithm for stochastic convex optimization (SCO) that achieves optimal excess risks across various $\ell_p$ geometries, including settings where previous methods failed. It tackles the challenge of privacy in sequential data processing, enabling applications like personalized bandit problems with strong privacy guarantees.

What Problem Does This Paper Address?

The paper tackles the problem of Differentially Private Stochastic Convex Optimization (DP-SCO), specifically in the context of streaming data and a continual release model. In streaming settings, data arrives sequentially and cannot be stored indefinitely, requiring algorithms to process and release information promptly. The continual release model means that parameters are updated and released after each new data point, posing a significant privacy challenge.

Existing DP-SCO algorithms often rely on batch processing or require large amounts of data, making them unsuitable for streaming scenarios. Furthermore, achieving optimal excess risks across different $\ell_p$ norms (which define the geometry of the optimization problem) has been a persistent challenge, especially when combining privacy with streaming and continual release requirements. The paper aims to bridge this gap by developing a DP-SCO algorithm that is both efficient for streaming data and achieves state-of-the-art or optimal privacy-preserving performance across various $\ell_p$ geometries.

Methods

The core of the paper's contribution lies in adapting the Frank-Wolfe (FW) algorithm for the DP-SCO streaming setting. Key methodological innovations include:

  • Recursive Gradient Variance Reduction: The authors generalize a recursive Frank-Wolfe algorithm for variance reduction. This technique is crucial for handling streaming data by efficiently updating gradient estimates without needing to store past data.
  • Tree-Based Mechanism for Privacy: To ensure differential privacy, they employ a tree-based aggregation protocol (similar to Guha Thakurta & Smith, 2013). This mechanism allows for the private release of partial sums of gradients, crucial for the recursive update.
  • Adaptive DP Analysis: The paper utilizes an adaptive DP analysis to show that a carefully chosen noise variance is sufficient to guarantee $(\epsilon, \delta)$-differential privacy, even with the sequential nature of data and parameter releases. This is a significant improvement over methods that might require accumulating noise.
  • Handling Different $\ell_p$ Geometries: The analysis is extended to various $\ell_p$ norms ($1 \le p < \infty$). This involves leveraging the properties of dual norms and specific regularity conditions for each $\ell_p$ space. For $p=1$, a specialized approach using the Report Noisy Max mechanism is employed to overcome the limitations of the tree-based method.
  • Application to Generalized Linear Bandits: The developed DP-SCO framework is applied to the problem of differentially private high-dimensional generalized linear bandits. This involves adapting the variance reduction techniques to handle the non-stationary nature of bandit problems, where the data distribution depends on past decisions.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data for experiments. The synthetic data is generated for a linear regression setting ($y = X^T\theta + \epsilon$) where $X \in \mathbb{R}^{d \times n}$ and $\theta \in \mathbb{R}^d$. The parameters are chosen to represent different $\ell_p$ geometries.

Key Insights and Ideas

  • Bridging the Gap for Streaming DP-SCO: The most significant insight is the development of a unified framework that achieves optimal or near-optimal DP-SCO rates in streaming settings across various $\ell_p$ norms, a feat not accomplished by prior work.
  • Recursive FW for Privacy: Adapting the Frank-Wolfe algorithm with recursive gradient updates and a tree-based privacy mechanism proves effective for sequential data processing while maintaining strong privacy guarantees.
  • $\ell_p$ Geometry Matters for Privacy: The paper highlights how the choice of $\ell_p$ norm significantly impacts the DP analysis and achievable rates, requiring tailored approaches for different geometries, especially for the challenging $p=1$ case.
  • Non-Stationarity in Bandits is Tractable: Extending DP-SCO to non-stationary environments like generalized linear bandits is shown to be feasible by carefully analyzing and bounding the variance introduced by the decision-making process.
  • Efficiency Gains: The proposed algorithm achieves optimal rates with linear time complexity and a reduced number of gradient queries compared to prior DP-SCO methods, making it more practical for high-dimensional streaming data.

Key Results

  • Optimal Excess Risk: The algorithm achieves the first optimal excess risk in linear time for $1 < p < 2$ and state-of-the-art excess risk for $2 < p < \infty$, matching non-private lower bounds.
  • Improved Gradient Queries: For $1 < p < 2$, the algorithm achieves optimal rates with $O(n)$ gradient queries, significantly outperforming previous methods requiring $O(n^{3/2})$ queries.
  • $p=1$ Case: For $p=1$, the algorithm achieves a nearly dimension-independent excess risk, overcoming the $\mathcal{O}(\sqrt{d})$ factor typically associated with tree-based mechanisms.
  • DP Generalized Linear Bandits: The paper presents the first regret bound for DP high-dimensional generalized linear bandits, achieving sublinear regret with poly-logarithmic dependence on dimension $d$.
  • Empirical Performance: Experiments show that the proposed algorithm outperforms NoisySFW and achieves comparable results to NoisySGD, with significantly better computational complexity.

Limitations and Future Work

  • $p=1$ Gap: While the algorithm achieves a good rate for $p=1$, there's a gap compared to the non-private setting, attributed to the inherent difficulty of the streaming setting and the lack of dataset shuffling for privacy amplification.
  • Regret Bound Refinement: The regret bound for the bandit problem has an extra $O(\log^2 T)$ factor compared to non-private methods, which the authors suggest could be refined in future work.
  • Lower Bound for $p=1$: Deriving the corresponding lower bound for the $p=1$ case in the strongly convex setting is left as future exploration.
  • Generalization to Non-linear Bandits: Extending the DP bandit framework to more general non-linear bandit settings is a potential future direction.

Summary updated

BibTeX
@inproceedings{2022private,
  title = {{Private Streaming SCO in $\textbackslash\{\}ell\_p$ geometry with Applications in High Dimensional Online Decision Making}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
}
Figure