A Near-Optimal Algorithm for Differentially Private Zeroth-Order Non-Smooth Convex ERM with Deterministic Query Complexity

We address a fundamental open problem in zeroth-order differentially private (DP) empirical risk minimization (ERM) for non-smooth (strongly) convex functions: whether optimal utility can be achieved with a \textit{deterministic} number of function evaluation queries. Prior approaches, while attaining optimal utility guarantees, rely on expected function evaluation query complexity, leaving the question of achieving optimal utility with deterministic number of queries unresolved. In this work, we provide the first affirmative answer by introducing a novel algorithmic framework that achieves near-optimal error—up to logarithmic factors—within a deterministic query budget. Our method extends recent advances in first-order DP techniques for non-smooth ERM to the zeroth-order setting. A central technical contribution of our work is a new privacy analysis for randomized finite difference estimators, which underpins our ability to design zeroth-order algorithms with both strong privacy and utility guarantees in deterministic time.