Optimizing Retraining Schedules via Learning Curves

Retraining is the primary mechanism by which deployed models adapt to new data, yet it is also among the most expensive operations in modern machine learning. How often must a model be retrained to remain near-optimal? We answer this question through a learning-curve based characterization of the retraining-frequency/risk trade-off in online learning. For the i.i.d. realizable setting, we observe that only $O(\log T)$ updates suffice to match the risk of *full retraining* whenever the learning curve is non-increasing. However, when the learning curve decays as a power law $t^{-\alpha}$ with $\alpha < 1$, as empirically observed in deep learning, the budget collapses further to $O(\log \log T)$ updates, yielding a *substantial asymptotic* improvement. We further design update schedules achieving these bounds, prove matching lower bounds, and present an adaptive algorithm that remains optimal when $\alpha$ is unknown. We then extend the analysis to piecewise-stationary and gradually drifting environments, and establish a no-free-lunch theorem showing that some prior knowledge of the learning curve is unavoidable, i.e., no universal algorithm can be competitive without it. Together, these results provide a sharp characterization of the frequency--accuracy trade-off in online retraining and bridge foundational learning theory with practical strategies for scalable deployment.