AdaGrad and Universality in Composite Optimization: Failure and a Remedy

AdaGrad adapts to unknown Hölder-smoothness in unconstrained deterministic convex optimization, attaining the rate $O(n^{-(1+\nu)/2})$ without knowledge of $\nu$, but a recent lower bound shows that this property can fail for composite problems. In the lower-bound construction, a persistent component of the smooth gradient forces the AdaGrad stepsize to decay as $n^{-1/2}$. Taking this mechanism as our starting point, we introduce AdaRes, a blockwise AdaGrad-type method that fits a constant to the observed gradient history and accumulates only the resulting least-squares residual. For stochastic convex composite problems with bounded iterates, AdaRes attains $O(n^{-1/2})$ under bounded second moments and, under $\nu$-Hölder-smoothness, $O\left(n^{-(1+\nu)/2}+\sigma n^{-1/2}\right)$, where $\sigma^2$ bounds the gradient variance at a solution. In particular, the deterministic Hölder rate is recovered when $\sigma=0$.