Search papers, labs, and topics across Lattice.
This paper addresses the challenge of polynomial approximation for non-polynomial activation functions in homomorphic encryption by formulating a distribution-aware interval optimization problem that minimizes mean-squared error (MSE). By combining minimax polynomial approximations with domain extension functions (DEFs) and their homomorphic counterparts (domain extension polynomials or DEPs), the authors effectively manage the trade-off between approximation accuracy within a specified interval and error control for inputs outside that interval. The key result is an analytically tractable DEF-based proxy objective that links the minimax approximation error to the clipping error, providing a robust framework for optimizing polynomial approximations in privacy-preserving computations.
Optimizing polynomial approximations in homomorphic encryption can significantly enhance the accuracy of privacy-preserving neural network inference.
Homomorphic encryption (HE) enables privacy-preserving inference under arithmetic constraints that restrict encrypted evaluation to additions and multiplications. As a result, non-polynomial activation functions must be replaced by polynomial approximations. Among polynomial approximation methods, minimax approximation, typically computed by the Remez algorithm, is a standard approach because it minimizes the maximum approximation error over a given design interval. For minimax polynomial design, the approximation interval is a critical hyperparameter: a wider interval improves robustness to large-magnitude inputs while increasing the minimax approximation error under a fixed degree budget. In this paper, we formulate this trade-off as a distribution-aware interval optimization problem, where the approximation interval is chosen to minimize the mean-squared error (MSE) with respect to the pre-activation distribution of interest. To effectively control outside-interval inputs, we combine minimax polynomials with domain extension functions (DEFs) and their HE-realizable polynomial counterparts, domain extension polynomials (DEPs), which approximate a clipping operation outside the design interval and thereby suppress uncontrolled polynomial extrapolation. We first derive an analytically tractable DEF-based proxy objective that captures the trade-off between within-interval minimax approximation error and outside-interval clipping error. We then connect this idealized objective to HE-realizable DEP constructions through an implementation-error decomposition with an accompanying upper bound.
