Differentially Private Online Submodular Maximization

Ensuring users’ privacy has become a critical task in online learning algorithms. As an illustrative example, sponsored search engines aim to maximize the probability that displayed ads or products are clicked by incoming customers, but prospective customers do not want their privacy infringed after clicking on a product. Users visiting online retailer web-pages such as Amazon, Walmart or Target leave behind an abundance of sensitive personal information that can be use to predict their behaviors or preferences, potentially leading to catastrophic results (Zhang et al.,, 2014)³³3See also https://www.nytimes.com/2012/02/19/magazine/shopping-habits.html. In this work, we introduce the first algorithms for privacy-preserving online monotone submodular maximization under a cardinality constraint.

A submodular set function $f:2^{U}\to\mathbb{R}$ exhibits diminishing returns, meaning that adding an element $x$ to a larger set $B$ creates less additional value than adding $x$ any subset of $B$. (See Definition 1 in Section 2 for a formal definition.) Submodular functions have found widespread application in economics, computer science and operations research (see, e.g., Bach, (2013) and Krause and Golovin, (2014)), and have recently gained attention as a modeling tool for data summarization and ad display (Ahmed et al.,, 2012; Streeter et al.,, 2009; Badanidiyuru et al.,, 2014). We additionally consider monotone submodular functions, where adding elements to a set can only increase the value of $f$. Since unconstrained monotone submodular maximization is trivial—$f(S)$ can be maximized by choosing the entire universe $S=U$—we consider cardinality constrained maximization, where the decision-maker solves: $\max_{S\subseteq U}f(S)\text{ s.t. }|S|\leq k$.

In the online learning setting, at each time-step $t$ a learner must choose a set $S_{t}\subseteq U$ of size at most $k$ and receives payoff $f_{t}(S_{t})$ for a monotone submodular function $f_{t}$. Importantly, the learner does not know $f_{t}$ before she chooses $S_{t}$, but this set can be chosen based on previous functions $f_{1},\ldots,f_{t-1}$. Two types of informational feedback are commonly studied in the online learning literature. In the full-information setting, the learner gets full oracle access to the function $f_{t}$ after choosing $S_{t}$, and thus is able to incorporate the entirety of previous functions into her future decisions. In the bandit setting, the learner only observes her own payoff $f_{t}(S_{t})$ as feedback.

Performance of an online learner is typically measured by the regret, which is the difference between the best fixed decision in hindsight and the cumulative payoff obtained by the learner (Zinkevich,, 2003; Hazan,, 2016; Shalev-Shwartz,, 2012). More precisely, the regret of a learner after $T$ rounds is: $\max_{|S|\leq k}\sum_{t=1}^{T}f_{t}(S)-\sum_{t=1}^{T}f_{t}(S_{t})$. The aim often is to design algorithms with sublinear regret, i.e., $o(T)$, so that the average payoff over time of the algorithm is comparable with the best average fixed profit in hindsight. Offline monotone submodular maximization under a cardinality constraint is NP-hard to approximate with a factor better than $(1-1/e)$ (Feige,, 1998; Mirrokni et al.,, 2008), so we instead measure the quality of our algorithms using the more restrictive notion of $(1-1/e)$-regret (Streeter and Golovin,, 2009; Streeter et al.,, 2009):

The privacy notion we consider in this work is differential privacy (Dwork et al.,, 2006), which enables accurate estimation of population-level statistics while ensuring little can be learned about the individuals in the database. Informally, a randomized algorithm is said to be differentially private if changing a single entry in the input database results in only a small distributional change in the outputs. (See Definition 2 in Section 2 for a formal definition.) This means that an adversary cannot information-theoretically infer whether or not a single individual participated in the database. Differentially private algorithms have been deployed by major organizations including Apple, Google, Microsoft, Uber, and the U.S. Census Bureau, and are seen as the gold standard in privacy-preserving data analysis. In this work, the input database to our learning algorithm consists of a stream of functions $F=\{f_{1},\ldots,f_{T}\}$, and each individual’s data corresponds to a function $f_{t}$. Our privacy guarantees ensure that the stream of chosen sets $S_{1},\ldots,S_{T}$ are differentially private with respect to this database of functions,

In both the full-information and bandit settings, we present differentially private online learning algorithms that achieve sublinear expected $(1-1/e)$-regret.

In this section we review definitions and properties of submodular functions and differential privacy.

