  Privacy concern has been increasingly important in many machine learning (ML)
problems. We study empirical risk minimization (ERM) problems under secure
multi-party computation (MPC) frameworks. Main technical tools for MPC have
been developed based on cryptography. One of limitations in current
cryptographically private ML is that it is computationally intractable to
evaluate non-linear functions such as logarithmic functions or exponential
functions. Therefore, for a class of ERM problems such as logistic regression
in which non-linear function evaluations are required, one can only obtain
approximate solutions. In this paper, we introduce a novel cryptographically
private tool called secure approximation guarantee (SAG) method. The key
property of SAG method is that, given an arbitrary approximate solution, it can
provide a non-probabilistic assumption-free bound on the approximation quality
under cryptographically secure computation framework. We demonstrate the
benefit of the SAG method by applying it to several problems including a
practical privacy-preserving data analysis task on genomic and clinical
information.
