summaries: This paper studies of designing revenue optimizing auctions subject to the an additional constraint on fairness. Instead of algebraically capturing the fairness of an allocation, the authors train a neural network termed PreferenceNet that assign a fairness score to any allocation. The neural network for strategy-proof, revenue maximizing auction (RegretNet) is trained to trade-off revenue and regret with the preference loss.  The author evaluate this on small instances (2-4 bidders and 2-4 items) and contrast revenue, regret and fairness of simple RegretNet with one constrained to produce fair allocations.   One primary motivation for a deep neural network based PreferenceNet is that it can capture real world preferences from humans. To explore this aspect, the authors conducted real world studies to get user preference samples and trained a PreferenceNet on that. They also correlate preference learned from humans with mathematical models of preference.

summaries: This paper covers a somewhat interesting and novel problem: learning constraints of an auction setting, and then learning to run an auction that respects those. Fairness in allocations is cited as a justification for this in practice, where it may be beneficial to learn from a human’s choices to determine how to decide who should win in the auction, for example to determine similar allocations across demographics.  The approach builds on the RegretNet line of work that learns to run revenue maximizing auctions. The approach broadly is to learn a feasibility constraint that is scored by human subjects, and then use that in the RegretNet architecture to learn to generate auctions that respect that constraint. In this work, the motivating constraint is a binary classification of fairness. The implementation is a composition of learning then constraint, followed by leveraging RegretNet to learn according to that function.   To support the approach, the authors first compare PreferenceNet to RegretNet trained with the exact constraints, and see similar performance suggesting some amount of usefulness. The authors then train PreferenceNet on responses from human subjects in two surveys regarding the binary qualitative fairness of allocations.

summaries: This paper proposes PreferenceNet, which is a new deep learning approach for designing revenue-maximizing auctions that encodes human preferences. PreferenceNet extends RegretNet [Duetting et al. 2019] with modified loss functions and additional constraints.

summaries: This paper describes how we can encode socially desirable constraints in auction mechanisms learned using the regretNet framework.   The paper has two main contributions:   (1) A metric that quantifies how well these mechanisms adhere to these constraints.   (2) An neural network and a training procedure (called the preferenceNet) that can encode these constraints using exemplars of the desired allocation  The authors demonstrate the efficacy of the proposed approach by showing that it can match the performance of standard approaches on both synthetic preferences as well as human preferences

abstractText: The design of optimal auctions is a problem of interest in economics, game theory, and computer science. Despite decades of effort, strategyproof, revenuemaximizing auction designs are still not known outside of restricted settings. However, recent methods using deep learning have shown some success in approximating optimal auctions, recovering several known solutions and outperforming strong baselines when optimal auctions are not known. In addition to maximizing revenue, auction mechanisms may also seek to encourage socially desirable constraints such as allocation fairness or diversity. However, these philosophical notions neither have standardization nor do they have widely accepted formal definitions. In this paper, we propose PreferenceNet, an extension of existing neural-network-based auction mechanisms to encode constraints using (potentially human-provided) exemplars of desirable allocations. In addition, we introduce a new metric to evaluate an auction allocations’ adherence to such socially desirable constraints and demonstrate that our proposed method is competitive with current state-of-the-art neural-network based auction designs. We validate our approach through human subject research and show that we are able to effectively capture real human preferences. Our code is available on GitHub.

authors:
Gianluca Brero
Benjamin Lubin
Sven Seuken

title: Machine Learning-powered Iterative Combinatorial Auctions

venue: (Nov

authors:
Yang Cai
Constantinos Daskalakis
S Matthew Weinberg

title: An algorithmic characterization of multi-dimensional mechanisms

venue: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

title: Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization

venue: IEEE 53rd Annual Symposium on Foundations of Computer Science

title: Understanding incentives: Mechanism design becomes algorithm design

venue: IEEE 54th Annual Symposium on Foundations of Computer Science

authors:
L Elisa Celis
Anay Mehrotra
Nisheeth K Vishnoi

title: Toward controlling discrimination in online ad auctions

venue: In: International Conference on Machine Learning (ICML)

authors:
Shuchi Chawla
Meena Jagadeesan

title: Fairness in ad auctions through inverse proportionality

venue: arXiv preprint arXiv:2003.13966

title: Multipart pricing of public goods

venue: Public choice

title: Electricity market design

venue: Oxford Review of Economic Policy

title: The FCC spectrum auctions: An early assessment

venue: Journal of Economics & Management Strategy

authors:
Michael Curry
Ping-yeh Chiang
Tom Goldstein
John P. Dickerson

title: Certifying Strategyproof Auction Networks

venue: Neural Information Processing Systems (NeurIPS)

authors:
Constantinos Daskalakis
Alan Deckelbaum
Christos Tzamos

title: Mechanism design via optimal transport

venue: Proceedings of the fourteenth ACM conference on Electronic commerce

title: Strong Duality for a Multiple-Good Monopolist

authors:
Paul Duetting
Zhe Feng
Harikrishna Narasimhan
David C. Parkes
Sai Srivatsa Ravindranath

title: Optimal Auctions through Deep Learning

authors:
Benjamin Edelman
Michael Ostrovsky
Michael Schwarz

title: Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords

venue: American Economic Review

authors:
Zhe Feng
Harikrishna Narasimhan
David C. Parkes

title: Deep Learning for Revenue- Optimal Auctions with Budgets

venue: In: International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)

authors:
Sainyam Galhotra
Sandhya Saisubramanian
Shlomo Zilberstein

title: Learning to Generate Fair Clusters from Demonstrations

