💻 computer science

Degree-Constrained Interval Optimization for Minimax Polynomial Approximation in Homomorphic Encryption

This paper proposes a distribution-aware interval optimization framework for minimax polynomial approximation in homomorphic encryption that balances within-interval error and outside-interval clipping by combining domain extension functions with their polynomial counterparts to minimize mean-squared error under degree constraints.

Original authors: Jiheon Woo, Donggyun Ryu, Yongjune Kim

Published 2026-07-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiheon Woo, Donggyun Ryu, Yongjune Kim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message to a friend using a magical lockbox. This lockbox, called Homomorphic Encryption, is amazing because it lets you do math on the locked box without ever opening it. You can add numbers and multiply them, and when you finally unlock the result, it's correct! But there's a catch: this magic lockbox only understands simple math (addition and multiplication). It gets confused by "curvy" functions like the ones neural networks use to make decisions (things like Sigmoid or ReLU).

To fix this, scientists usually replace those curvy functions with polynomials—think of them as smooth, wiggly lines made of straight sticks glued together. The goal is to make these wiggly lines hug the curvy function as tightly as possible.

The "Goldilocks" Problem: Too Big, Too Small, or Just Right?

The tricky part is deciding where to make the hug tightest.

In the past, researchers used a method called Minimax Approximation (often calculated by the Remez algorithm). Imagine you are stretching a rubber band over a mountain range. The Minimax method tries to stretch the rubber band so that the highest point of the gap between the band and the mountain is as small as possible.

But here is the problem: How wide should the mountain range be?

If you make the range too narrow, the rubber band hugs the mountain perfectly in the middle, but if a hiker (your data) wanders outside that range, the rubber band shoots off into the sky, creating a massive error.
If you make the range too wide, the rubber band stays safe for hikers who wander far, but it becomes loose and sloppy in the middle where most hikers actually are.

The paper argues that simply picking a "safe" wide range (like the old way) is a bad idea because it makes the math sloppy where it matters most. Instead, the authors suggest we should pick the perfect width based on where the hikers are most likely to be.

The New Strategy: A Smart Fence and a Safety Net

The authors propose a new way to find this perfect width. They treat the width not as a fixed rule, but as a variable to be optimized. They ask: "If we know the probability of hikers being at different spots, what width gives us the lowest average error?"

To handle the hikers who do wander outside the perfect zone, they use a clever trick involving Domain Extension Functions (DEFs) and their polynomial cousins, Domain Extension Polynomials (DEPs).

Think of the DEF as a smart fence. Inside the fence, the rubber band hugs the mountain perfectly. Outside the fence, instead of letting the rubber band fly off into chaos, the fence gently clips the hiker's path, keeping them from falling off the edge. The DEP is the mathematical version of this fence that the magic lockbox can actually understand.

What They Found (The "Aha!" Moment)

The team did some heavy math and computer simulations to test this idea. Here is what they discovered:

The Sweet Spot Exists: They found that for every type of "curvy" function (like ReLU, Sigmoid, Tanh, and GELU), there is a specific "sweet spot" width that minimizes the average error. This sweet spot is usually much smaller than the super-wide, conservative ranges people used to use.
The "Proxy" Works: Calculating the perfect width is hard. So, they created a simplified mathematical shortcut (a "proxy") that guesses the right width. In their simulations, this shortcut was incredibly accurate, finding the exact same sweet spot as the complex, perfect calculation.
Huge Gains for Some Functions: When they tested this on real-world activation functions, the results were striking.
- For Sigmoid, Tanh, and GELU, the new method reduced the error by several orders of magnitude compared to the old, wide-range method. That's like going from a blurry photo to a crystal-clear 4K image.
- For ReLU, it also improved the accuracy significantly, though the gains were slightly less dramatic than the others.

What They Didn't Do (And What They Ruled Out)

It is important to know what this paper doesn't claim:

It's not a magic fix for everything: The paper explicitly rules out the idea that you can just make the interval wider and wider to solve all problems. They show that a wider interval actually increases the error inside the region where most data lives.
It's not a proven "win" in a real-world network yet: The results shown are based on numerical experiments and simulations using specific mathematical models (like Gaussian and Laplace distributions). They have not yet tested this on a full, live neural network running on a real server with real user data. They suggest this is the next step, but they haven't done it yet.
It doesn't solve the "noise" problem: The paper acknowledges that Homomorphic Encryption is still limited by "noise" (mathematical fuzziness that builds up). While their method makes the approximation better, it doesn't magically remove the need to manage the noise budget; it just makes the polynomial approximation more efficient within that budget.

The Bottom Line

The authors have built a smart ruler for measuring how wide your approximation zone should be. Instead of guessing or playing it safe with a giant zone, this ruler looks at where your data is likely to be and picks the perfect size.

In their simulations, this approach showed that by using a Domain Extension Polynomial (a safety net) combined with an optimized interval, you can get much more accurate results than the old "one-size-fits-all" wide intervals. For functions like Sigmoid and Tanh, the improvement is massive, suggesting that this method could make privacy-preserving AI much more practical in the future.

The paper concludes that while the math is solid and the simulations look great, the real test will be integrating this into full-scale encrypted neural networks, a challenge they leave for future explorers.

Technical Summary: Degree-Constrained Interval Optimization for Minimax Polynomial Approximation in Homomorphic Encryption

Problem Statement
In Homomorphic Encryption (HE)-based Privacy-Preserving Machine Learning (PPML), neural network inference must be performed on encrypted data using only arithmetic operations (addition and multiplication). Consequently, non-polynomial activation functions (e.g., ReLU, sigmoid, tanh, GELU) must be replaced by polynomial approximations. The standard approach, minimax approximation (computed via the Remez algorithm), minimizes the worst-case error over a specific design interval $[-t, t]$ .

However, a critical trade-off exists in selecting the design interval $t$ under a fixed polynomial degree budget:

Wider Intervals: Improve coverage of large-magnitude inputs but increase the minimax approximation error within the interval.
Narrower Intervals: Reduce the minimax error within the interval but increase the risk of "uncontrolled extrapolation" for inputs falling outside the interval. In HE, where intermediate plaintext values are unobservable, such extrapolation errors can be amplified thousands of times, severely degrading inference accuracy.

While Domain Extension Functions (DEFs) and their polynomial counterparts, Domain Extension Polynomials (DEPs), have been proposed to clip inputs outside the design interval and prevent uncontrolled extrapolation, the optimal design interval $t$ itself remains a hyperparameter that must be tuned. Existing methods often rely on conservative, fixed intervals (e.g., $[-20\sigma, 20\sigma]$ ), which may not minimize the overall error for a specific input distribution.

Methodology
The paper formulates the selection of the approximation interval $[-t, t]$ as a distribution-aware optimization problem. The goal is to choose $t$ to minimize the Mean Squared Error (MSE) with respect to the pre-activation input distribution $X$ .

Idealized Objective (DEF-based):
The authors define an ideal objective $J_{DEF}(t)$ based on a non-polynomial hard-clipping map $D_t(x)$ . This objective decomposes the total MSE into:
- Within-interval term: The error of the minimax polynomial $p_{n,t}$ on $[-t, t]$ .
- Outside-interval term: The error incurred when inputs are clipped to the boundaries $\pm t$ .
To make this analytically tractable, the authors derive a proxy objective $\hat{J}_{DEF}(t)$ :
- Within-interval approximation: They model the residual distribution of minimax polynomials using the arcsine law, justified by the equioscillation property of minimax solutions. This allows the conditional second moment of the error to be approximated as $E_n(t)^2 / 2$ , where $E_n(t)$ is the minimax error.
- Outside-interval approximation: They substitute the polynomial endpoint values with the target function's endpoint values to create a closed-form surrogate for the clipping error.
Handling Activation Types:
- Homogeneous Functions (ReLU, LeakyReLU): For these, the minimax error scales linearly with the interval radius ( $E_n(t) = t E_n(1)$ ). This allows for an exact analytical derivation of the optimal normalized radius $\alpha^* = t^*/\sigma$ via a first-order condition involving the standard normal PDF and CDF.
- Non-Homogeneous Functions (Sigmoid, Tanh, GELU): Since no simple scaling law exists, the authors numerically sample the minimax error curve $E_n(t)$ over a grid of radii and fit a smooth polynomial surrogate. This surrogate is then used within the proxy objective to find the optimal $t$ .
HE-Realizable Implementation (DEP-based):
Since the ideal hard-clipping map is non-polynomial, the framework connects the ideal analysis to HE-realizable constructions using Domain Extension Polynomials (DEPs).
- A composition of scaled DEP stages maps a conservative input range $[-R_0, R_0]$ into the design interval $[-t, t]$ .
- The authors derive an implementation-error decomposition and an upper bound ( $U_{impl}$ ) that quantifies the gap between the ideal DEF objective and the practical DEP realization. This bound accounts for the near-identity error within the preservation region and the bounded error for inputs in the extended region.

Key Contributions

Principled Formulation: The paper provides the first principled formulation of interval optimization for degree-constrained minimax polynomial approximation, explicitly minimizing MSE over the pre-activation distribution rather than using fixed, conservative intervals.
Analytically Tractable Proxy: The authors derive a DEF-based proxy objective that captures the trade-off between within-interval minimax error and outside-interval clipping error. This proxy utilizes the arcsine distribution model for residuals and endpoint-value substitution for clipping errors.
Error Decomposition and Bounds: The work establishes a rigorous connection between the ideal DEF analysis and HE-realizable DEP constructions, providing an upper bound on the MSE gap induced by replacing the ideal clipping function with polynomial compositions.
Numerical Validation: The paper validates the framework on representative activation functions (ReLU, LeakyReLU, Sigmoid, Tanh, GELU) under Gaussian and Laplace input distributions.

Results
Numerical experiments demonstrate that the proposed interval optimization significantly outperforms conventional fixed-interval minimax baselines (e.g., using $[-20\sigma, 20\sigma]$ ):

MSE Reduction: The optimized approach achieves substantially lower MSE. The gains are particularly pronounced for sigmoid, tanh, and GELU, where the MSE is reduced by several orders of magnitude compared to the fixed-interval baseline.
Proxy Accuracy: The minimizer of the analytical proxy $\hat{J}_{DEF}(t)$ closely matches the minimizer of the numerically evaluated ideal objective $J_{DEF}(t)$ across all tested functions, validating the surrogate's utility for interval selection.
DEP Performance: Practical DEP-based evaluators achieve lower MSE than the fixed-interval baseline. The experiments also reveal a trade-off in DEP design: a larger extension factor ( $L=2.5$ ) reduces the number of required stages and accumulated composition error, yielding better practical MSE than a smaller factor ( $L=1.6$ ) in the tested settings, despite the latter being closer to ideal clipping per stage.

Significance and Claims
The paper claims that treating the approximation interval as an optimization variable, rather than a fixed hyperparameter, is essential for maximizing the accuracy of HE-based inference under degree constraints. By balancing the minimax error within the interval against the clipping error outside it, the proposed framework enables more accurate inference without increasing the polynomial degree or multiplicative depth.

The authors position this work as a foundational step for end-to-end HE-based neural network inference. They note that future work should investigate the integration of this framework into full network pipelines, considering the interplay of layer-wise distributions and cumulative errors, as well as specific cryptographic library implementation costs. The paper does not claim to solve the entire PPML problem but offers a specific, analytically grounded method to optimize a critical component (polynomial approximation intervals) that directly impacts inference accuracy.