Online Convex Optimization with Warm Starts: Upper and Lower Regret Bounds

Online learners often begin from a retrieved, teacher-supplied, or previously trained parameter whose reliability is unknown. We study how this warm start affects static regret through its distance to the closest offline optimum. If that distance is revealed, online gradient descent achieves regret proportional to the distance times the square root of the horizon, and a matching lower bound holds at every distance up to half the domain diameter. Without the distance, a learning-rate ensemble and a translated parameter-free method adapt to its realized value, yet no algorithm can attain the oracle rate within one universal constant at every distance. Perfect trust in an exact warm start also entails linear sensitivity to small errors. With a known strong-convexity modulus, regularized follow-the-leader obtains a quadratic distance term without distance-dependent tuning, although its additive logarithmic term remains unmatched. A two-point bandit bound holds for oblivious losses in dimension at least two when a certified interior ball around the warm start contains a closest optimum. Logistic-loss experiments using the same online and offline objective illustrate the benefit of reliable retrieval and the cost of corruption.