Boston University
Unconstrained online convex optimization: regularization in the adversarial setting and beyond
Abstract
dc:description.abstractMost first-order optimizers require a learning rate that depends on the problem scale, the distance from initialization to an optimal solution, and receive gradient feedback that is stochastic, corrupted, or both. This thesis studies whether these two difficulties can be resolved simultaneously: we develop online convex optimization algorithms on an unconstrained domain that adapt to the unknown problem scale while operating under inexact gradient feedback. We consider two models of gradient inexactness: a stochastic model, where each gradient is perturbed by zero-mean heavy-tailed noise with bounded p-th moment for p in (1,2], and an adversarial model, where up to k gradient observations are arbitrarily corrupted. In both settings, the algorithm observes only the corrupted gradient yet must control regret against the true gradients. The central technique combines gradient clipping with a time-varying regularizer: clipping limits the influence of extreme observations, while the regularizer cancels the resulting clipping bias and controls iterate growth. The latter is a genuine obstacle in unconstrained online convex optimization, where iterates can grow exponentially fast. Under heavy-tailed gradient noise, we establish the first high-probability comparator-adaptive regret bound Õ(‖x‖ T^(1/p)) for any comparator x in the unconstrained setting, matching existing lower bounds. Under adversarial corruption, we provide an algorithm achieving Õ(‖x‖(√T + k)) regret with a matching lower bound. We then resolve a puzzle from practice: explicit regularization is never implemented in stochastic convex optimization, yet clipping alone works well. Our explanation is structural: the environment a learner faces under stochastic convex optimization is cooperative in that every feedback carries information about learning a fixed objective, whereas general online convex optimization is adversarial. We formalize this as the stochastic-like condition, under which iterate stability follows: the iterates of any comparator-adaptive algorithm automatically remain near the optimum without explicit regularization. This yields a black-box reduction: any comparator-adaptive online learner inherits high-probability convergence guarantees in stochastic convex optimization. As a further application of iterate stability, we obtain comparator-adaptive algorithms for stochastic fixed point iterations, resolving the stochastic setting left open in prior work.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy
- Level thesis:degree_level
- doctoral
- Discipline thesis:degree_discipline
- Electrical & Computer Engineering
- Grantor
- Boston University
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Zhang, Jiujia
- Advisor dc:contributor.advisor
-
- Cutkosky, Ashok
- ORCID dc:identifier.orcid
Subjects
dc:subject × 9Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53768