ECE PhD Thesis Defense: Jiujia Zhang

ECE PhD Thesis Defense: Jiujia Zhang

Title: Unconstrained Online Convex Optimization: Regularization in the Adversarial Setting and Beyond

Presenter: Jiujia Zhang

Advisor: Professor Ashok Cutkosky

Chair: Professor Douglas Densmore

Committee: Professor Ashok Cutkosky, Professor Alex Olshevsky, Professor Brian Kulis, Professor David Castañón, Professor Xuezhou Zhang

Google Scholar Link: https://scholar.google.com/citations?user=eiOVT-8AAAAJ&hl=en

Abstract: Most first-order optimizers used to train a model require the user to explicitly choose a learning rate, a parameter governing the size of each update. This choice is consequential: too large a learning rate causes training to diverge, while too small a value wastes computation without making enough progress. This difficulty is structural rather than incidental: classical optimizers such as stochastic gradient descent requires an estimate of how far the starting point lies from a good solution in advance. In practice, such information is rarely available and must instead be tuned heuristically, which is often time-consuming and unreliable.

Beyond the learning rate, the true gradient itself is rarely observed in contemporary training tasks. For large datasets, computing exact gradients is expensive, so mini-batches are used instead to obtain stochastic approximations of the gradient. On top of this, the feedback actually received may be corrupted, whether by data outliers, adversarial interference, or in distributed training, communication and quantization errors that accumulate across machines. In practice, optimization is proceeded under inexact gradient feedback, making it essential to understand how to design algorithms that remain robust to such inexactness.

This thesis asks whether optimization algorithms can be built that (a) never need to be told the scale of the problem in advance, and (b) still perform well when the gradient they receive is noisy or corrupted. The answer is yes and is achieved by designing comparator-adaptive Online Convex Optimization (OCO) algorithms around two intertwined tools: the incoming inexact gradient is first clipped to tame large corruptions which introduces a clipping bias, and this bias is then corrected by a carefully chosen regularizer. Using this two-step recipe, we show that OCO algorithms can remain robust whether the corruption takes the form of heavy-tailed noise or a certain number of arbitrarily corrupted feedbacks. Through the classical online-to-batch conversion, these OCO regret guarantees translate directly into convergence guarantees for Stochastic Convex Optimization (SCO).

The thesis also resolves a puzzle from empirical practice: In SCO, practitioners never implement explicit regularization, yet good performance is still observed. Our theory traces this to a structural distinction that the classical online-to-batch conversion overlooks: the environment a learner faces under SCO is "cooperative", since every update pursues the same fixed objective, whereas under general OCO it is "adversarial". As a consequence, many existing OCO algorithms remain robust in practical SCO tasks even in their off-the-shelf form with straightforward gradient clipping.