venue: (Feb

authors:
Robert Geirhos
Jörn-Henrik Jacobsen
Claudio Michaelis
Richard Zemel
Wieland Brendel
Matthias Bethge
Felix A Wichmann

title: Shortcut learning in deep neural networks

venue: Nature Machine Intelligence

authors:
Yiannis Giannakopoulos
Elias Koutsoupias

title: Duality and optimality of auctions for uniform distributions

venue: Economics and Computation (EC)

authors:
Noah Golowich
Harikrishna Narasimhan
David C. Parkes

title: Deep Learning for Multi- Facility Location Mechanism Design

venue: In: International Joint Conference on Artificial Intelligence (IJCAI)

title: Incentives in teams

venue: Journal of the Econometric Society

authors:
Nima Haghpanah
Jason D. Hartline

title: Reverse Mechanism Design

authors:
Kenneth Holstein
Jennifer Wortman Vaughan
Hal Daumé III
Miro Dudik
Hanna Wallach

title: Improving fairness in machine learning systems: What do industry practitioners need?

venue: In: Conference on Human Factors in Computing Systems (CHI)

authors:
Christina Ilvento
Meena Jagadeesan
Shuchi Chawla

title: Multi-Category Fairness in Sponsored Search Auctions

venue: In: Conference on Fairness, Accountability, and Transparency (FAccT)

authors:
Ian A Kash
Rafael M Frongillo

title: Optimal auctions with restricted allocations

authors:
Kevin Kuo
Anthony Ostuni
Elizabeth Horishny
Michael J. Curry
Samuel Dooley
Pingyeh Chiang
Tom Goldstein
John P. Dickerson

title: ProportionNet: Balancing Fairness and Revenue for Auction Design with Deep Learning

authors:
Kevin Leyton-Brown
Paul Milgrom
Ilya Segal

title: Economics and computer science of a radio spectrum reallocation

venue: Proceedings of the National Academy of Sciences (PNAS)

authors:
Jingling Li
Mozhi Zhang
Keyulu Xu
John P. Dickerson
Jimmy Ba

title: Noisy Labels Can Induce Good Representations

authors:
Alejandro M. Manelli
Daniel R. Vincent

title: Bundling as an optimal selling mechanism for a multiple-good monopolist

venue: J. Econ. Theory

title: Optimal auction design

venue: Mathematics of Operations Research

title: Optimal mechanism for selling two goods

venue: The BE Journal of Theoretical Economics

authors:
Jad Rahme
Samy Jelassi
Joan Bruna
S Matthew Weinberg

title: A Permutation-Equivariant Neural Network Architecture For Auction Design

authors:
Jad Rahme
Samy Jelassi
S Matthew Weinberg

title: Auction learning as a two-player game

venue: In: International Conference on Learning Representations (ICLR)

title: A necessary and sufficient condition for rationalizability in a quasi-linear context

venue: Journal of mathematical Economics

authors:
Debjani Saha
Candice Schumann
Duncan C McElfresh
John P Dickerson
Michelle L Mazurek
Michael Carl Tschantz

title: Measuring Non-Expert Comprehension of Machine Learning Fairness Metrics

authors:
Nripsuta Ani Saxena
Karen Huang
Evan DeFilippis
Goran Radanovic
David C Parkes
Yang Liu

title: How do fairness definitions fare? Examining public attitudes towards algorithmic definitions of fairness

venue: Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society

authors:
Weiran Shen
Pingzhong Tang
Song Zuo

title: Automated mechanism design via neural networks

venue: Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems

authors:
Megha Srivastava
Hoda Heidari
Andreas Krause

title: Mathematical Notions vs. Human Perception of Fairness: A Descriptive Approach to Fairness for Machine Learning

authors:
Andrea Tacchetti
DJ Strouse
Marta Garnelo
Thore Graepel
Yoram Bachrach

title: A neural architecture for designing truthful and efficient auctions

title: Counterspeculation, auctions, and competitive sealed tenders

venue: The Journal of finance

title: Dominant-strategy versus bayesian multi-item auctions: Maximum revenue determination and comparison

venue: Economics and Computation (EC). 2017

heading: 1 Introduction

text:
Auctions are an essential tool in many marketplaces, including those in electricity [8], advertising [14], and telecommunications [9, 26]. The design of auctions with desirable properties is thus an important theoretical and practical problem. A typical assumption is that bidders may choose to bid strategically and will successfully anticipate the behavior of other bidders. This results in a potentially complicated Bayes-Nash equilibrium which may be difficult to predict. To evade this problem, a common requirement is that an auction should be strategyproof (i.e. bidders should be incentivized to truthfully share their valuations regardless of other bidders’ actions).
If the goal of an auction is to maximize the total welfare of all participants, the Vickrey-ClarkeGroves (VCG) mechanism is both strategyproof and welfare-maximizing [40, 7, 20]. Intuitively, in many cases the VCG mechanism corresponds to a second-price auction. If the goal is to maximize the revenue gained, the problem is more challenging. Myerson’s work completely characterizes strategyproof, revenue-maximizing auctions for a single item [29]. Beyond this case, results are more limited. Some results are known for the “multiple-good monopolist” problem, in which the auctioneer sells multiple items to a single bidder [11, 12, 24, 31, 28, 21, 18]. In addition, designing auctions for the related but weaker notion of Bayes-Nash incentive compatibility is reasonably well understood [2, 3, 4].
There has been significant difficulty in designing strategyproof auctions involving multiple items and multiple bidders. [41] shares significant, but limited results which solve the case in which items
* The first two authors contributed equally to this work. 35th Conference on Neural Information Processing Systems (NeurIPS 2021).
may have at most 2 values. Due to the apparent difficulty of analytically designing strategyproof, revenue maximizing auctions, recent methods instead approximate optimal auctions using machine learning approaches [13, 10, 19, 25, 15, 33, 32]. [37] proposes an method which guarantees exact strategyproofness in the single-agent setting. [39, 1] also use neural networks in the design of auctions. These methods primarily focus on standard mechanism design goals of revenue or welfare maximization, but these may not be the only goals of an auction. An auction might be conducted for public goods (i.e. electromagnetic spectrum distribution [9]), where the auctioneer must consider the effect not only on the auctioneer and bidders but on third-parties as well [30]. In other cases, such as auctions involving job or credit advertisements, it might be necessary to additionally constrain the auction mechanism to ensure fairness with respect to protected characteristics [23, 6]. Recent work has considered the problem of determining revenue-maximizing, strategyproof, fair auctions, either from a specific class [5] or with a general neural network approach [25].
The underlying notions of “fairness” used in these papers (e.g. total-variation fairness [23]) are defensible but somewhat arbitrary – they are attempts to formally capture human intuition. It might instead be better to attempt to capture, from data, human intuitions about fairness or other ethical requirements that are not explicitly defined [38, 16].
In this paper, we introduce PreferenceNet, an extension to RegretNet that directly encodes socially desirable constraints from data, and captures noisy human preferences. We are motivated by advertising auctions where the allocations of the auction mechanism must satisfy human preference constraints alongside the typical goals of strategyproofness and revenue maximization. We conduct a number of experiments using synthetic data (as is typical for neural network based auction mechanisms [13]) and evaluate our method on different auction settings and fairness constraints. We show that PreferenceNet is able to effectively capture each fairness constraint and matches the performance of standard approaches. We also conduct two surveys to further study human preferences. In the first survey (n=140), when given a specific definition of fairness, we ask participants to determine if a given auction setting is fair in order to test the noise in human judgements. In the second survey (n=345), we elicit judgements of pairwise comparisons of two auction settings to determine preferences without priming the participants with any particular definition of fairness. We train PreferenceNet on these data and show that our approach can capture nuanced human preferences in auction design.

heading: 2 Background and Related Work

text:
RegretNet. [13] presents RegretNet, a neural-network architecture for learning approximately strategyproof auctions that maximize revenue. RegretNet treats the auction mechanism as a function from bids to allocations and payments, parameterized as a neural network. Revenue is optimized via gradient descent on sampled truthful bid profiles; strategyproofness is enforced by computing strategic bids in an adversarial manner to minimize violations. RegretNet has been modified and extended in a variety of ways, particularly to enforce additional desirable constraints. [10, 39, 19, 25, 15, 33].
Special Case: Single-Bidder Auctions. We highlight a special case in which deep learning for auctions has been particularly successful – auctions with a single bidder. In the single-bidder setting, the set of strategyproof mechanisms can be easily characterized [34], and it is possible to design neural network architectures which will always lie in this set. [13, 37] present two different learningbased solutions. Both methods are guaranteed to be strategyproof, and revenue can be maximized by unconstrained optimization. There are some known optimal single-agent mechanisms (we highlight those of Manelli-Vincent [28] and Pavlov [31], as they are relevant to auction settings we study below). Moreover, the theory of single-bidder mechanisms is well understood [11, 12, 18], so it is also possible to learn empirically strong mechanisms using these approaches and then prove their optimality [37, 13]. Unfortunately, when moving beyond the single-agent setting, it is necessary to use more general neural network architectures for which these guarantees do not apply. Because we are interested in such settings, we focus on these general architectures in this work.
Fairness and Human Preferences. As mentioned, while revenue, strategyproofness, and individual rationality are the classic goals of auction design, it might also be necessary for allocations made by an auction to satisfy certain other requirements such as fairness [5, 25]. However, it is not always
clear if these mathematical definitions of these concepts actually capture human intuitions. [36, 38] considers human reactions to different definitions of fairness in a classification setting. [35] tests the extent to which human participants are able to understand and apply fairness metrics. [16] considers the problem of learning to perform fair clustering from human-provided demonstrations. As discussed below, we also crowdsource human opinions on fairness in auctions and analyze the results in Section 6.

heading: 3 Problem Setting

text:
Auction Model. An auction is defined as a set of agents N = {1, . . . , n} bidding for items M = {1, . . . ,m}. Each agent i ∈ N has a corresponding private valuation vi, randomly drawn from a set of n valuations as v = (v1, ...vn) ∈ Vi. In general vi may be functions over the power set of items 2M . However, we only consider simpler cases with additive valuations and unit-demand valuations, where the valuation is simply a vector vi ∈ Rm of values per item. Each agent reports a bid vector bi to the auctioneer, which may differ from the private valuation vi. Given the profile of bids b = (b1, . . . , bn) of all agents, the auction has allocation and payment rules g(b) : Rmn → [0, 1]nm and p(b) : Rmn → Rn. We will refer to the matrix of allocation probabilities, whose rows must sum to 1, as g(b) = z . Likewise agent i’s value of the jth item is vi,j , and bidder i has payment function pi. Moreover, for unit-demand auctions, we restrict the allocation to allow each bidder to win, in expectation, at most 1 item. Given the allocation, each agent receives a utility which can in either case be represented in linear form as ui(v) = ∑ j vi,jzi,j − pi.
Desirable Auction Properties. A mechanism is individually rational (IR) when an agent is guaranteed non-negative utility: ui(vi; v) ≥ 0 ∀i ∈ N, v ∈ V . A mechanism is dominant-strategy incentivecompatible (DSIC) or strategyproof if every agent maximizes their own utility by bidding truthfully, regardless of the other agents’ bids. We can define regret, the difference in utility between the bid player i actually made and the best possible strategic bid: rgti(v) = maxbi ui(bi, v−i)− ui(vi, v−i). In addition to satisfying the IR and DSIC constraints, the auctioneer seeks to maximize their expected revenue. If the auction is truly DSIC, players will bid truthfully, and as a result revenue is simply Ev∼V [ ∑ i∈N pi(v)].

heading: 4 PreferenceNet: Encoding Human Preferences

text:
We first explore a new metric to evaluate the adherence to socially desirable constraints in item allocations. Next, we describe the implementation details of PreferenceNet and important considerations when training the model.
Evaluation Metrics. There are limited evaluation criteria that quantitatively measures an auction mechanism’s ability to enforce constraints on item allocations. If the constraints are not known explicitly, one can qualitatively examine the allocation graphs to evaluate the underlying allocation function g(b). However, visual inspection does not scale to larger auction settings. As shown in Figure 1, our proposed metric is not only able to capture the same insights as qualitative analysis, but also scales to arbitrarily large auction mechanisms.
Given the limitations of existing analysis techniques, we propose Preference Classification Accuracy (PCA), a new metric to evaluate how well a learned auction model satisfies an arbitrary constraint. For a set of test bids b and allocations g(b) : Rmn → [0, 1]nm generated by our learned auction model, we assign a label s(b) ∈ {1, 0} to each allocation according to a ground truth labeling function based on the underlying preference. For each test bid b, s(b) is 1 if the learned auction network satisfies the ground truth constraint. PCA is calculated by averaging the value of s(b) over n test bids. Note that this metric remains valid in cases when we know the underlying preference function (e.g. total variation fairness, entropy) as well as when we are sampling from an unknown distribution (e.g. human preference elicitation). For cases where the underlying preference function is known, we can directly compute the preference score for a given allocation and apply a threshold to obtain a label. For cases where the preference function is unknown, as is the case in human preference elicitation, we can use the ground truth allocation-label pair to assign preference labels s(b) to new allocations based on the nearest neighbor in the ground truth set. This metric gives us a formal way to measure
the degree to which preference constraints are violated, which crucially can be used whether or not the constraints follow an explicitly-known function.
Preference Elicitation. In order to effectively elicit preferences, we rely on pairwise comparisons between allocations to identify both positive and negative exemplars. We compare each input set of of allocations against n other allocations to determine if a particular sample is preferred over these alternatives (see Figure 2). This method of group preference elicitation reduces noise and ensures that the learned preference is satisfactory to a majority of the participants. We use this ranking approach to generate training labels in all of our experiments as described below.
Training Algorithm. We present the training algorithm of PreferenceNet below. We use the same additive and unit-demand network architectures as RegretNet for arbitrary numbers of agents and items. Our training algorithm follows closely from RegretNet. PreferenceNet consists of two subnetworks: RegretNet and a 3-layer MLP with a sigmoid activation at the output. We first train the MLP using a uniformly drawn sample of allocations as inputs, and optimize the binary cross entropy loss function using ground truth labels (generated as in Figure 2) identifying positive and negative exemplars. Next, we train RegretNet using the standard training procedure with the modified loss function described in Eq. 1. Lastly, we sample allocations and payments from the partially trained RegretNet model every c epoch and augment the MLP training set to adapt to the distributional shifts in allocations over the course of training. Our modified loss function Cρ(w;λ) is defined as:
Lrgt = ∑ i∈N λ(r,i) rgti(w) + ρr 2 ∑ i∈N rgti(w) 2, Ls = ∑ j∈M sj
Cρ(w;λ) = − 1
L L∑ l=1 ∑ i∈N pwi (v (l)) + Lrgt − Ls (1)
where Ls is the output of the trained MLP. RegretNet is optimized such that it is strategyproof, revenue-maximizing, satisfies the preference learned by the MLP (i.e. maximizes the output scores of the MLP).
For each configuration of n agents and m items, we train RegretNet for a maximum of 200 epoch using 160,000 training samples. We also train the MLP with 80,000 initial training samples and iteratively retrain the MLP with 5,000 additional samples from the partially trained RegretNet every 5 epoch. For all networks, we use the Adam optimizer and 100 hidden nodes per layer. We apply warm restarts to the MLP optimizer each time we add new training data to to prevent the model from settling in a local minima. We incremented ρr every 2500 iterations and λr every 25 iterations. Finally, we report the preference classification accuracy, mean regret, and mean payments by simulating the allocations of 20,000 testing samples. We run all our experiments on an NVIDIA Titan X (Pascal) GPU. We refer readers to GitHub for our implementation.
MLP Architecture. We learn implicit preference functions using a simple 3-layer multi-layer perceptron that takes as input a mini-batch of allocations and outputs a vector that scores the input ∈ [0, 1] as a measure of how closely the allocation satisfies the ground truth preference. Given that neural networks are universal function approximators, with enough parameters the MLP can represent any arbitrary preference function. In practice, we find that ReLU non-linear activations and batch normalization are essential to effectively train this network.
Class Balanced Sampling. The distribution of positive and negative training examples for arbitrary preferences are often imbalanced – preferred examples may be concentrated in a small region of possible allocations. Often, this imbalance can make it difficult to train a robust model. Commonly, neural networks with improper class balance fail to learn a good decision boundary. In order to compensate for such imbalanced datasets, we can explicitly over-sample sparse classes until there are an equal number of positive and negative training examples. In practice this allows the network to quickly learn the decision boundary and allows us to train with fewer data points.
MLP Co-Training. The distribution of payments and allocations generated by RegretNet shift significantly during the course of training. As a result, the initially trained MLP may not effectively enforce the preference loss as RegretNet continues to train. In order to adapt to the distribution shift, we sample allocations from RegretNet at fixed intervals while it is training, add them back to the training set, and retrain the MLP. We generate noisy labels [27] using the existing MLP to reduce the cost of collecting expensive labels. In practice, we find that this approach effectively reinforces the decision boundary between positive and negative exemplars.
Model Validation and Selection. The optimal model minimizes regret, while maximizing payments and preference classification accuracy. In practice, satisfying all three conditions may be difficult. Often, we find that choosing a fixed epoch to evaluate does not provide consistent results. Rather, we evaluate each checkpoint on a validation set and maximize the following criteria in Eq. 2:
α ∗ PCA + β ∗ ¯p(b)
max(p(b)) + γ ∗ (1−
¯rgt(b)
max(rgt(b)) ) s.t. α+ β + γ = 1 (2)
In our experiments we set α = 0.45, β = 0.1, γ = 0.45. It is important to note that the maximum regret and payments are calculated over the entire training process, while the mean regret, payment, and preference classification accuracy are calculated at each epoch.

heading: 5 Sampling Synthetic Preferences

text:
Given the lack of publicly available auction data, we generate synthetic bids as in [13, 25, 37]. We first validate PreferenceNet using synthetic preferences, and extend our analysis to real human preferences in Section 6. In our synthetic preference experiments, we are interested in three types of fairness: total variation fairness (TVF), entropy, and a quota system. All three definitions of fairness map the allocations g(b) onto R. We train auction models for each of these valuation function and compare RegretNet with our proposed model under uniform additive and unit-demand auction settings in Table 5. Note in Table 5 that RegretNet is trained with an additional loss function term to explicitly optimize for the preference. PreferenceNet is trained as described in 4. We describe the three definitions of fairness below:
Total Variation Fairness. An auction mechanism satisfies total variation fairness if the `1-distance between allocations for any two users is at most the distance between those users. That is, total variation fairness is satisfied when
∀k ∈ {1, ..., c},∀j, j′ ∈M, ∑ i∈Ck |g(b)i,j − g(b)i,j′ | ≤ dk(j, j′). (3)
We fix d = 0 in all of our experiments. We minimize violations of the above constraints.
Entropy. An auction mechanism satisfies the entropy constraint if the entropy of the normalized allocation for a bid profile b
− n∑ i=1 P ( g(b)i,·∑ j g(b)ij ) logP ( g(b)i,·∑ j g(b)ij ) (4)
is maximized. We normalize across items, turning the allocation into a probability distribution. This normalization ensures that entropy reflects diversity in the allocations, and not the overall number of items being allocated. Specifically, encouraging entropy ensures that the allocation for a given agent will tend to be more uniformly distributed.
Quota. An auction mechanism satisfies the quota constraint if, for each item in the (normalized) allocation, the smallest allocation to any agent j is greater than some minimum threshold t:
min j ( g(b)·,j∑ i g(b)i,j ) > t (5)
Here, we normalize the allocation so that the allocation per item will be a probability distribution over agents. The intuition for this definition is that each agent must guarantee some floor across every item. Returning to the advertising example, this ensures some minimum percentage of ad impressions are seen by every demographic group.
We train a number of models to compare the performance between RegretNet and PreferenceNet. Despite leveraging an weaker, implicit signal to learn fairness constraints, PreferenceNet is able to closely match the performance of RegretNet. Surprisingly, PreferenceNet improves upon RegretNet in some cases, indicating that with careful hyperparameter tuning, further improvements are possible. Of the three fairness constraints examined, enforcing a quota is hardest for additive auctions, as both RegretNet and PreferenceNet struggled for auctions with a large number of agents.
Limitations. Despite its effectiveness, we highlight limitations of our approach. In general, PreferenceNet always optimizes for the simplest function. For example, if learning a piece-wise preference where the positive exemplars are not clustered in a single region as in Figure 3, PreferenceNet tends to only satisfy part of the piece-wise function. This is unsurprising, given that neural networks are known to take shortcuts in optimization [17]. Moreover, PreferenceNet has difficulty in generating allocations with tightly clustered preference scores to satisfy a particular constraint. Given that we optimize for preferences implicitly using exemplars, this behavior is understandable. We study these limitations further in the supplemental material.

heading: 6 Soliciting Human Preferences

text:
In this section, we detail the creation of and results derived from two human subjects surveys. The results of these surveys are used to validate core assumptions of our model and provide data that we use to train an auction model. We find that PreferenceNet is able to adhere to the notion of fairness expressed by the human’s preferences of auction outcomes. This encouraging result validates the utility and expressiveness of PreferenceNet.
We conducted both surveys through Cint, a crowdsourcing platform which connected us with Englishspeaking participants located in the United States. After submitting an application for our human subjects research to our institutional IRB, we were notified that the survey was exempt from IRB review. Our survey protocols can be found in the supplemental materials. Cint compensates per survey completion (regardless of length to complete), and both surveys were set to pay $1.92. All survey results are anonymized to protect participant privacy. We include these results in the supplemental material.
Measuring Preference Noise. Our first survey was designed to test how participants would interpret and apply a simple fairness definition. The survey protocol was designed as follows: We primed participants to consider an advertising auction that was shown to two different (vague) demographic groups. Each participant was told that an auction would be fair if each ad was presented to each group at equal rates. After some familiarization, we asked the participants to determine if a given scenario was fair. Each participant was asked 30 such questions. The median completion time for the survey was 6 minutes with a median hourly wage of $18. The 30 questions presented to the participants came from a question bank of 64 randomly generated scenarios, each with an associated TVF score.
Human understanding is an inherently noisy process. Despite providing the same context, we observe that survey participants understand a given definition of fairness and apply it to various scenarios differently. Given this data, we perform a normality test using a Q-Q plot as shown in the supplemental material. We find that our survey data are well correlated with the Gaussian distribution. This is also well supported by our visual inspection of the noise distribution. Experimentally, we observe that participants’ choice of what is fair has a decision boundary at approximately a TVF value of 0.7. Interestingly, the noise is maximal near the decision boundary as shown in Figure 4. Concretely, we can model this noise using a probit model, so that the probability that that the label is unpertubed for a particular TVF value increases with distance such that P (Y = 1|X) = kΦ( |x−µ|σ ), where Φ is the CDF of the Gaussian distribution, µ is the decision boundary, σ is the measured sample standard deviation, and k is an optional parameter that can scale the noise. We can use this noise model to perturb the input training data to the MLP to better simulate real data. We explore this further in the supplemental material.
Group Preference Elicitation. We designed our second survey to ask similar questions to the preference noise survey above. However, there were two primary differences: (1) we did not prime the participants with a fairness definition, and (2) the participants were presented with two scenarios and were asked which they thought was more fair. Each participant was asked 30 of these pairwise questions on the questions described above (full protocol details in the supplemental materials). This survey had 345 participants who had a median completion time of 7 minutes and a median pay of $15 per hour.
Notions of fairness and diversity have neither standardized nor widely accepted formal definitions [38, 35, 36, 22]. The purpose of this survey is to elicit preferences from a group and train an auction model whose allocations resemble the group preference. Using the survey data, we apply our preference elicitation strategy as described in Section 4 to generate training labels for each sample. After training PreferenceNet to enforce the group preference for both the unit-demand and additive auction settings, we find that the group preference is more similar to TVF and entropy. As shown in Figure 5, human preferences are not perfectly captured by these typical models, both because group preferences rarely converge to a unifying model, and preference elicitation is a noisy process.

heading: 7 Conclusion

text:
Although surveying people to elicit their preferences can effectively help us model ambiguous definitions of socially beneficial constraints, we must be careful about the framing of the survey questions and the choice of audiences we survey.
Ethical Implications. Humans are inherently biased, so we need to be cognizant of the effects these latent biases might have over preferences for fairness. Moreover, sampling human preferences facilitates opportunities for data poisoning attacks, in which a malicious survey respondent could try to negatively impact the survey collection process. In general, we can mitigate both of these issues by sampling at scale to avoid problems with noisy labels, although this brings additional cost. Most importantly, we must involve stakeholders to ensure that their preferences are validated through the learned model in an iterative process.
In this paper we present PreferenceNet, a novel extension to RegretNet that makes it easier to learn preferences from data to encode socially desirable constraints for auction design. We introduce a new metric to empirically measure how closely a learned mechanism enforces a particular constraint, and show that our proposed method is able to effectively capture human preferences.
Acknowledgments and Disclosure of Funding
This research was supported in part by NSF CAREER Award IIS-1846237, NSF D-ISN Award #2039862, NSF Award CCF-1852352, NIH R01 Award NLM-013039-01, NIST MSE Award #20126334, DARPA GARD #HR00112020007, DoD WHS Award #HQ003420F0035, and a Google Faculty Research Award. We thank the authors of ProportionNet for sharing their codebase and Kevin Kuo and Uro Lyi for their feedback in writing this paper.

title: PreferenceNet: Encoding Human Preferences in Auction Design with Deep Learning


summaries: The paper presents an algorithm for differentially private (DP) learning of personalized models. A set of users with their own private data collaborate to privately learn a good embedding of the data followed by a linear regression based on this embedding.   The paper contribution is a theoretical analysis of the proposed algorithm with DP guarantees and utility bounds.   As far as I know there is no such bounds in the literature within the same setting. The author compare their result with the bounds in the non private case and with an upper bound obtained using the exponential mechanism which provides an information theoretic bound but cannot be efficiently implemented. In the later case, the bounds on the excess risk differs by O(1/\epsilon) and O(1/\sqrt(m)), m being the number of samples and \epsilon the privacy budget.

summaries: This paper focuses on a setting, where there are multiple users each holds a training dataset. In this setting, users have to share information about their model or data to learn a meaningful representation and to solve their tasks better than they could without using the shared, low-dimensional representation. The paper proposes an approach for this problem that provides strong user-level differential privacy guarantees at the same time. For the privacy guaranteees, the method uses exponential mechanism and utility analysis of the algorithm is made by using that.

summaries: The authors deal with personalized model learning under the user-level joint differential privacy. In this problem, each user aims to build a user-specified model to make a prediction for the user's data. In the training process, the users utilize knowledge from the other users' data to improve their model's performance. In this setup, we want to prevent the leakage of the sensitive information in the user's data to the other user. The authors develop the differentially private algorithms for the model personalization task and reveal the upper bounds on the personalized model's accuracy of these algorithms.

summaries: This paper studies the problem of model personalization with user-level differential privacy in the setting where users don't have enough data to find a good solution on their own but can leverage information in similar learning problems shared by other users. The problem is viewed as learning a 2-layer neural network, where the first embedding is the shared structure and the second layer is trained individually. This paper provides two types of algorithms: inefficient algorithms based on the exponential mechanism that establish information-theoretic upper bounds on an achievable error and efficient algorithms based on alternating minimization, which starts from an initial embedding and then repeatedly uses a DP minimizer to minimize the error. For the specific case of linear regression with squared error loss, the paper shows the alternating minimization framework can converge to a near-optimal embedding.

abstractText: We study personalization of supervised learning with user-level differential privacy. Consider a setting with many users, each of whom has a training data set drawn from their own distribution Pi. Assuming some shared structure among the problems Pi, can users collectively learn the shared structure—and solve their tasks better than they could individually—while preserving the privacy of their data? We formulate this question using joint, user-level differential privacy—that is, we control what is leaked about each user’s entire data set. We provide algorithms that exploit popular non-private approaches in this domain like the Almost-No-Inner-Loop (ANIL) method, and give strong user-level privacy guarantees for our general approach. When the problems Pi are linear regression problems with each user’s regression vector lying in a common, unknown lowdimensional subspace, we show that our efficient algorithms satisfy nearly optimal estimation error guarantees. We also establish a general, information-theoretic upper bound via an exponential mechanism-based algorithm.

authors:
Martín Abadi
Andy Chu
Ian J. Goodfellow
H. Brendan McMahan
Ilya Mironov
Kunal Talwar
Li Zhang

title: Deep learning with differential privacy

venue: In Proc. of the 2016 ACM SIGSAC Conf. on Computer and Communications Security (CCS’16),

authors:
Peter L. Bartlett
Shahar Mendelson

title: Rademacher and gaussian complexities: Risk bounds and structural results

venue: J. Mach. Learn. Res.,

authors:
Raef Bassily
Vitaly Feldman
Kunal Talwar
Abhradeep Guha Thakurta

title: Private stochastic convex optimization with optimal rates

venue: In NeurIPS,

authors:
Raef Bassily
Adam Smith
Abhradeep Thakurta

title: Private empirical risk minimization: Efficient algorithms and tight error bounds

venue: In Proc. of the 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS),

authors:
Mark Bun
Thomas Steinke

title: Concentrated differential privacy: Simplifications, extensions, and lower bounds

venue: In Theory of Cryptography Conference,

authors:
Emmanuel J. Candès
Yaniv Plan

title: Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements

authors:
Nicholas Carlini
Chang Liu
Úlfar Erlingsson
Jernej Kos
Dawn Song

title: The secret sharer: Evaluating and testing unintended memorization in neural networks

venue: In 28th USENIX Security Symposium (USENIX Security

authors:
Nicholas Carlini
Florian Tramer
Eric Wallace
Matthew Jagielski
Ariel Herbert-Voss
Katherine Lee
Adam Roberts
Tom Brown
Dawn Song
Ulfar Erlingsson

title: Extracting training data from large language models

authors:
Kamalika Chaudhuri
Claire Monteleoni
Anand D Sarwate

title: Differentially private empirical risk minimization

venue: Journal of Machine Learning Research,

authors:
Yinbo Chen
Xiaolong Wang
Zhuang Liu
Huijuan Xu
Trevor Darrell

title: A new meta-baseline for few-shot learning

venue: arXiv preprint arXiv:2003.04390,

authors:
Liam Collins
Hamed Hassani
Aryan Mokhtari
Sanjay Shakkottai

title: Exploiting shared representations for personalized federated learning

venue: arXiv preprint arXiv:2102.07078,

title: The rotation of eigenvectors by a perturbation

venue: Journal of Mathematical Analysis and Applications,

authors:
Simon S Du
Wei Hu
Sham M Kakade
Jason D Lee
Qi Lei

title: Few-shot learning via learning the representation, provably

venue: arXiv preprint arXiv:2002.09434,

authors:
Cynthia Dwork
Krishnaram Kenthapadi
Frank McSherry
Ilya Mironov
Moni Naor

title: Our data, ourselves: Privacy via distributed noise generation

venue: In Advances in Cryptology— EUROCRYPT,

authors:
Cynthia Dwork
Frank McSherry
Kobbi Nissim
Adam Smith

title: Calibrating noise to sensitivity in private data analysis

venue: In Proc. of the Third Conf. on Theory of Cryptography (TCC),

authors:
Cynthia Dwork
Moni Naor
Toniann Pitassi
Guy N. Rothblum

title: Differential privacy under continual observation

venue: In STOC,

authors:
Cynthia Dwork
Kunal Talwar
Abhradeep Thakurta
Li Zhang

title: Analyze gauss: optimal bounds for privacy-preserving principal component analysis

venue: In Proceedings of the forty-sixth annual ACM symposium on Theory of computing,

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: arXiv preprint arXiv:1703.03400,

authors:
Robin C. Geyer
Tassilo Klein
Moin Nabi

title: Differentially private federated learning: A client level perspective

authors:
Justin Hsu
Zhiyi Huang
Aaron Roth
Tim Roughgarden
Zhiwei Steven Wu

title: Private matchings and allocations

authors:
Rui Hu
Yuanxiong Guo
Hongning Li
Qingqi Pei
Yanmin Gong

title: Personalized federated learning with differential privacy

venue: IEEE Internet Things J.,

authors:
Shaoli Huang
Dacheng Tao

title: All you need is a good representation: A multi-level and classifier-centric representation for few-shot learning

authors:
Prateek Jain
Praneeth Netrapalli
Sujay Sanghavi

title: Low-rank matrix completion using alternating minimization

venue: In Proceedings of the forty-fifth annual ACM symposium on Theory of computing,

authors:
Prateek Jain
Om Dipakbhai Thakkar
Abhradeep Thakurta

title: Differentially private matrix completion revisited

venue: In International Conference on Machine Learning,

authors:
Muhammad Abdullah Jamal
Guo-Jun Qi

title: Task agnostic meta-learning for few-shot learning

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Yihan Jiang
Jakub Konevcný
Keith Rush
Sreeram Kannan

title: Improving federated learning personalization via model agnostic meta learning

authors:
Shiva Prasad Kasiviswanathan
Homin K. Lee
Kobbi Nissim
Sofya Raskhodnikova
Adam D. Smith

title: What can we learn privately

venue: In 49th Annual IEEE Symp. on Foundations of Computer Science (FOCS),

authors:
Michael Kearns
Mallesh Pai
Aaron Roth
Jonathan Ullman

title: Mechanism design in large games: Incentives and privacy

venue: In Proceedings of the 5th conference on Innovations in theoretical computer science,

authors:
Yehuda Koren
Robert Bell
Chris Volinsky

title: Matrix factorization techniques for recommender systems

authors:
Kwonjoon Lee
Subhransu Maji
Avinash Ravichandran
Stefano Soatto

title: Meta-learning with differentiable convex optimization

venue: IEEE Computer Society,

authors:
Daniel Levy
Ziteng Sun
Kareem Amin
Satyen Kale
Alex Kulesza
Mehryar Mohri
Ananda Theertha Suresh

title: Learning with user-level

venue: privacy. CoRR,

authors:
Jeffrey Li
Mikhail Khodak
Sebastian Caldas
Ameet Talwalkar

title: Differentially private meta-learning

venue: In 8th International Conference on Learning Representations,

title: Cs229t/stat231: Statistical learning theory (winter

authors:
H. Brendan McMahan
Daniel Ramage
Kunal Talwar
Li Zhang

title: Learning differentially private recurrent language models

venue: In 6th International Conference on Learning Representations,

authors:
Frank McSherry
Kunal Talwar

title: Mechanism design via differential privacy

venue: Annual IEEE Symposium on Foundations of Computer Science

title: Rényi differential privacy

venue: IEEE 30th Computer Security Foundations Symposium (CSF),

authors:
Seewong Oh
Prateek Jain
Kiran Thekumparampil

venue: Personal communication,

authors:
Aniruddh Raghu
Maithra Raghu
Samy Bengio
Oriol Vinyals

title: Rapid learning or feature reuse? towards understanding the effectiveness of MAML

venue: arXiv preprint arXiv:1909.09157,

title: Old techniques in differentially private linear regression

venue: In ALT,

authors:
Karan Singhal
Hakim Sidahmed
Zachary Garrett
Shanshan Wu
Keith Rush
Sushant Prakash

title: Federated reconstruction: Partially local federated learning

authors:
Adam Smith
Abhradeep Thakurta
Jalaj Upadhyay

title: Is interaction necessary for distributed private learning

venue: IEEE Symposium on Security and Privacy (SP),

authors:
Shuang Song
Kamalika Chaudhuri
Anand D Sarwate

title: Stochastic gradient descent with differentially private updates

venue: IEEE Global Conference on Signal and Information Processing,

authors:
Karthik Sridharan
Shai Shalev-shwartz
Nathan Srebro

title: Fast rates for regularized objectives

venue: In Advances in Neural Information Processing Systems. Curran Associates, Inc.,

authors:
Chen Sun
Abhinav Shrivastava
Saurabh Singh
Abhinav Gupta

title: Revisiting unreasonable effectiveness of data in deep learning era

venue: In Proceedings of the IEEE international conference on computer vision,

title: Topics in random matrix theory, volume 132

venue: American Mathematical Soc.,

authors:
Kiran Koshy Thekumparampil
Prateek Jain
Praneeth Netrapalli
Sewoong Oh

title: Sample efficient linear meta-learning by alternating minimization, 2021

authors:
Yonglong Tian
Yue Wang
Dilip Krishnan
Joshua B Tenenbaum
Phillip Isola

title: Rethinking few-shot image classification: a good embedding is all you need

venue: arXiv preprint arXiv:2003.11539,

authors:
Nilesh Tripuraneni
Chi Jin
Michael I Jordan

title: Provable meta-learning of linear representations

venue: arXiv preprint arXiv:2002.11684,

title: User-friendly tail bounds for sums of random matrices

venue: Foundations of computational mathematics,

title: An introduction to matrix concentration inequalities

venue: arXiv preprint arXiv:1501.01571,

authors:
Kangkang Wang
Rajiv Mathews
Chloé Kiddon
Hubert Eichner
Françoise Beaufays
Daniel Ramage

title: Federated evaluation of on-device personalization

authors:
Tao Yu
Eugene Bagdasaryan
Vitaly Shmatikov

title: Salvaging federated learning by local adaptation

heading: 1 Introduction

text:
Modern machine learning techniques are amazingly successful but come with a range of risks to the privacy of the personal data on which they are trained. Complex models often encode exact personal information in surprising ways—allowing, in extreme cases, the exact recovery of training data from black box use of the model [7, 8]. The emerging architecture of modern learning systems, in which models are trained collaboratively by networks of mobile devices using extremely rich, personal information exacerbates these risks.
The paradigm of model personalization, a special case of multitask learning, has emerged as one way to address both privacy and scalability issues. The idea is to let users train models on their own data—for example, to recognize friends’ and family members’ faces in photos, or to suggest text completions that match the user’s style—based on information that is common to the many other similar learning problems being solved by other users in the system. Even a fairly limited amount of shared information—a useful feature representation or starting set of parameters for optimization, for example—can dramatically reduce the amount of data each user requires. But that shared information can nevertheless be highly disclosive.
In this paper, we formulate a model for reasoning rigorously about the loss to privacy incurred by sharing information for model personalization. In our model, there are n users, each holding a dataset of m labeled examples. We assume user j’s data set Dj is drawn i.i.d. from a distribution Pj ; the user’s goal is to learn a prediction rule that generalizes well to unseen examples from Pj . Ideally, the user should succeed much better than they could have on their own. We give new algorithms for this setting, analyze their accuracy on specific data distributions, and test our results empirically.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We ask that our algorithms satisfy user-level, joint differential privacy (DP) [28] (called task-level privacy, in the context of multi-task learning [32]). In this setting, each user provides their data set Dj as input to the algorithm and receives output Aj = Aj(D1, ..., Dn). We require that for every choice of the other data sets D−j = (D1, ..., Dj−1, Dj+1, ..., Dn) and for every two data sets Dj and D′j , the collective view of the other users A−j be distributed essentially identically regardless of whether user j inputs Dj or D′j . The standard model of differential privacy doesn’t directly fit our setting, since the model ultimately trained by user j will definitely reveal information about user j’s data set. That said, the algorithms we design can ultimately be viewed as an appropriate composition of modules that satisfy the usual notion of DP (an approach known as the billboard model). For simplicity, we describe our algorithms in a centralized model in which the data are stored in a single location, and the algorithm A is run as a single operation. In most cases, we expect A to be run as a distributed protocol, using either general tools such as multiparty computation or lightweight, specialized ones such as differentially private aggregation to simulate the shared platform.
Intuitively, strong privacy requirement at user level, while still demanding that users share some common information is significantly challenging. For one, as each user individually has a small amount of data, it has to share information about it’s model/data to learn a meaningful representation. Furthermore, in practical personalization settings, there is feedback loop between the common or pooled knowledge of all users and the personalized models for each user. That is, starting with reasonable personalized models for each user, leads to a better pooled information, while good pooled information then helps each user learn better personal model. Now, requirement of strong privacy guarantees forces the pooled information quality to degrade up to some extent, which can then lead to poorer personalized model and form a negative feedback loop.

heading: 1.1 Contributions

text:
We consider two types of algorithms for DP model personalization: inefficient algorithms (based on the exponential mechanism [35]) that establish information-theoretic upper bounds on achievable error, and efficient ones based on popular iterative approaches to non-private personalization [40, 26, 51, 52]. These latter approaches are popular for their convergence speed and low communication overhead. As is often the case, those same features make them attractive starting points for DP algorithms.
Problem Setting: Consider a set of n users, and suppose each user j ∈ [n] holds a data set of m records Dj = {(xij , yij)}i∈[m] where xij ∈ R
d, yij ∈ R. The goal is to learn a personalized model fj(·) = f(·; θj) : Rd → R for each user j, where θj is a vector of parameters describing the model. We aim to learn a shared, low-dimensional representation for the features that allows users to train good predictors individually. For concreteness, we consider a linear embedding specified by a d× k matrix U , where k d. We may think of U either as providing a k-dimensional representation of the feature xij (as U>xij) or, alternatively, as a compact way to specify a d-dimensional regression vector θj = Uvj where vj is vector of length k. In both cases, user j’s final predictor has the form
fj(xij) = f ′(〈xij ,Uvj〉) = f ′(〈U>xij ,vj〉)
One may view this as a model as a two-layer neural network, where the first layer is shared across all users and the second layer is trained individually. A useful setting to have in mind is one where k m d—so users do not have enough data to find a good solution on their own, but they do have enough data to find the best vector vj once an embedding U has been specified. Without loss of generality, we assume U ∈ Rd×k to be an orthonormal basis and refer to it as embedding matrix. For brevity, we will define the matrix V = [v1| · · · |vn] ∈ C ⊆ Rk×n with vjs as columns.
Measure of Accuracy: Let LPop(U ;V ) = E(i,j)∼u[m]×[n],(xij ,yij)∼Pj [ ` ( 〈U>xij ,vj〉; yij )] , where the loss function takes the form ` : R × R → R. We will focus on excess population risk defined in (1). The privately learned models are denoted by ( Upriv,V priv ) . The error measures are defined with respect to any fixed choice of parameters (U∗,V ∗).
RiskPop( ( Upriv,V priv ) ; (U∗,V ∗)) = LPop(Upriv,V priv)− LPop(U∗,V ∗). (1)
Alternating Minimization Framework: We develop an efficient framework based on alternating minimization [46, 29, 23]: starting from an initial embedding map U0, the algorithm proceeds in
rounds that alternate between users individually selecting the model v(t)j that minimizes the error of the predictor f ′(〈·,U (t)v(t)j 〉), and then running a DP algorithm, for which user j provides inputs Dj ,v (t) j , to privately select a new embedding U (t+1) that minimizes the error of the predictor f ′(〈·,U (t+1)v(t)j 〉). In both steps, the optimization to be performed is convex when the loss being optimized is convex. This helps us handle the inherent non-convexity in the problem formulation.
Instantiation and Analysis for Linear Regression with Gaussian Data: For the specific case of linear regression with the squared error loss, we show that our framework can be fully instantiated with an efficient algorithm which converges quickly to an optimal solution. For simplicity, we consider the case where the feature vectors and field noise are normally distributed and independent of each user’s “true” model θ∗j , and furthermore that the θ ∗ j vectors admit a common low-dimensional representation

heading: U∗ ∈ Rd×k, so that θ∗j = U

text:
∗v∗j . We show that careful initialization of U0 followed by alternating
minimization converges to a near-optimal embedding as long as m = ω(k2) and n = ω ( k2.5d1.5
ε
) .
Notice that non-privately, one would require n = ω(dk) users to get any reasonable test error. For standard private linear regression in dk dimensions, current state-of-the-art results (Theorem 3.2, [3]) have a sample complexity similar to what we achieve.
Theorem 1.1 (Special case of Theorem 4.2). Suppose the output for point xij ∼ N (0, 1)d of user j is given by yij ∼ 〈(U∗)>xij ,v∗j 〉 +N (0, σ2F) where U
∗ ∈ Rd×k is an orthonormal matrix that describes the shared representation, and suppose v∗j ∼ N (0, 1)k. Let σF ≤ √ k and ε ≤ 1. Then, assuming the number of users n is at least (kd)1.5/ε, and the number of points per user m is at least k2, with high probability Algorithm 1 learns an embedding matrix Upriv such that the average test error of a linear regressor learned over points embedded by Upriv is at most Õ ( d3k5
ε2n2 + σ 2 F · km
) .
Our instantiation of the framework in this case has two major components: The initial embedding U0 is derived from users’ data by a single noisy averaging step which roughly approximates the d× d projector onto the k-dimensional column space of U∗. The idea is that given two data points (xij , yij) and (x(i+1)j , y(i+1)j), the expected value of the rank-one matrix yijy(i+1)jxijx>(i+1)j is (when rescaled) a projector onto the space spanned by the regression vector θj . Adding these rank-one matrices across many data points and users produces a matrix with high overlap with the desired projector U∗(U∗)>. This is similar to the approach taken by [13] to design a non-private algorithm for a related, less general setting.
The DP minimization step, which fixes the vj’s and seeks a near-minimal U , can be performed using any DP algorithm for convex minimization [9, 4]. In this particular case, one can view this step as solving a linear regression problem in which U represents a list of dk real parameters: once x and v are fixed, 〈U>x,v〉 = x>Uv is a linear function of U .
For the analysis to be tractable, we restrict our attention to linear regression with independent, normally-distributed features. However, the framework we provide is more general, and can be applied to a wider class of models. Developing mathematical tools to analyse the behavior of noisy alternating minimization algorithms in more general settings remains an important open question.
Additionally, we run simulations on synthetic data to demonstrate the effectiveness of our proposed algorithm. Our algorithm reaches a significantly better privacy-utility tradeoff compared to two baselines: i) each user uses their own data, and ii) all users jointly learn a single model under differential privacy.
Information-theoretic Upper Bounds: In addition to developing efficient algorithms for particular settings, we give upper bounds on the achievable error of user-level DP model personalization via inefficient algorithms. Specifically, we consider the natural approach of using the exponential mechanism [35] to select a common structure that provides low prediction error on average across users. For the specific case of a shared linear embedding (a generalization of the linear regression setting above), when the feature vectors are drawn i.i.d. from N (0, 1)d, and when the v∗j ’s are drawn i.i.d. from N (0, 1)k, we provide an upper bound showing that n = ω ( k1.5d1.5
ε
) users suffice to learn
a good model, assuming m is sufficiently large for users to train the remaining parameters locally
(Theorem 5.2). In comparison to alternating minimization, the sample complexity is better by a factor of k.
In summary, we initiate a systematic study of differentially private model personalization in the practically important few-shot (or per-user sparse data) learning regime. We propose using users’ data to learn a strong common representation/embedding using differential privacy, that can in turn be used to learn sample efficient models for each user. Using a simple but foundational problem setting, we demonstrate rigorously that this technique can indeed learn accurate common representation as well as personalized models, despite users housing only a small number of data points.

heading: 1.2 Related Work

text:
Personalization Frameworks: Model personalization is a special case of multitask or few-shot learning [10, 25] where the goal is to leverage shared structure amongst multiple tasks to better learn the individual tasks. There are many different frameworks for multi-task learning, each capturing a different kind of shared structure. In the context of model personalization, where tasks correspond to users, two broad approaches stand out.
“Neighboring models”. This approach assumes that while each user learns their own model, all or a fraction of the models are close to each other thus can be learned together [18, 25].
“Common representation”. This approach, which we adopt in this paper, assumes a low-dimensional shared subspace where all points can be represented and now each user/task can learn a sample efficient model to solve the individual task [47, 38]. A common instantiation is a DNN architecture in which the weights in the last layer are user-specific but other weights are shared. Algorithmically, this second approach is more complex since it entails simultaneously finding an accurate representation of data and models building upon those representations. But several studies [38, 47] have shown it to be significantly more effective than other approaches like neighboring models.
Recent works on this approach (e.g. [44, 47, 22, 40]) follow a similar training strategy to ours— that is, they alternatively update the shared representation using gradient descent and then finetune individual classifiers [38, 30, 47]. In particular, the Almost-No-Inner-Loop (ANIL) method by [38] is most similar to the alternating optimization method that we adopt (see Algorithm 1). Theoretical understanding of these methods generally lag significantly behind their empirical success. However, several interesting recent results explain the effectiveness of these methods on simple tasks [13, 46]. Most of the papers in this domain focus on the linear regression problem with a shared lowdimensional representation that we study [46, 11, 48]. They show that one can provide much better estimates for the shared representation, and overall prediction error, by pooling information than would be possible for individual users acting alone. These existing analyses do not allow for noise in the iterations. In fact, for the general problem, the noise can lead to suboptimal solutions. Thus, a key contribution of our work is to show that in a widely studied setting, alternating minimization converges even when the minimization of U is noisy.
Privacy: In our setting, the data set is made up of users’ individual data sets D1, ..., Dn, where each Dj potentially contains many records (labeled training examples). Users interact via a central algorithm, which we assume for simplicity to be implemented correctly and securely (either by a trusted party or using cryptographic techniques like multiparty computation). This algorithm provides output to each of the users. We aim to control what those outputs leak about the users’ input data.
That is, presence/absence of user and its entire data should not affect the outputs significantly. This notion is known as user-level or task-level privacy and has been widely studied in the literature [34, 31], albeit mostly without personalization component. The only works we are aware of that look at personalization (or multitask learning more generally) with user-level guarantees are [19] and [24]. Geyer et al. [19] consider the “neighboring models” approach, which cannot work in the setting we study. Jain et al. [24] consider matrix completion, which can be viewed as a version of our setting in which training examples are limited to indicator vectors (items from a known discrete set).
A few studies attempt to provide only record-level privacy – a significantly weaker notion of privacy where presence/absence of only single record should be undetected by the output of the model. While the notion has been studied extensively for the standard non-personalized models [27, 9], for personalized models the literature is somewhat limited [21, 32]. The work of [32] discusses both taskand record-level privacy, but ultimately provides only algorithms that satisfy the weaker guarantee.
As mentioned above, our goal is to provide strong user-level privacy guarantees so such methods do not apply in our case.

heading: 1.3 Notation

text: We denote all matrices with bold upper case letters (e.g., A), and all vectors with bold lower case letters (a). Unless specified explicitly, all vectors are column vectors. We denote the clipping operation on a vector a as clip (a; ζ) = a ·min { 1, ζ‖a‖2 } .

heading: 2 Background on Privacy

text:
Billboard model: In this paper, we operate in the billboard model [20] of differential privacy [15, 14, 36]. Consider n users, and a computing server. The server runs a differentially private algorithm on sensitive information from the users, and broadcasts the output to all the users. Each user j ∈ [n] can then use the broadcasted output in a computation that solely relies on her data. The output of this computation is not made available to other users. A block schematic is shown in Figure 1. One important attribute of the billboard model is that it trivially satisfies joint differential privacy [28].
User-level privacy protection: In this work, we provide user-level privacy protection [16]. I.e., from the output of the algorithm available to an adversary, they will not be able to detect the presence/absence of all the data samples belonging to a single user. Correspondingly, in the definition of differential privacy below (Definition 2.1), a “record” consists of all the data samples belonging to a single user. Furthermore, we adhere to the replacement model of privacy, where the protection is with respect to the replacement of a user with another, instead of the presence/absence of a user.
Definition 2.1 (Differential Privacy [15, 14, 36]). A randomized algorithm A is (ε, δ)-differentially private if for any pair of data sets D and D′ that differ in one record (i.e., |D4D′| = 1), and for all S in the output range of A, we have
Pr[A(D) ∈ S] ≤ eε ·Pr[A(D′) ∈ S] + δ,
where probability is over the randomness of A. Similarly, an algorithm A is (α, ρ)- Rényi differentially private (RDP) if Dα (A(D)||A(D′)) ≤ ρ, where Dα is the Rényi divergence of order α.

heading: 3 Model Personlization via Private Alternating Minimization

text:
In this section, we first provide a generic/meta algorithm for private model personalization (Algorithm 1 (Algorithm APriv-AltMin)). The main idea is to alternate between two states for T iterations, i.e., for t ∈ [T ], (i) Estimate the best embedding matrix U (t) based on the current personalized models[ v
(t) 1 , . . . ,v (t) n
] while preserving user-level (α, ρ)-
RDP, and (ii) update the personalized modes based on the updated embedding matrix U (t). Finally, output Upriv ← U (T+1), which will be used by each user j ∈ [n] to train her final personalized model vprivj . While Algorithm APriv-AltMin is a fairly natural method for model personalization, to the best of our knowledge, this is the first work that formally studies the privacy/utility trade-offs under user-level privacy. Prior works [40, 37] have used similar ideas in the non-private meta-learning setting. The estimation of the embedding matrix can be implemented by
any differentially private convex optimization algorithm (e.g., DP-SGD [42, 4, 1]). As discussed in Section 4, for specific case of linear regression, we can perturb the sufficient statistics to obtain differential privacy guarantee, and then optimize over it. A similar idea was used in [41, 39].
We provide a formal description in Algorithm 1. In Section 4, we instantiate it in the context of personalized linear regression. There, we also provide formal excess population risk guarantees under
Algorithm 1 APriv-AltMin: Differentially Private Alternating Minimization Meta-algorithm Require: Data sets from each user j ∈ [n]: Dj = {(xij ∈ Rd, yij ∈ R) : i ∈ [m]} for m
mod 4 = 0, rank of the projector: k, privacy parameters: (α, ρ), number of iterations: T , initial rank-k subspace matrix: Uinit, loss function: `.
1: Initialize U (1) ← Uinit. 2: Randomly permute the users j ∈ [n] via permutation π ∼unif [n]. Set j ← π(j),∀j ∈ [n]. 3: for t ∈ [T ] do 4: St ← [ 1 + d (t−1)nT e, d tn T e ] .
5: Each user j ∈ [St] independently solves v(t)j ← arg min ‖v‖2≤Rk 4 m ∑ i∈[m/4] ` ( 〈(U (t))>xij ,v〉; yij ) .
6: Estimate U (t+1) ← arg min U∈K 4 m·|St| ∑ i∈[m/4+1,m/2],j∈St ` ( 〈U>xij ,v(t)j 〉; yij ) under (α, ρ)RDP, where K is the set of all rank-k matrices with orthonormal columns in Rd×k. 7: end for 8: Upriv ← U (T+1).
some data generating assumption. Since Line 6 guarantees (α, ρ)-RDP, and disjoint sets of users are used in each iteration, we can conclude that the whole algorithm guarantees (α, ρ)-RDP.
4 Instantiating Algorithm APriv-AltMin with Linear Regression In this section, we instantiate Algorithm APriv-AltMin (Algorithm 1) in the context of linear regression. While our privacy guarantees hold for any instantiation of the training data, the utility guarantees hold under the following data generating assumption.
Data generation: We instantiate the problem description in Section 1.1 as follows. There is a fixed model v∗j ∈ Rk for each user j ∈ [n], and a fixed rank-k matrix with orthonormal columns U∗ ∈ Rd×k across all users. Let V ∗ := [v∗1| · · · |v∗n]. For each feature vector xij ∈ Rd, the response yij is given by:
yij = 〈(U∗)>xij ,v∗j 〉+ zij , zij ∼ N (0, σ2F). (2)
In Theorem 4.2, we provide the privacy and utility guarantee for an instantiation of Algorithm 1 (Algorithm APriv-AltMin) where the loss function is ` ( 〈U>xij ,v〉; yij ) = ( yij − 〈U>xij ,v〉 )2 .
We will adhere to Assumptions 4.1 for the utility analysis.
Assumption 4.1 (Assumptions for Utility Analysis). Let λi > 0 be the i-th eigenvalue of 1n ( V ∗ (V ∗) > )
, and let µ := max j∈[n] ∥∥v∗j∥∥2 /√kλk be the incoherence parameter. Let Noise-to-signal ratio be NSR = σF√
λk . We assume: (i) ∀i ∈ [m], j ∈ [n],xij ∼iid N (0, 1)d, and corresponding yij be generated using (2), (ii) m = Ω̃ ( (1 + NSR) · k + k2 ) , (iii)
n = Ω̃ ( λ1 λk · µ2dk + ( λ1 λk )2 d k2 · ( NSR2 + µ2k )2 + λ1λk ·∆(ε,δ) · ( NSR2 + µ2k ) d3/2 ) . Here, Ω̃(·)
hides polylog (n,m, k).
Theorem 4.2 (Main Result. Bound on Excess Risk). Let V priv = [vpriv1 , . . . ,vprivn ] with
vprivj ← arg min v∈Rk
2
m ∑ m 2 <i≤m ( yij − 〈(Upriv)>xij ,v〉 )2 .
Let Assumption 4.1 hold. Then, Algorithm APriv-AltMin with parameters in Lemma 4.4 and ∆(ε,δ) :=√ 16 log(1/δ)
ε outputs U priv such that i) it is (ε, δ)-differentially private, and ii) it has the following
excess population risk w.p. at least 1 − 1/n9 (over the randomness of data generation and the
Algorithm 2 Instantiating Line 6 of Algorithm 1 ( Algorithm APriv-AltMin) Require: Set of users at time step t ∈ [T ]: St. Current models: { v (t) j : j ∈ St } , data samples:
{(xij , yij) : j ∈ St, i ∈ [m]}, privacy parameter: ∆(ε,δ), clipping threshold for model: η, clipping threshold for response: ζ. 1: W ij = clip ( # » xijv > j ; η ) and ỹij = clip (yij ; ζ) for all i ∈ [m/4 + 1,m/2], j ∈ St.
2: W priv ← ∑
j∈St,i∈[m/4+1,m/2] W ijW
> ij +Nsym ( 0,m2η4∆2(ε,δ)/4 )dk×dk, and bpriv ←
∑ j∈St,i∈[m/4+1,m/2] ỹijW ij +N ( 0,m2ζ2η2∆2(ε,δ)/4 )dk 3: #» Z(t+1) ← arg min
u∈Rdk
4 m·|St|
( u>W privu− 2u>bpriv ) 4: return U (t+1) ← Q part of the QR-decomposition of Z(t+1)
algorithm): RiskPop( ( Upriv,V priv ) ; (U∗,V ∗)) ≤
= O
( ∆(ε,δ)(σ 2 F + µ 2k2dλk)(µ 4k3d2)
n2 + σ2Fµ 4k2d nm
) · polylog (d, n) + k
m · σ2F.
See supplementary material for the proof.
Remark 1. Let us understand the bound above for a simple setting where the personal model for each user v∗j ∼ N (0, 1)k. Assuming large enough n, this implies that λk ≈ 1 and µ ≈ Õ(1). Now even when V ∗ is known a priori, to obtain a reasonable estimate of U∗, we need to solve the following linear regression problem while ensuring DP: Upriv = min
U
∑ ij(yij − 〈xij(v∗j )>,U〉)2.
Note that xij(v∗j ) > is isotropic. Now, without differential privacy, the information theoretical optimal estimation error is Θ ( σ2F · dknm ) , where dk is the size of the linear regression problem and mn is the number of samples. Now, if we were to solve the above regression problem with DP, the best known algorithm [41] will have an additional error of Õ (( κ · dknε )2) , where κ = σF + maxij ‖xij(v∗j )>‖F · ‖U ∗‖F = Õ(σF + √ dk2). Note that the first two terms in Theorem 4.2
indeed match O (( κ · dknε )2 + σ2F · dknm ) up to an additional factor of k and up to polylog (d, n) factors. Finally, the last error term in the above theorem is due to excess risk in estimating v∗ for a given user with m samples, and is information theoretically optimal.
Remark 2. Under the assumption in Remark 1 and for σF = 0, the sample complexity for Theorem 4.2 is n = ω̃(k2.5d1.5/ε + d) and m = ω̃(k2). Note that, for ε → ∞, the complexity is O(k) worse than the information theoretic optimal. Furthermore, the sample complexity suffers from an additional √ d for constant ε compared to non-private case. Even for standard linear regression, a similar additional √ d factor is present in the sample complexity bound [41]; we leave further investigation into the optimal sample complexity for future work.
In Section 4.1, we show an instantiation of AlgorithmAPriv-AltMin (Algorithm 1) s.t. if the embedding matrix (Uinit) is initialized well, then Upriv ( Upriv )> converges in ‖ · ‖F to U∗(U∗)>. In Section 4.2, we provide an algorithm to obtain a good initialization of the embedding matrix (Uinit). Combining these two results imply Theorem 4.2.

heading: 4.1 Local Subspace Convergence

text:
In Algorithm 2, we instantiate Line 6 of Algorithm APriv-AltMin. For any matrix A ∈ Rd1×d2 , let #»
A ∈ Rd1d2 be the vectorized representation with columns of A placed consecutively. Let Nsym(0, σ2)d×d denote a Wigner matrix with entries drawn i.i.d. from N (0, σ2). The privacy guarantee of Algorithm 2 is presented in Lemma 4.3 and the local subspace guarantee in Lemma 4.4.
Lemma 4.3 (Privacy guarantee). If we set ∆(ε,δ) = √
8 log(1/δ)/ε, then instantiation of Algorithm APriv-AltMin with Algorithm 2 is (ε, δ)-differentially private in the billboard model.
Lemma 4.4 (Local Subspace Convergence). Recall Assumptions 4.1. In Algorithm 2, let model clipping threshold η = Õ(µ √ λkdk), and response clipping threshold ζ = Õ ( σF + µ √ kλk ) . Let the
number of iterations of Algorithm 1 (Algorithm APriv-AltMin) be T = Ω ( log (
(λ1/λk) NSR+∆(ε,δ)
)) . Finally,
assume Uinit be s.t. ‖(I − U∗ (U∗)>)Uinit‖F ≤ λk32λ1 . We have the following for Algorithm 1 (Algorithm APriv-AltMin), instantiated with Algorithm 2, w.p. at least 1− 1/n10 (over the randomness of data generation and the algorithm):
∥∥∥(I−U∗ (U∗)>)Upriv∥∥∥ F = Õ ( ∆(ε,δ)(NSR + µ √ dk2)µ √ k2d2 n + NSR · µ √ kd√ nm ) .
Here, the noise-to-signal-ratio NSR = σF√ λk
and privacy parameter ∆(ε,δ) = √ 8 log(1/δ)
ε . In Õ(·), we hide polylog (d, n).
See supplementary material for the proofs. The analysis of Lemma 4.4 roughly follows the analysis of alternating minimization [46], while accounting for the noise introduced due to privacy. At each iteration, we show that the embedding subspace gets closer in the Frobenius norm, and each of the personalized models gets closer in the `2-norm.