As is standard in the submodular maximization literature, we assume $f(\emptyset)=0$. In our motivating example, this means that if no items are shown to the incoming customer, then the probability of selecting an item is $0$. We let $\mathcal{F}$ denote the family of submodular functions with finite ground set $U$. For the sake of simplicity, we will additionally assume that all functions take value in the interval $[0,1]$. In this work, we additionally consider set functions $f$ that are monotone or non-decreasing, i.e., $f(A)\leq f(B)$ for all $A\subseteq B$.

In the problem of online monotone submodular maximization under a cardinality constraint, a sequence of $T$ monotone submodular functions $f_{1},\ldots,f_{T}:2^{U}\to[0,1]$ arrive in an online fashion. At every time-step $t$, the decision maker $\mathcal{A}$ has to choose a subset $S_{t}\subseteq U$ of size at most $k$ before observing $f_{t}$. This decision must be based solely on previous observations. The decision maker $\mathcal{A}$ receives a payoff $f_{t}(S_{t})$ and her goal is to minimize the $(1-1/e)$-expected-regret $\operatorname{\mathbb{E}}[\operatorname{\mathcal{R}}_{T}]$, where $\operatorname{\mathcal{R}}_{T}=\left(1-\frac{1}{e}\right)\max_{|S|\leq k}\sum_{t=1}^{T}f_{t}(S)-\sum_{t=1}^{T}f_{t}(S_{t})$ as defined in Equation (1), and the randomness is over the algorithm’s choices.

A fundamental tool in our analysis is the Hedge algorithm (Algorithm 1) of Freund and Schapire, (1997) which chooses an action from a set $[N]=\{1,\ldots,N\}$ based on past payoffs from each action. The algorithm takes as input a learning rate $\eta$ and a stream of linear functions $g_{1},\ldots,g_{T}:[N]\to[0,1]$, where the payoff of playing action $i$ at time $t$ is $g_{t}(i)$.

In our setting, the learner must select a set of at most $k$ items from the ground set $U$. The learner does this by implementing $k$ ordered copies of the Hedge algorithm, each of which choses one item, so the action space for each instantiation is the ground set: $N=U$. The $i$-th copy of Hedge learns the item with the best marginal gain given the decisions made by the previous $i-1$ Hedge algorithms.

The Hedge algorithm exhibits the following guarantee, which is useful for analyzing its regret, as well as the regret of our algorithms which instantiate Hedge.

For the privacy considerations of this work, we view the input database as the ordered input sequence of submodular functions $F=\{f_{1},\ldots,f_{T}\}$ and the algorithm’s output as the sequence of chosen sets $S_{1},\ldots,S_{T}$. We say that two sequences $F,F^{\prime}$ of functions are neighboring if $f_{t}\neq f_{t}^{\prime}$ for at most one $t\in[T]$.

Differential privacy is robust to post-processing, meaning that any function of a differentially private output maintains the same privacy guarantee.

Differentially private algorithms also compose, and the privacy guarantees degrade gracefully as addition DP computations are performed. This enables modular algorithm design using simple differentially private building blocks. Basic Composition (Dwork et al.,, 2006) says that can simply add up the privacy parameters used in an algorithm’s subroutines to get the overall privacy guarantee. The following Advanced Composition theorem provides even tighter bounds.

Our algorithms rely on the Exponential Mechanism (EM) introduced by McSherry and Talwar, (2007). The EM takes in database $F$, a finite action set $U$, and a quality score $q:\mathcal{F}^{T}\times U\to\mathbb{R}$, where $q(F,i)$ assigns a numeric score to the quality of outputting $i$ on input database $F$. The sensitivity of the quality score, denoted $\Delta q$, is the maximum change in the value of $q$ across neighboring databases: $\Delta q=\max_{i\in U}\max_{F,F^{\prime}\;neighbors}|q(F,i)-q(F^{\prime},i)|$. Given these inputs, the EM outputs $i\in U$ with probability proportional to $\exp(\varepsilon\frac{q(F,i)}{2\Delta q})$. The Exponential Mechanism is $(\varepsilon,0)$-DP (McSherry and Talwar,, 2007).

As noted by Jain et al., (2012) and Dwork et al., 2010a , the Hedge algorithm can be converted into a DP algorithm using advanced composition and EM.

