## Abstract

As one of the most fundamental problems in machine learning, statistics and differential privacy, Differentially Private Stochastic Convex Optimization (DP-SCO) has been extensively studied in recent years. However, most of the previous work can only handle either regular data distributions or irregular data in the low dimensional space case. To better understand the challenges arising from irregular data distributions, in this paper we provide the first study on the problem of DP-SCO with heavy-Tailed data in the high dimensional space. In the first part we focus on the problem over some polytope constraint (such as the l1-norm ball). We show that if the loss function is smooth and its gradient has bounded second order moment, it is possible to get a (high probability) error bound (excess population risk) of Õ(log d/(n?)1/3) in the ?-DP model, where n is the sample size and d is the dimension of the underlying space. Next, for LASSO, if the data distribution has bounded fourth-order moments, we improve the bound to Õ(log d/(n?)2/5) in the $(?)-DP model. In the second part of the paper, we study sparse learning with heavy-Tailed data. We first revisit the sparse linear model and propose a truncated DP-IHT method whose output could achieve an error of Õ ((s*2 log2d)/n?), where s*is the sparsity of the underlying parameter. Then we study a more general problem over the sparsity (i.e., l0-norm) constraint, and show that it is possible to achieve an error of Õ((s*3/2 log d)/n?), which is also near optimal up to a factor of Õ(gs*), if the loss function is smooth and strongly convex.

Original language | English (US) |
---|---|

Title of host publication | PODS 2022 - Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |

Publisher | Association for Computing Machinery |

Pages | 227-236 |

Number of pages | 10 |

ISBN (Electronic) | 9781450392600 |

DOIs | |

State | Published - Jun 12 2022 |

Event | 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2022 - Philadelphia, United States Duration: Jun 12 2022 → Jun 17 2022 |

### Publication series

Name | Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems |
---|

### Conference

Conference | 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2022 |
---|---|

Country/Territory | United States |

City | Philadelphia |

Period | 06/12/22 → 06/17/22 |

### Bibliographical note

Publisher Copyright:© 2022 ACM.

## Keywords

- differential privacy
- high dimensional statistics
- robust statistics
- stochastic convex optimization

## ASJC Scopus subject areas

- Software
- Information Systems
- Hardware and Architecture