Differentially private learning beyond the classical dimensionality regime (Q7233236)

This interesting paper concens differentially private learning beyond the classical dimensionality regime. To gain some perspective, it is well known that there are many limitations of classical statistical theory for modern high-dimensional supervised learning problems. To give a typical example, in genomics, neuroscience, image data and many other applications from various domains, the dimensionality \(d\) of the data is often larger than \(n\) the number of points and there are many well statistics techniques to address these challenges, for example the entire area of manifold learning and many others. In the paper under review, the authors study differentially private learning in the proportional dimensionality regime, in which the number of data samples \(n\) and problem dimension \(d\) approach infinity at rates proportional to one another. What this means is that \( d/n\to\varepsilon\) for large enough \(n\). The key is that \(\varepsilon\) is a given constant in the interval \((0,\infty)\). Note that unlike many previous works where \(\varepsilon\) is positive and small enough the much weaker assumption on \(\varepsilon\) makes the problem significally harder.\N\NThe authors in particular, provide sharp theoretical estimates of the error of several well known differentially private algorithms for robust linear regression and logistic regression, including output perturbation, objective perturbation, and noisy stochastic gradient descent, in the proportional dimensionality regime. They also discover and provide many new observations not known before. See the paper under review for more details. \N\NThe paper is well written with a good set of references.\N\NFor the entire collection see [Zbl 08152620].