In this section, we introduce our first algorithm for online submodular maximization under cardinality constraint. It is both differentially private and achieves the best known expected $(1-1/e)$-regret in $T$. For cardinality $k$, the learner implements $k$ ordered copies of the Hedge algorithm. Each copy is in charge of learning the marginal gain that complements the choices of the previous Hedge algorithms. At time-step $t$, each Hedge algorithm selects an element $a\in U$ and the learner gathers these choices to play the corresponding set. When she obtains oracle access to the submodular function, for each $i\in[k]$, she constructs a vector $g_{t}^{i}$ with $a$-th coordinate given by the marginal gain of adding $a\in U$ to the choices made by the previous $i-1$ Hedge algorithms. Finally, she feeds back the vector $g_{t}^{i}$ to Hedge algorithm $i$. A formal description of this procedure is presented in Algorithm 2.

To ensure differential privacy, it would be enough to show that each Hedge $\mathcal{E}_{i}$ is $(\varepsilon/k,\delta/k)$-DP. Indeed, if the sequence $(a_{1}^{i},\ldots,a_{T}^{i})$ constructed by each Hedge algorithm $i$ is $(\varepsilon/k,\delta/k)$-DP, then by Basic Composition and post-processing, the sequence $(S_{1},\ldots,S_{T})$ is $(\varepsilon,\delta)$-DP, where $S_{t}=\{a_{t}^{i}\}_{i=1}^{k}$. However, for $i\geq 2$, the output of expert $\mathcal{E}_{i}$ depends on the choices made by algorithms $\mathcal{E}_{1},\ldots,\mathcal{E}_{i-1}$. Moreover, algorithm $\mathcal{E}_{i}$ by itself is again accessing the database $F$, hence ruling out a post-processing argument. Despite this, we show that all experts together are $(\varepsilon,\delta)$-DP even though individually we cannot ensure they preserve $(\varepsilon/k,\delta/k)$-DP.

It is worth noting that the Hedge algorithms $\mathcal{E}_{1},\ldots,\mathcal{E}_{k}$ in Algorithm 2 can be replaced by any other no-regret DP method that selects items over $U$, and the same proof structure would follow—although the regret bound would depend on the choice of no-regret algorithm. For instance, if we utilize the private experts method of(Thakurta and Smith,, 2013) instead of the Hedge algorithm, Algorithm 2 would be $(\varepsilon,0)$-DP with a regret bound of $\mathcal{O}\left(k^{2}\frac{\sqrt{|U|T\log^{2.5}T}}{\varepsilon}\right)$.

In the bandit case, the algorithm only receives as feedback the value $f_{t}(S_{t})$. Given this restricted information, the algorithm must trade-off exploration of the function with exploiting current knowledge. As in (Streeter and Golovin,, 2009), our algorithm controls this tradeoff using a parameter $\gamma\in[0,1]$, and by randomly exploring in each time-step independently with probability $\gamma$.

The non-private approach of Streeter and Golovin, (2009) obtains $\mathcal{O}(T^{2/3})$ expected $(1-1/e)$-regret, and works as follows: In exploit rounds (prob. $1-\gamma$), play the experts’ sampled choice $S_{t}$ and feed back $0$ to each $\mathcal{E}_{i}$. In explore rounds (prob. $\gamma$), select $i\in[k]$ and $a\in U$ uniformly at random. Play set $S_{t}=S_{t}^{i-1}+a$, observe feedback $f_{t}(S_{t}^{i-1}+a)$, give this value to $\mathcal{E}_{i}$, and feedback $0$ to the remaining experts.

As we show in Appendix B.1, directly privatizing this algorithm using the Hedge method from the full-information setting results in an expected $(1-1/e)$-regret of $\mathcal{O}(T^{3/4})$, which is far from the optimal $\mathcal{O}(T^{2/3})$. The problem with this naive approach is that a new sample is obtained via the Hedge algorithms at every time-step, including exploit steps, so to ensure $(\varepsilon,\delta)$-DP, a learning rate of $\eta=\frac{\varepsilon}{k\sqrt{32T\log(k/\delta)}}$ is required.

We improve upon this by calling the Hedge algorithm only after an exploration time-step has occurred, and new information is available. The learner continues playing this same set until the next exploration round, and privacy of these exploitation rounds follows from post-processing. This dramatically reduces the number of rounds that access the dataset, and reduces the overall amount of noise required for privacy.

