Revisiting ML Training under Fully Homomorphic Encryption: Convergence Guarantees, Differential Privacy, and Efficient Algorithms

We present the first theoretical convergence analysis of machine learning training under fully homomorphic encryption (FHE), combined with a differentially private (DP) training algorithm tailored to encrypted computation. Our approach improves computational efficiency over standard differentially private gradient descent (DP-GD) while achieving comparable utility. In particular, we prove convergence of approximate gradient descent using polynomial approximations of activation and loss functions, which are required for FHE compatibility. To preserve privacy in downstream tasks, we integrate differential privacy without relying on costly per-sample gradient clipping, enabling scalable encrypted learning. We also provide data-independent hyperparameter selection and theoretically grounded strategies for polynomial approximation which can be of independent interest. Together, these contributions advance the feasibility of efficient, private, and secure machine learning on sensitive data.

Machine learning systems are increasingly trained on sensitive data such as medical records and financial information. Protecting privacy during training remains challenging, especially when computation is outsourced to external servers. Existing privacy-preserving training methods are also often prohibitively slow and expensive, limiting their use in practice. In this work, we develop techniques for training machine learning models while keeping the underlying data protected throughout the entire pipeline. The training data remains encrypted at all times, so the server performing the computation never sees the raw information. We also incorporate differential privacy, which adds carefully calibrated randomness during training to limit what the final model can reveal about any individual training example. Beyond the system design, we provide the first theoretical analysis showing that accurate learning is still possible under the approximations and noise introduced by encrypted and privacy-preserving training. We additionally introduce a new training method that avoids several of the most computationally expensive operations used in prior approaches, significantly improving efficiency and scalability. Experiments show that our method achieves comparable model accuracy while reducing the computational cost of encrypted private training by several times. These results help bring secure and privacy-preserving machine learning closer to practical deployment in areas such as healthcare, finance, and government services.