Generalization Error of First-Order Methods for Statistical Learning with Generic Oracles

Kevin Scaman, Mathieu Even, Laurent Massoulié

Abstract

In this paper, our aim is to analyse the generalization capabilities of first-order methods for statistical learning in multiple, different yet related, scenarios including supervised learning, transfer learning, robust learning and federated learning. To do so, we provide sharp upper and lower bounds for the minimax excess risk of strongly convex and smooth statistical learning when the gradient is accessed through partial observations given by a data-dependent oracle. This novel class of oracles can query the gradient with any given data distribution, and is thus well suited to scenarios in which the training data distribution does not match the target (or test) distribution. In particular, our upper and lower bounds are proportional to the smallest mean square error achievable by gradient estimators, thus allowing us to easily derive multiple sharp bounds in the aforementioned scenarios using the extensive literature on parameter estimation.

Introduction

This work introduces a unified theoretical framework to analyze the minimax excess risk—the gap between the test loss achieved by an algorithm and the best possible loss—across diverse learning scenarios like transfer, robust, and federated learning. By introducing the concept of data-dependent oracles, we demonstrate that the fundamental limit of learning is determined by how well an oracle can estimate the true population gradient, a quantity termed the "best approximation error."

Problem Formulation

In classical machine learning theory, error is typically decomposed into generalization error (the difference between training and test performance) and optimization error (the distance to the training optimum). However, this decomposition is often inadequate for modern settings. For instance, in transfer learning, the training and test distributions differ, while in robust learning, training data may be corrupted. In such cases, the standard training loss is not the appropriate objective to minimize.

We address a fundamental question: Given a specific data access mechanism (an "oracle"), what is the absolute best test performance any first-order optimization algorithm can achieve? The goal is to move beyond case-by-case analyses and provide a unified mathematical tool applicable to diverse learning configurations.

Methodology

The core of this analysis rests on two novel concepts:

  1. Data-Dependent Oracles: Instead of assuming access to raw samples, we model data access via an oracle. This oracle accepts a model parameter and returns a biased or partial view of the gradient based on a fixed dataset. This allows for the modeling of i.i.d. sampling, corrupted datasets, or fixed grids within a single framework.
  2. Best Approximation Error ($\sigma$): This statistical quantity measures the minimum possible mean square error achievable when estimating the true population gradient using the information provided by the oracle.

We establish minimax bounds based on these concepts:

  • Lower Bound: No algorithm can achieve an excess risk smaller than approximately $\sigma^2 / \mu$, where $\mu$ represents the strong convexity of the loss.
  • Upper Bound: We propose Minibatch GD with Warmup—an algorithm utilizing increasing batch sizes—to reach this theoretical limit within logarithmic factors.

Learning Scenarios

The framework is applied to five distinct learning scenarios:

  • Supervised Learning: Training and test distributions are identical.
  • Transfer Learning: The training distribution $D'$ differs from the test distribution $D$.
  • Federated Learning: Collaboration between multiple agents with heterogeneous local data.
  • Robust Learning: A fraction $\eta$ of the data is subject to arbitrary corruption.
  • Fixed Data: Learning from a predetermined, non-random set of points, such as a sensor grid.

Key Results and Insights

The analysis reveals that the difficulty of a learning task is fundamentally tied to the difficulty of estimating the population gradient. If the oracle provides poor gradient information, the excess risk remains high regardless of the optimization algorithm's sophistication.

A significant finding is that Transfer Learning and Robust Learning are mathematically analogous, differing only in how the gradient estimate is biased. Furthermore, achieving optimal rates in supervised learning requires a "warmup" phase using initial samples to establish a baseline estimate, followed by exponentially increasing batch sizes.

The following table summarizes the sharp bounds derived for these scenarios:

Table 1: Minimax excess risk bounds for various learning scenarios.

As shown in Table 1:

  • Supervised Learning: Excess risk scales as $O(1/n)$.
  • Transfer Learning: Risk is dominated by the Total Variation (TV) distance between distributions, scaling with $d_{TV}(D, D')^2 + 1/n$.
  • Robust Learning: For bounded gradients with a corruption fraction $\eta$, the risk scales with $\eta^2 + 1/n$.
  • Fixed Data: Risk depends on the "coverage" of fixed points, specifically the expected squared distance from a random test point to the nearest training point.

Conclusion and Future Work

While this framework provides sharp bounds for strongly convex and smooth losses, future work will explore extensions to non-convex settings and other regularity conditions, such as Hessian-based oracles. The current analysis focuses on oracle query complexity rather than hardware-specific constraints, providing a fundamental information-theoretic perspective on the limits of statistical learning.

Summary updated

Abstract

In this paper, our aim is to analyse the generalization capabilities of first-order methods for statistical learning in multiple, different yet related, scenarios including supervised learning, transfer learning, robust learning and federated learning. To do so, we provide sharp upper and lower bounds for the minimax excess risk of strongly convex and smooth statistical learning when the gradient is accessed through partial observations given by a data-dependent oracle. This novel class of oracles can query the gradient with any given data distribution, and is thus well suited to scenarios in which the training data distribution does not match the target (or test) distribution. In particular, our upper and lower bounds are proportional to the smallest mean square error achievable by gradient estimators, thus allowing us to easily derive multiple sharp bounds in the aforementioned scenarios using the extensive literature on parameter estimation.
BibTeX
@inproceedings{scaman2024generalization,
  author = {Kevin Scaman and Mathieu Even and Laurent Massoulié},
  title = {{Generalization Error of First-Order Methods for Statistical Learning with Generic Oracles}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=vvkGbYN9Sx},
}
Figure