heading: 4.2 Initialization Algorithm

text:
In Algorithm 3, we describe a private estimator for the estimation of U∗. This estimator eventually gets used in initializing the linear regression instantiation of Algorithm 1. We provide the privacy and subspace closeness guarantees in Lemma 4.5 and 4.6, with proofs in supplementary material.
Algorithm 3 APriv-init: Private Initialization Algorithm for Algorithm APriv-AltMin Require: Data sets from each user j ∈ [n]: Dj = {(xij ∈ Rd, yij ∈ R) : i ∈ [m]}, clipping bound
for response: ζ, noise standard dev. for privacy: ∆(ε,δ), and rank of the orthonormal basis: k. 1: W ij ← sym ( x(2i)jx > (2i+1)j
‖x(2i)j‖2·‖x(2i+1)j‖2 · clip
( y(2i)j ; ζ ) · clip ( y(2i+1)j ; ζ )) for all i ∈ [m/2] and j ∈
[n]. Here, sym(W ) makes a matrix ∈Rd×d symmetric by replicating the upper triangle.
2: MNoisy ← 2nm ( ∑ i∈[m/2],j∈[n] W ij +Nsym ( 0,∆2(ε,δ)ζ 4m2 )d×d) . 3: Upriv ← Top-k eigenvectors of MNoisy as columns.
Lemma 4.5 (Privacy guarantee). If we set ∆(ε,δ) = √
8 log(1/δ)/ε, Algorithm 3 (Algorithm APriv-init) is (ε, δ)-differentially private. Lemma 4.6 (Subspace closeness). Recall Assumptions 4.1. Let the clipping bound for response be ζ = Õ(σF + µ √ kλk). We have the following for Algorithm 3 (Algorithm APriv-init) w.p. at least 1− 1/n10:∥∥∥(I−U∗ (U∗)>)Upriv∥∥∥ 2 = Õ ( ∆(ε,δ) ( NSR2 + µ2k ) d3/2 n + (NSR2 + µ2k) √ d√ nm ) .
Here, privacy parameter ∆(ε,δ) = √ 8 log(1/δ) ε . In Õ(·), we hide polylog (d, n).
The proof goes via direct analysis of the distance between the estimated subspace from the training examples, and the true subspace. While the convergence guarantee in Lemma 4.6 is unconditional, it is weaker than Lemma 4.4, especially in its dependence on k and NSR.
Lemma 4.6 implies that under Assumption 4.1, ∥∥∥(I−U∗ (U∗)>)Upriv∥∥∥
F = O
( λk λ1 ) , which
is sufficient to satisfy the initialization condition in Lemma 4.4. Hence, if we initialize U using Algorithm 3 (Algorithm APriv-init) with a disjoint set of samples for each user, it immediately follows that the the local convergence guarantee in Lemma 4.4 is indeed a global convergence guarantee.
Algorithm 4 AExp: Joint Differentially Private ERM via Exponential Mechanism
Require: Data sets from each user j ∈ [n]: Dj = {(xij ∈ Rd, yij ∈ R) : i ∈ [m]} where m mod 2 = 0; model `2-norm constraint C; clipping bound on the projected features Lf ; privacy parameter ε; rank of the projection matrix k; net width φ, loss function ` : R×R→ R; Lipschitz constant ξ of w.r.t. its first parameter.
1: Define a score function for any rank-k matrix with orthonormal columns U ∈ Rd×k as
score (U) = ∑ j∈[n] ( min ‖vj‖2≤C 2 m ∑ i∈[m/2] ` ( 〈clip ( U>xij ;Lf ) ,vj〉; yij )) .
2: Define a net N φ of ‖ · ‖F -radius φ over matrices with orthonormal columns in Rd×k. 3: Sample Upriv ∈ N φ with Pr[Upriv = U ] ∝ exp ( − εn
8LfCξ · score (U)
) .
4: Each user j ∈ [n] independently estimates vprivj ← arg min ‖v‖2≤C 2 m m∑ i=m/2+1 ` ( 〈 ( Upriv )> xij ,v〉; yij ) .

heading: 5 Exponential Mechanism based Model Personalization

text:
In this section, we take a more general approach towards outputting a projector Upriv that approximately minimizes the excess population risk without worrying about actually estimating the projector onto U∗. Here, as we only care about low-excess risk, as opposed to subspace closeness, we can guarantee better convergence under milder assumptions. Recall the loss function LPop(U ,V ) from (1).
We want to optimize min U∈K
( min
V ∈Rd×n,‖vj‖2≤C LPop(U ,V )
) while ensuring ε-DP in the billboard
model. (Here K ∈ Rd×k is the set of matrices with orthonormal columns, and vj corresponds to the j-th column of V .) To that end, we will use the exponential mechanism [35], over an `F -net of radius φ over K. The algorithm is presented in Algorithm 4 (Algorithm AExp). The privacy analysis of AlgorithmAExp follows from the standard analysis of exponential mechanism, and the utility analysis goes via first proving an excess empirical risk bound, and then appealing to uniform convergence to get to excess population risk bound.
Theorem 5.1 (Privacy guarantee). Algorithm 4 is ε-differentially private in the billboard model.
Theorem 5.2 (Utility guarantee). Suppose the loss function ` is ξ-Lipschitz in its first parameter, and C is the bound on the constraint set. Set the net size φ = 1/(εn) and the clipping norm Lf = 40 √ d · log(nm) in Algorithm 4. Assuming ε ∈ (0, 1) and that the feature vectors are drawn i.i.d. from N (0, 1)d, we have (w.p. ≥ 1− 1/min{d, n}10):
RiskPop( ( Upriv,V priv ) ; (U∗,V ∗)) = O ( ξC · ( k · d1.5
εn + √ k√ m
)) · polylog (d, n) .
Here, U∗ and V ∗ are any fixed values of the common embedding matrix (orthonormal, in Rd×k) and matrix of individual regression vectors (in Rn×k, with rows of norm at most C), respectively. See supplementary material for the proofs of Theorems 5.1 and 5.2.
Comparison of the utility guarantee to Theorem 4.2: The utility guarantee for Algorithm AExp (Theorem 5.2) is much more general than that in Theorem 4.2. Unlike Theorem 4.2, it allows arbitrary Lipschitz loss function `, and any distribution over the feature vectors. However, for linear regression with i.i.d. spherical normal feature vectors and setting the diameter of the constraint set C = √ k, one can make Theorems 4.2 and 5.2 comparable. Theorem 4.2 shows an excess population
risk Õ ( k5d3
ε2n2 + k m
) whereas Theorem 5.2 gives Õ (√ k3d3 εn + √ k2 m ) . Theorem 4.2 is tighter in the
regime where n = Ω(k3.5d1.5/ε). This difference is comparable to the so-called fast rates [43]. However, the sample complexity of Theorem 5.2 is better in terms of m by a factor of k1.5.

heading: 6 Numerical Simulation

text:
In this section, we provide numerical simulations to validate our theoretical results. There are three baselines: i) each user solves their problem using their own data without consulting with other
users (called own data), and ii) a single differentially private global model trained on all users data together (called single model), and iii) non-private variant of alternating minimization, trained up to convergence. Overall, we observe that Algorithm 1 (Algorithm APriv-AltMin) outperforms the private baselines by a significant margin.
We consider the linear regression problems on synthetic data and the alternating minimization algorithm 1. We set the number of users n = 50, 000, number of samples per user m = 10, data dimension d = 50 and rank k = 2. We sample x, U and v from Gaussian distributions, and the field noise σF of target y is set to be 0.01. We normalize U to unit norm. We run Algorithm 1 with full batch, i.e., T = 1 and for multiple epochs. The privacy risk will accumulate over epochs, and we use the RDP sequential composition to account for that. We fix the clipping norm to be 10−4 and pick the optimal the number of epochs in {1, 2, 5, 10}. In Figure 2, we fix δ = 10−6 and plot the population mean squared error (MSE) computed based on the groundtruth model for multiple ε. As a reference, the MSE for a purely random model is around 4. In addition to (ε, δ)-differential privacy, we also report the value of Zero-Concentrated Differential Privacy (zCDP) [5], as it better captures the privacy properties, especially for Gaussian mechanism based algorithms. The definition can be found at Appendix A. In particular, privacy parameter ε = {1, 2, 5, 10} corresponds to 0.009, 0.04, 0.23, 0.90-zCDP, respectively. We observe that at ε ≈ 5, the population MSE for Algorithm 3 is comparable to the non-private baseline. In contrast, the error for the single model baseline remains very high, even at high values of ε.

heading: 7 Conclusion

text:
In this paper we studied the problem of personalized supervised learning with user-level differential privacy. Through our framework and Algorithm 1, we demonstrated that we can indeed learn accurate shared linear representation of the data, despite a limited number of samples-per-user and while preserving each user’s privacy. Our error bounds and sample complexity bounds are nearly optimal in key parameters and are in fact, comparable to the best known bounds available for a much simpler linear regression problem.
This work leads to several interesting questions: (i) In our model, can we provide similar privacy/utility trade-offs for deep networks based embedding functions instead of a linear embedding function, (ii) Can we make a variant of the exponential mechanism algorithm computationally feasible?, and (iii) Empirically validate the privacy/utility trade-offs on real world data sets.
As more and more ML models are personalized for user tastes, ensuring privacy of individuals’ data is paramount to a fair, responsible system. We provide a rigorous framework to design such solutions, which hopefully will motivate practitioners and researchers to make privacy as a first class citizen while designing their personalization based ML system.
Acknowledgements and Funding Disclosure We would like to thank Brendan McMahan, and Daniel Ramage for various helpful discussions during the course of this project. Adam Smith was supported in part by NSF award CCF-1763786 as well as a Sloan Foundation research award and a Google Faculty Research Award.

title: Differentially Private Model Personalization