The Convex Geometry of Private Selection

Many private learning systems spend their privacy budget on a winner, adding noise to a vector of scores and publishing the candidate with the largest noisy score. For every log-concave noise and every polytope of candidates we prove that the exact pure privacy of this mechanism is the largest change that an allowed score shift makes on one convex set of the noise, its privacy body, inside the tangent cones of the polytope. The exponential mechanism and permute-and-flip have the same body and hence exactly the same privacy on every readout, and the cone identity behind this result shows that the standard calibrations of the sparse vector technique are exact for long streams. Calibrating a noise thus becomes choosing a body. After the argmax, the K-norm noise that is optimal for releasing the scores has the largest expected spread among the K-norm noise distributions whose bodies are feasible and contain its body. On selection with abstention and on assignment, mechanisms already in use attain the optimal worst-case regret at high privacy, up to a constant factor.