Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
2026-05-11 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to do optimization tasks when users want to keep their labels private but agree to share features openly. Previous research showed that the error in such optimizations grew linearly with the number of label types, making it costly for many labels. The authors propose a new method that reduces this error growth to the square root of the number of labels, which is a big improvement. They also prove that this improvement is the best possible under the privacy rules they use.
Stochastic Convex OptimizationLocal Differential PrivacyLabel PrivacyExcess RiskPrivacy RegimesNon-interactive AlgorithmsInformation-theoretic Lower BoundsHigh-privacy regimeMedium-privacy regime
Authors
Lynn Chua, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Ziteng Sun, Chiyuan Zhang
Abstract
We study the problem of Stochastic Convex Optimization (SCO) under the constraint of local Label Differential Privacy (L-LDP). In this setting, the features are considered public, but the corresponding labels are sensitive and must be randomized by each user locally before being sent to an untrusted analyzer. Prior work for SCO under L-LDP (Ghazi et al., 2021) established an excess population risk bound with a \emph{linear} dependence on the size of the label space, $K$: $O\left({\frac{K}{ε\sqrt{n}}}\right)$ in the high-privacy regime ($ε\leq 1$) and $O\left({\frac{K}{e^ε \sqrt{n}}}\right)$ in the medium-privacy regime ($1 \leq ε\leq \ln K$). This left open whether this linear cost is fundamental to the L-LDP model. In this note, we resolve this question. First, we present a novel and efficient non-interactive L-LDP algorithm that achieves an excess risk of $O\left({\sqrt{\frac{K}{εn}}}\right)$ in the high-privacy regime ($ε\leq 1$) and $O\left({\sqrt{\frac{K}{e^ε n}}}\right)$ in the medium-privacy regime ($1 \leq ε\leq \ln K$). This quadratically improves the dependency on the label space size from $O(K)$ to $O(\sqrt{K})$. Second, we prove a matching information-theoretic lower bound across all privacy regimes for any sufficiently large $n$.