If the exact number of exploration rounds were known, this could be plugged into the learning rate $\eta$ to achieve $(\varepsilon,\delta)$-DP. In the non-private setting, a doubling trick (see, e.g., Shalev-Shwartz, (2012)) can be employed to find the right learning rate by calling the algorithm multiple times, doubling $T$ and thus rescaling $\eta$ on each iteration. Unfortunately, this doubling trick does not work in the private setting due to the direct non-linear connection between $\varepsilon$ the privacy parameter, $T$ the time horizon and $\eta$ the learning rate, as specified in Proposition 2. Instead we use concentration inequalities (Alon and Spencer,, 2004) to ensure that there are no more than $2\gamma T$ exploration rounds, except with probability $e^{-8{T^{1/3}}}$. With this, we can select a fixed learning rate $\eta=\frac{\varepsilon}{k\sqrt{32(2\gamma T)\log(k/\delta)}}$ and guarantee optimal $\mathcal{O}(T^{2/3})$ expected $(1-1/e)$-regret, and the cost of $(\varepsilon,\delta+e^{-8{T^{1/3}}})$-DP.

We remark in Appendix B.2 that this additional loss in the $\delta$ term can be avoided by pre-sampling the exploration round, but this requires $\Theta(T^{2/3}+k|U|)$ space, which may be unacceptable for large $T$.

Algorithm 3 presents the space-efficient approach. Here $\widehat{f}_{t}^{i}$ is the vector with $a$-th coordinate given by: $\widehat{f}_{t}^{i,a}=f_{t}(S_{t}^{i-1}+a)\mathbf{1}_{\{\text{Explore at time $t$, pick }i,\text{ pick }a\}}$.

We sketch an extension of our methodology for (continuous) DR-submodular functions (Hassani et al.,, 2017; Niazadeh et al.,, 2018). Further details can be found in Appendix C.

Let $\mathcal{X}=\prod_{i=1}^{n}\mathcal{X}_{i}$, where each $\mathcal{X}_{i}$ is a closed convex set in $\mathbb{R}$. A function $f:\mathcal{X}\to\mathbb{R}_{+}$ is called DR-submodular if $f$ is differentiable and $\nabla f(\mathbf{x})\geq\nabla f(\mathbf{y})$ for all $\mathbf{x}\leq\mathbf{y}$. DR-submodular functions do not fit completely in the context of convex functions. For instance, the multilinear extension of a submodular function (Calinescu et al.,, 2011) is DR-submodular. The function $f$ is said to be $\beta$-smooth if $\|\nabla f(\mathbf{x})-\nabla f(\mathbf{y})\|_{2}\leq\beta\|\mathbf{x}-\mathbf{y}\|_{2}$. In the online learning DR-submodular maximization problem, at each time-step $t=1,\ldots,T$, a $\beta$-smooth DR-submodular function $f_{t}:\mathcal{X}\to[0,1]$ arrives and, without observing the function, the learner selects a point $\mathbf{x}_{t}\in\mathcal{X}$ learned using $f_{1},\ldots,f_{t-1}$. She gets the value $f_{t}(\mathbf{x}_{t})$ and also oracle access to $\nabla f_{t}$. The learner’s goal is to minimize the $(1-1/e)$-regret $\mathcal{R}_{T}=\left(1-\frac{1}{e}\right)\max_{\mathbf{x}\in\mathcal{P}}\sum_{t=1}^{T}f_{t}(\mathbf{x})-\sum_{t=1}^{t}f_{t}(\mathbf{x}_{t})$.

Online DR-submodular problems have been extensively studied in the full information setting—see for instance (Chen et al., 2018b, ; Chen et al., 2018a, ; Niazadeh et al.,, 2018). Similarly to the discrete submodular case, most of these methods implement $K$ ordered algorithms $\mathcal{E}_{0},\ldots,\mathcal{E}_{K-1}$ for optimizing linear functions over $\mathcal{X}$. Algorithm $\mathcal{E}_{k}$ computes a direction of maximum increment from a point given by the algorithms $\mathcal{E}_{k-1},\ldots,\mathcal{E}_{0}$. The learner averages these directions to obtain a new point to play in the region $\mathcal{X}$. This is the continuous version of the Hedge approach.

We show in Algorithm 4 and Theorem 9 that a simple modification transforms the continuous method of Chen et al., 2018b into a differentially private one. For this, we utilize the Private Follow the Approximate Leader (PFTAL) framework of Thakurta and Smith, (2013) as a black-box. PFTAL is an online convex optimization algorithm for minimizing $L$-Lipschitz convex functions over a compact convex region $\mathcal{X}$. In few words, their algorithm guarantees $(\varepsilon,0)$-DP and achieves an expected regret $\mathcal{O}\left(\frac{L^{2}\sqrt{nT\log^{2.5}T}}{\varepsilon}\right)$.

The big $\mathcal{O}$ term hides dimension, bounds in gradient and diameter of $\mathcal{X}$ and only shows terms in $T$ and privacy parameter $\varepsilon$. The proof appears in Appendix C.