The importance of feature preprocessing for differentially private linear optimization Article Swipe

MAKE IMPACT

Ziteng Sun , Ananda Theertha Suresh , Aditya Krishna Menon · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2307.11106

Training machine learning models with differential privacy (DP) has received increasing interest in recent years. One of the most popular algorithms for training differentially private models is differentially private stochastic gradient descent (DPSGD) and its variants, where at each step gradients are clipped and combined with some noise. Given the increasing usage of DPSGD, we ask the question: is DPSGD alone sufficient to find a good minimizer for every dataset under privacy constraints? Towards answering this question, we show that even for the simple case of linear classification, unlike non-private optimization, (private) feature preprocessing is vital for differentially private optimization. In detail, we first show theoretically that there exists an example where without feature preprocessing, DPSGD incurs an optimality gap proportional to the maximum Euclidean norm of features over all samples. We then propose an algorithm called DPSGD-F, which combines DPSGD with feature preprocessing and prove that for classification tasks, it incurs an optimality gap proportional to the diameter of the features $\max_{x, x' \in D} \|x - x'\|_2$. We finally demonstrate the practicality of our algorithm on image classification benchmarks.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2307.11106

PDF

https://arxiv.org/pdf/2307.11106

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4385208618

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4385208618

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2307.11106

Digital Object Identifier

Title

The importance of feature preprocessing for differentially private linear optimization

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2023

Year of publication

Publication date

2023-07-19

Full publication date if available

Authors

Ziteng Sun, Ananda Theertha Suresh, Aditya Krishna Menon

List of authors in order

Landing page

https://arxiv.org/abs/2307.11106

Publisher landing page

PDF URL

https://arxiv.org/pdf/2307.11106

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2307.11106

Direct OA link when available

Concepts

Preprocessor, Feature (linguistics), Differential privacy, Stochastic gradient descent, Computer science, Artificial intelligence, Gradient descent, Norm (philosophy), Euclidean distance, Euclidean geometry, Pattern recognition (psychology), Optimization problem, Algorithm, Mathematics, Artificial neural network, Law, Geometry, Philosophy, Political science, Linguistics

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload