Some learning problems have two nested levels. An outer choice, such as how much to trust each training example, is judged by how well an inner model trained under that choice performs. These are bilevel problems. Their most useful applications, such as cleaning mislabeled data or tuning many regularizers at once, often involve data that owners will not reveal. Fully homomorphic encryption (FHE) lets a server compute directly on encrypted numbers, but only through additions and multiplications, and each chained multiplication adds noise to the ciphertext. Once the chain of multiplications, called the multiplicative depth, exceeds a budget fixed in advance, the result decrypts to garbage. The server can then only continue by bootstrapping, an expensive re-encryption that dominates running time. So the cost that matters for encrypted bilevel optimization is total multiplicative depth to reach a given accuracy, not the gradient-call count that plaintext complexity theory tracks. Because an encrypted program cannot test "have I converged?", both the iteration count and the penalty settings must be fixed before the data is ever seen.
We propose to treat total depth as the complexity measure. We run a single-loop value-function penalty method with a fixed, budget-chosen penalty weight. A penalty method folds the inner problem into the outer objective as an extra cost term, so no nested solve is needed. We derive the depth-optimal penalty weight and iteration count in closed form. Every quantity the encrypted circuit needs can then be computed in plaintext beforehand, together with an a priori guarantee on output quality. The test case is encrypted hyper-data cleaning, where the server learns one trust weight per training example. That upper-level variable is far too large for grid search, and it is the standard plaintext benchmark for penalty bilevel methods.
Core Claim
The method builds on the penalty reformulation analyzed by Kwon et al.:
$$\psi_\sigma(x,y,z) = f(x,y) + \tfrac{1}{\sigma}\big[g(x,y) - g(x,z)\big] + p(x).$$
Here $x$ holds the per-example weights, $y$ is the model trained with the penalty pulling it toward lower-level optimality, and $z$ is a second copy of the model tracking the lower-level minimizer. The function $f$ is the loss on a small clean validation set, and $g$ is the weighted training loss. The weight $\sigma>0$ sets how softly lower-level optimality is enforced, and $p$ is a fixed-degree polynomial penalty keeping each weight near $[0,1]$.
Each iteration takes one gradient step in each of $x$, $y$, $z$. Every gradient is first-order and polynomial when the losses are polynomial, so there is no Hessian, no inner minimization, and no projection. Kwon et al. show that the gradient of the penalized objective is $O(\sigma)$-close to the true hypergradient. The penalized objective's smoothness constant grows like $1/\sigma$, so the safe step size shrinks like $\sigma$. Standard nonconvex gradient descent after $N$ steps therefore reaches stationarity error about $(\sigma N)^{-1/2}$, and the total error behaves like
$$\mathrm{err}(\sigma,N) \approx C_1\,\sigma + C_2\,(\sigma N)^{-1/2} + C_3\,N\,\eta_{\mathrm{enc}},$$
where $\eta_{\mathrm{enc}}$ is the per-step approximation error introduced by encrypted arithmetic in CKKS, the FHE scheme for approximate real-number arithmetic. Setting the first two terms equal gives $\sigma^\star \propto N^{-1/3}$ and error $\propto N^{-1/3}$. That inverts to $N \propto \epsilon^{-3}$, which matches the deterministic $O(\epsilon^{-3})$ rate of Kwon et al. Under encryption, $N = L_{\mathrm{tot}}/d$, where $d$ is the depth one iteration consumes and $L_{\mathrm{tot}}$ is the total depth available across bootstraps. The claim is therefore concrete. For a given depth budget, one should neither drive $\sigma\to 0$ as plaintext practice suggests, nor grow the penalty degree over iterations as Schlor et al. do. One should instead fix $\sigma$ from the budget, which minimizes the number of bootstraps needed to reach a target validation loss. The accompanying theorem also gives an explicit bound on output quality for a given $N$. That bound is exactly what an encrypted computation needs, because it cannot stop early.
Relation to Prior Work
Three plaintext penalty methods motivate the design, and each is ruled out as-is by depth. The method of Mehra & Hamm penalizes the squared norm of the lower-level gradient. Its outer gradient then needs mixed second derivatives, roughly doubling per-step depth. The minimax formulation of Lu & Mei and the three-layer smoothed Lagrangian of SLM need proximal steps, max-updates, or dual-variable scaling that are not polynomial. Kwon et al. supply our formulation. Their analysis uses Moreau envelopes, an inner minimization we avoid by tracking $z$ with plain gradient steps; that is safe here because our lower levels are strongly convex. Their constants are stated for oracle calls, not depth.
On the encryption side, the constraining evidence comes from two papers. Schlor et al. show that polynomial penalties make constrained optimization run natively under FHE. Their penalties grow in degree across iterations, which conflicts with a fixed depth budget, and their method stays single-level. Zhou et al. show that replacing a non-polynomial operation with a penalty term cut per-iteration depth from 24 to 9 and gave 3–5x speedups. This is the strongest evidence that algorithm-level depth reduction beats relying on bootstrapping, but their setting is single-level convex training. Esperança et al. supply two design rules we reuse. Gradient descent has depth independent of dimension while coordinate descent does not, and the van Wijngaarden series transformation accelerates convergence for one extra level in total, whereas Nesterov momentum costs a level per step. We add bilevel structure, fixed-degree penalties, and a depth-indexed theory.
Research Program
The first part is analysis. We make the error display above rigorous for weighted least squares and weighted polynomial-logistic lower levels, both strongly convex in the model. The analysis must track the coupled errors of the two inner copies $y$ and $z$, the bias from the soft box penalty of fixed degree $2m$, and CKKS approximation error treated as an inexact-gradient perturbation. The output is a plaintext calculator. Given dataset size, dimension, bounds on the data, and the CKKS parameters, it returns $\sigma^\star$, the step sizes, $N$, the bootstrapping schedule, and a certified bound on the final hypergradient norm.
The second part is circuit design. We compile one iteration so that the weights $x_i$ multiply per-example residuals only once, packed across ciphertext slots, and we measure the per-iteration depth $d$ exactly. A secondary question is whether a single van Wijngaarden transform applied to the fast lower-level copies $y,z$ shortens $N$ at a cost of one level. Esperança et al. established that effect only for single-level regression.
The third part is an encrypted implementation. It uses CKKS with parameter sets from the Homomorphic Encryption Standard at 128-bit security, and optionally GPU acceleration via cuHE.
Baselines
The do-nothing reference trains the model on the noisy data with uniform weights, encrypted in the style of Zhou et al., under the same CKKS parameters. It shows how much cleaning buys, and it is the cheapest in depth.
The plaintext ceiling runs SLM and the Kwon et al. penalty method to convergence on the same features and model class. For orientation, SLM reports 90.44% test accuracy on MNIST hyper-cleaning with 50% label noise, against 88.1% for V-PBGD (SLM). Those numbers use a neural model on full MNIST, so we rerun both methods on our reduced-feature setup instead of comparing to them directly.
The strongest encrypted competitor is one-step unrolled reweighting. The server takes one inner gradient step and differentiates the validation loss through it with respect to $x$. For per-example weights this hypergradient is cheap and polynomial. It is myopic and has no convergence guarantee, but it may work well in practice, so it is the method to beat. It will run with the identical circuit toolkit, the same depth budget and bootstrapping allowance, and a tuning grid of equal size over its step sizes chosen on plaintext surrogate data, as ours is.
Ablations isolate the key ingredients at matched total depth. The first replaces the value-function penalty with the gradient-norm penalty of Mehra & Hamm. The second replaces the fixed-degree box penalty with the growing-degree schedule of Schlor et al. The third replaces the budget-derived $\sigma^\star$ with a small plaintext-tuned $\sigma$.
Beating a baseline means reaching its clean-test accuracy with fewer bootstraps, or reaching higher accuracy at the same number of bootstraps, across at least three noise seeds.
Why not just…?
Why not just grid-search hyperparameters in parallel ciphertexts and let the client pick the best? For one or two scalar hyperparameters this is probably simpler and better, and we concede it. With one weight per training example, or one regularizer per feature on Prostate (8 dimensions), the grid is exponentially large. That is why every experiment here uses high-dimensional upper-level variables.
Why not just decrypt at the client every few iterations? This removes the depth problem but requires the data owner to stay online, to exchange data over many rounds, and to see intermediate iterates. Schlor et al. and Zhou et al. both cite these costs as reasons to avoid interaction. We report the interactive variant's round count alongside our bootstrap count, so readers can price the trade for their own deployment.
Why not just bootstrap a standard nested solver? Bootstrapping dominates encrypted training time, as Nandakumar et al. and Kang note. Esperança et al. report that a depth-aware design brought encrypted Prostate regression to about 30 minutes, where earlier bootstrapping-dependent approaches took days. A nested solver multiplies depth by the inner iteration count per outer step. We run it as a baseline and count its bootstraps.
Why not just use one-step unrolled reweighting? This is the real threat. If it matches our accuracy per bootstrap, the empirical case for the penalty method shrinks to one thing: it comes with a pre-computable quality certificate and a principled choice of $N$, which the unrolled method lacks. Our experiments will say which situation holds.
Proposed Experiments
We use four testbeds. The first is MNIST reduced by PCA to 3-vs-8, following Zhou et al., with 50% label noise. The second is Adult, COMPAS, and Credit with 30–50% injected label noise; on the unweighted versions of these, Zhou et al. report encrypted accuracy within 1.82% and AUC within 0.78% of plaintext DP training. The third is Prostate with per-feature ridge weights tuned on a held-out split. Esperança et al. report convergence of plain encrypted ridge regression there in four VWT-accelerated iterations, about 30 minutes, and 3.5 GB of RAM. The fourth is Fashion-MNIST reduced by PCA, as a harder hyper-cleaning case. SLM confirms robustness there, but the file quotes no percentage for Fashion-MNIST.
The first decisive check runs in plaintext with an exact depth counter. We sweep $\sigma$ and $N$ and test whether the empirically best $\sigma$ scales like $N^{-1/3}$ and whether the certified bound upper-bounds the observed hypergradient norm. If the optimal $\sigma$ does not move with the budget, the central claim fails.
The second check is encrypted. It plots clean-test accuracy against bootstrap count and wall-clock time for our method, one-step unrolling, the nested bootstrapped solver, and the do-nothing reference. We also report the gap to the plaintext ceiling.
The third check runs the ablations at matched depth. It asks whether avoiding second derivatives and avoiding growing-degree penalties each save measurable bootstraps, and whether the single van Wijngaarden transform shortens $N$ without harming the certificate.
The fourth check verifies decryption correctness at every scheduled bootstrap. It confirms that the plaintext calculator's depth predictions match the compiled circuit exactly, since a miscount there would silently corrupt the result.
References
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation
- A polynomial-based QCQP solver for encrypted optimization
- Penalty Method for Inversion-Free Deep Bilevel Optimization
- First-Order Penalty Methods for Bilevel Optimization
- SLM: A Smoothed First-Order Lagrangian Method for Structured Constrained Nonconvex Optimization
- Revisiting ML Training under Fully Homomorphic Encryption: Convergence Guarantees, Differential Privacy, and Efficient Algorithms
- Encrypted Accelerated Least Squares Regression
- Homomorphic Encryption Standard
- cuHE: A Homomorphic Encryption Accelerator Library
- Towards Deep Neural Network Training on Encrypted Data
- Privacy-Preserving Machine Learning With Fully Homomorphic Encryption for Deep Neural Network