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 √2D(∑t|ĝt|2)1/2+2Dmaxt|ĝ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.
Related
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
- Stabilized SQP Method for Convex Piecewise Linear-Quadratic Composite Optimization Problems
- Tracking a Small Set of Experts in Online Convex Optimization
- On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts
- Online Optimization with Unknown Time-Varying Parameters Using Noisy Gradient Measurements
BibTeX
@misc{asgari2026gradientonly,
title = {{Gradient-Only Online Convex Optimization with a Single Quadratic Leader}},
author = {Kamiar Asgari},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00190},
eprint = {2610.00190},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00190},
}
RIS
TY - UNPB
TI - Gradient-Only Online Convex Optimization with a Single Quadratic Leader
AU - Kamiar Asgari
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.00190
UR - https://arxiv.org/abs/2610.00190
AB - 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 √2D(∑_t|ĝ_t|^2)^1/2+2Dmax_t|ĝ_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.
ER -