ABS: An Adaptive Bootstrapping Scheduler for Efficient and Accurate Logistic Regression Training over Homomorphic Encryption

Homomorphic Encryption (HE) presents a com pelling paradigm for privacy-preserving machine learning; how ever, its practical adoption is hindered by substantial computa tional overhead. For iterative algorithms such as Logistic Regres sion (LR), the main performance bottleneck is bootstrapping, a noise-refreshing operation essential for maintaining correctness. Prevailing approaches employ static bootstrapping schedules, forcing practitioners into a suboptimal trade-off: either frequent bootstrapping with minimal parameters, which incurs a massive overhead, or infrequent bootstrapping with large parameters, which slows down all other operations. This study introduces the Adaptive Bootstrapping Scheduler (ABS), an algorithm that resolves this false dichotomy by reframing static scheduling as a dynamic optimization prob lem. ABS intelligently co-designs the HE parameterization and bootstrapping schedule to minimize the execution time while maximizing the model precision. At its core, the ABS leverages a fine-grained performance model to navigate the complex, non linear relationship between operational costs and bootstrapping frequency. Furthermore, we investigate a subtle but critical design choice: which intermediate value to use for bootstrapping. Our analysis, supported by prior work on noisy optimization, reveals that bootstrapping the gradient—a counter-intuitive but optimal strategy—significantly mitigates error accumulation via learning rate scaling. Implemented over the Poseidon library, our experiments on multiple public datasets demonstrate that ABS consistently accelerates LR training by up to 1.77× and achieves superior model fidelity compared to state-of-the-art static schedulers.