Learning From An Optimization Viewpoint

Karthik SridharanarXiv 2012 · OpenReview

Abstract

In this dissertation, we study statistical and online learning problems from an optimization viewpoint. The dissertation is divided into two parts: I. We first consider the question of learnability for statistical learning problems in the general learning setting. The question of learnability is well studied and fully characterized for binary classification and for real-valued supervised learning problems using the theory of uniform convergence. However, we show that for the general learning setting, uniform convergence theory fails to characterize learnability. To fill this void, we use stability of learning algorithms to fully characterize statistical learnability in the general setting. Next, we consider the problem of online learning. Unlike the statistical learning framework, there is a dearth of generic tools that can be used to establish learnability and rates for online learning problems in general. We provide online analogs to classical tools from statistical learning theory like Rademacher complexity, covering numbers, etc. We further use these tools to fully characterize learnability for online supervised learning problems. II. In the second part, for general classes of convex learning problems, we provide appropriate mirror descent (MD) updates for online and statistical learning of these problems. Further, we show that the MD is near optimal for online convex learning and, for most cases, is also near optimal for statistical convex learning. We next consider the problem of convex optimization and show that oracle complexity can be lower bounded by the so-called fat-shattering dimension of the associated linear class. Thus, we establish a strong connection between offline convex optimization problems and statistical learning problems. We also show that for a large class of high-dimensional optimization problems, MD is in fact near optimal even for convex optimization.

Introduction

For decades, the "gold standard" for proving a problem is learnable was Uniform Convergence. This theory suggests that if a hypothesis class is simple enough (e.g., has a low VC-dimension), the error observed on training data will eventually converge to the true error. However, this framework has significant limitations. In general learning settings, a problem can be perfectly learnable even when uniform convergence fails. This is particularly evident in Online Learning, where data arrives sequentially and may be chosen by an adversary rather than being drawn from a static distribution. This work, "Learning From An Optimization Viewpoint" by Karthik Sridharan, re-evaluates these foundations, framing learning as an optimization task and identifying stability as the fundamental requirement for learnability.

Part I: Stability and General Learnability

The first part of the dissertation addresses the gap in general learning settings where uniform convergence fails to characterize learnability. Sridharan moves away from the complexity of the hypothesis class and focuses on the Stability of the learning rule.

The Universal Learning Rule

Sridharan introduces the "Universal Learning Rule" and proves that a problem is statistically learnable if and only if there exists a stable Asymptotic Empirical Risk Minimizer (AERM). This shift establishes that stability—how much an algorithm's output changes with a single data point swap—is a more powerful and necessary condition for learning than uniform convergence. If an algorithm is stable, it generalizes; if a problem is learnable, a stable algorithm must exist.

Online Learning as a Tree Game

Unlike statistical learning, which treats data as an i.i.d. (independent and identically distributed) "bag," online learning is modeled as a game played on a tree. Each path represents a possible sequence of adversarial moves. To analyze this, Sridharan develops "Sequential Rademacher Complexity," providing online analogs to classical tools like covering numbers. These tools allow for a full characterization of learnability for online supervised learning problems, providing the first rigorous toolkit for this "game-view" of learning.

Part II: Tractable Convex Learning and Mirror Descent

The second part focuses on the efficiency of learning in convex settings where computational tractability is paramount. The primary tool utilized is Mirror Descent (MD), a generalized version of gradient descent that can be tuned to the specific geometry of the problem space.

The Optimality of Mirror Descent

The thesis demonstrates that Mirror Descent is near-optimal across various contexts. For online convex learning, MD achieves a regret bound within a $O(\log^2 n)$ factor of the minimax value (the absolute theoretical limit). In statistical convex learning, it remains near-optimal in most cases, performing within a logarithmic factor of the best possible theoretical algorithm.

Oracle Complexity and the Parallelization Paradox

Using the framework of Oracle Complexity, which measures efficiency by the number of queries (e.g., gradients) required to reach a target accuracy, Sridharan shows that oracle complexity can be lower-bounded by the fat-shattering dimension of the associated linear class. This establishes a deep connection between offline convex optimization and statistical learning.

Furthermore, in high-dimensional spaces, the work reveals a "Parallelization Paradox": for many hard convex optimization problems, access to distributed oracles (parallel computing) does not significantly improve oracle complexity. The sequential bottleneck remains fundamental, making simple first-order methods like Mirror Descent as efficient as any possible parallelized approach. Essentially, for many high-dimensional problems, one cannot "brute force" a faster solution with more machines.

Conclusion

This dissertation provides a unified framework for understanding learnability through the lens of algorithmic stability and Mirror Descent. By proving that stability is the true requirement for learnability and establishing the near-optimality of Mirror Descent, this work bridges the gap between theoretical consistency and computational efficiency in both online and statistical learning.

Summary updated

Abstract

In this dissertation we study statistical and online learning problems from an optimization viewpoint.The dissertation is divided into two parts : I. We first consider the question of learnability for statistical learning problems in the general learning setting. The question of learnability is well studied and fully characterized for binary classification and for real valued supervised learning problems using the theory of uniform convergence. However we show that for the general learning setting uniform convergence theory fails to characterize learnability. To fill this void we use stability of learning algorithms to fully characterize statistical learnability in the general setting. Next we consider the problem of online learning. Unlike the statistical learning framework there is a dearth of generic tools that can be used to establish learnability and rates for online learning problems in general. We provide online analogs to classical tools from statistical learning theory like Rademacher complexity, covering numbers, etc. We further use these tools to fully characterize learnability for online supervised learning problems. II. In the second part, for general classes of convex learning problems, we provide appropriate mirror descent (MD) updates for online and statistical learning of these problems. Further, we show that the the MD is near optimal for online convex learning and for most cases, is also near optimal for statistical convex learning. We next consider the problem of convex optimization and show that oracle complexity can be lower bounded by the so called fat-shattering dimension of the associated linear class. Thus we establish a strong connection between offline convex optimization problems and statistical learning problems. We also show that for a large class of high dimensional optimization problems, MD is in fact near optimal even for convex optimization.
BibTeX
@misc{sridharan2012learning,
  author = {Karthik Sridharan},
  title = {{Learning From An Optimization Viewpoint}},
  year = {2012},
  eprint = {1204.4145},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1204.4145},
}
Figure