Gradient-Only Online Convex Optimization with a Single Quadratic Leader

Abstract

We study online convex optimization on a bounded Euclidean domain when the learner receives only one subgradient at its prediction and knows neither the horizon, a gradient bound, nor the losses'strong-convexity parameters. We present a scale-invariant algorithm that couples projected adaptive gradient descent to one cone-constrained quadratic leader through a positive wealth process. The algorithm maintains $O(d)$ state, without a learning-rate grid or restarts. For a domain of diameter at most $D$, it guarantees regret at most $\sqrt{2}D(\sum_t\|\widehat g_t\|^2)^{1/2}+2D\max_t\|\widehat g_t\|$, with no logarithmic factor. A simultaneous quadratic-distance bound yields explicit improvements for unknown strong convexity, including a refinement governed by jumps in the observed gradient scale. For varying per-round curvature, the bound depends on the total shortfall below a reference level selected in hindsight. The proof uses a clipping-compatible surrogate and a potential involving the quadratic minimum, log wealth, and two scalar curvature statistics. The resulting strongly convex bound is not uniform at the classical logarithmic rate over all curvature-to-gradient ratios; the exact parameter dependence is stated. The contribution is a single-leader construction and its analysis, within an established literature on universal and scale-free online learning.