Back to search

Boston University

Unconstrained online convex optimization: regularization in the adversarial setting and beyond

Abstract

dc:description.abstract

Most 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 × 9

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/53768

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Zhang, Jiujia. Unconstrained online convex optimization: regularization in the adversarial setting and beyond. doctoral thesis, Boston University, 2026. https://hdl.handle.net/2144/53768