Noise-Augmented Privacy-Preserving Empirical Risk Minimization with
  Dual-purpose Regularizer and Privacy Budget Retrieval and Recycling
  We propose Noise-Augmented Privacy-Preserving Empirical Risk Minimization
(NAPP-ERM) that solves ERM with differential privacy guarantees. Existing
privacy-preserving ERM approaches may be subject to over-regularization with
the employment of an l2 term to achieve strong convexity on top of the target
regularization. NAPP-ERM improves over the current approaches and mitigates
over-regularization by iteratively realizing target regularization through
appropriately designed augmented data and delivering strong convexity via a
single adaptively weighted dual-purpose l2 regularizer. When the target
regularization is for variable selection, we propose a new regularizer that
achieves both privacy and sparsity guarantees simultaneously. Finally, we
propose a strategy to retrieve privacy budget when the strong convexity
requirement is met, which can be returned to users such that the DP of ERM is
guaranteed at a lower privacy cost than originally planned, or be recycled to
the ERM optimization procedure to reduce the injected DP noise and improve the
utility of DP-ERM. From an implementation perspective, NAPP-ERM can be achieved
by optimizing a non-perturbed object function given noise-augmented data and
can thus leverage existing tools for non-private ERM optimization. We
illustrate through extensive experiments the mitigation effect of the
over-regularization and private budget retrieval by NAPP-ERM on variable
selection and prediction.
