Better Full-Matrix Regret via Parameter-Free Online Learning

Ashok CutkoskyNeurIPS 2020 · OpenReview

Introduction

In the realm of Online Convex Optimization (OCO), developing algorithms that are both highly adaptive to the geometry of the data and easy to deploy without manual "hyperparameter hacking" remains a fundamental challenge. This paper tackles this issue by providing new OCO algorithms that achieve "full-matrix" regret bounds. Crucially, these algorithms adapt to the specific directional geometry of the data without requiring users to tune learning rates, and they maintain these guarantees across any convex domain. By doing so, the work bridges the gap between the empirical success of adaptive algorithms like AdaGrad and their theoretical underpinnings.

The Challenge: Tuning Traps and Constraint Complications

In a standard OCO setting, a learner repeatedly chooses a point $w_t$ within a domain $W$ and subsequently receives a loss function. The primary objective is to minimize regret—the difference between the learner's total accumulated loss and the loss of the best fixed point $\mathring{w}$ chosen in hindsight.

While standard algorithms like AdaGrad are "adaptive" (scaling their learning rates based on historical gradients), they face two significant hurdles in achieving full-matrix regret bounds:

  1. The Tuning Trap: Most full-matrix variants of these algorithms—which utilize a matrix to scale gradients differently across various directions—require a learning rate $\eta$ that depends on the unknown distance to the optimal point, $\|\mathring{w}\|$. In practice, researchers manually tune this parameter. However, in strict online settings, this distance is fundamentally unknowable a priori.
  2. Constraint Complications: Achieving sophisticated regret bounds is relatively straightforward in unconstrained spaces (e.g., $\mathbb{R}^d$). However, the mathematics become complex and the theoretical guarantees often weaken when the learner is restricted to a specific convex set $W$, such as a probability simplex or a bounded ball.

Methodology: A Parameter-Free Framework

To overcome these hurdles, the author introduces a general framework for constructing regret bounds using a sequence of increasing norms. The core technical contribution unfolds across three main stages:

  • FTRL with Time-Varying Constraints: The approach utilizes a "Follow-the-Regularized-Leader" (FTRL) strategy with a unique twist: the algorithm is constrained to stay within a unit ball that dynamically changes size based on the current norm. While this constraint might seemingly degrade the standalone FTRL performance, it introduces crucial predictability.
  • 1D to Multi-D Reduction: To eliminate the need for hyperparameter tuning, the author employs a "parameter-free" reduction. A simple one-dimensional learner, capable of learning its own scale, is used to "drive" the more complex multi-dimensional algorithm.
  • Handling Constraints: The framework adapts a technique to convert unconstrained algorithms into constrained ones. By carefully projecting points back into the domain $W$ and adjusting the surrogate gradients fed back into the learner, the regret analysis remains mathematically sound.

Key Insights

  • Demystifying AdaGrad's Success: The author posits that full-matrix AdaGrad excels in practice—despite theoretical bounds that do not always reflect this advantage—because practitioners effectively "oracle-tune" the learning rate. This paper demonstrates that it is possible to achieve these "oracle" benefits automatically, without manual intervention.
  • Incomparable Bounds: The research highlights that different types of regret bounds (e.g., rank-based versus trace-based) are mathematically "incomparable." Depending on the specific characteristics of the data, one bound might be vastly superior to the other. The proposed framework is highly flexible, allowing it to target multiple types of these bounds.
  • Norm Sequences as a Strategy: Rather than committing to a single fixed geometry, the algorithm adapts to a sequence of norms $\|\cdot\|_t$ generated on-the-fly. This dynamic adaptation allows the algorithm to effectively "learn" the shape of the loss surface as optimization progresses.

Theoretical Results

As a purely theoretical paper focused on algorithmic proofs and regret analysis, the work does not evaluate the algorithms on empirical datasets. Instead, it provides two major new regret bounds that hold for arbitrary convex domains:

  1. Rank-Dependent Bound: A bound that depends on the rank $r$ of the subspace spanned by the gradients, effectively "ignoring" irrelevant directions in the data.
  2. Refined AdaGrad Bound: A bound that recovers the optimal performance of full-matrix AdaGrad without requiring prior knowledge of the optimal learning rate $\eta$.

Mathematically, the regret is shown to be bounded by approximately $\tilde{O}(\|\mathring{w}\| \sqrt{\text{rank}(G_T) \sum \langle g_t, \mathring{w} \rangle^2})$, where $G_T$ is the sum of the outer products of the gradients. This confirms that the algorithm performs exceptionally well when the data is "approximately low-rank."

Limitations and Future Directions

The author identifies several areas for future improvement:

  • Logarithmic Overhead: The new bounds introduce extra $\sqrt{\log T}$ factors compared to the best possible unconstrained rates, presenting an opportunity for tighter bounds in future work.
  • Origin Centering: The current algorithms utilize regularizers centered at the origin. Allowing the "center" of the algorithm to dynamically shift over time could lead to even more efficient optimization.
  • Conditional Bounds: Recent literature has shown that even better bounds are achievable if gradients satisfy certain "non-randomness" conditions. Whether these specific results can be replicated in the constrained settings discussed here remains an open question.

Summary updated

Abstract

We provide online convex optimization algorithms that guarantee improved full-matrix regret bounds. These algorithms extend prior work in several ways. First, we seamlessly allow for the incorporation of constraints without requiring unknown oracle-tuning for any learning rate parameters. Second, we improve the regret of the full-matrix AdaGrad algorithm by suggesting a better learning rate value and showing how to tune the learning rate to this value on-the-fly. Third, all our bounds are obtained via a general framework for constructing regret bounds that depend on an arbitrary sequence of norms.
BibTeX
@inproceedings{cutkosky2020better,
  author = {Ashok Cutkosky},
  title = {{Better Full-Matrix Regret via Parameter-Free Online Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=Dt9ahw1d6Nx},
}
Figure