Publications

• Sorted by Date • Classified by Publication Type • Classified by Research Category •

A Survey on Scenario Theory, Complexity, and Compression-Based Learning and Generalization

Roberto Rocchetta, Alexander Mey, and Frans A. Oliehoek. A Survey on Scenario Theory, Complexity, and Compression-Based Learning and Generalization. IEEE Transactions on Neural Networks and Learning Systems, ():1–15, 2023.

Download

pdf [3.2MB]  ps.gz ps HTML 

Abstract

This work investigates formal generalization error bounds that apply to support vector machines (SVMs) in realizable and agnostic learning problems. We focus on recently observed parallels between probably approximately correct (PAC)-learning bounds, such as compression and complexity-based bounds, and novel error guarantees derived within scenario theory. Scenario theory provides nonasymptotic and distributional-free error bounds for models trained by solving data-driven decision-making problems. Relevant theorems and assumptions are reviewed and discussed. We propose a numerical comparison of the tightness and effectiveness of theoretical error bounds for support vector classifiers trained on several randomized experiments from 13 real-life problems. This analysis allows for a fair comparison of different approaches from both conceptual and experimental standpoints. Based on the numerical results, we argue that the error guarantees derived from scenario theory are often tighter for realizable problems and always yield informative results, i.e., probability bounds tighter than a vacuous [0,1] interval. This work promotes scenario theory as an alternative tool for model selection, structural-risk minimization, and generalization error analysis of SVMs. In this way, we hope to bring the communities of scenario and statistical learning theory closer, so that they can benefit from each other’s insights.

BibTeX Entry

@ARTICLE{Rocchetta23TNNLS,
    author={Rocchetta, Roberto and Mey, Alexander and Oliehoek, Frans A.},
    journal={IEEE Transactions on Neural Networks and Learning Systems}, 
    title={A Survey on Scenario Theory, Complexity, and Compression-Based Learning and Generalization}, 
    year={2023},
    volume={},
    number={},
    pages={1-15},
    doi={10.1109/TNNLS.2023.3308828},
    keywords =   {refereed},
    abstract = {
      This work investigates formal generalization error bounds that apply to
      support vector machines (SVMs) in realizable and agnostic learning
      problems. We focus on recently observed parallels between probably
      approximately correct (PAC)-learning bounds, such as compression and
      complexity-based bounds, and novel error guarantees derived within
      scenario theory. Scenario theory provides nonasymptotic and
      distributional-free error bounds for models trained by solving
      data-driven decision-making problems. Relevant theorems and
      assumptions are reviewed and discussed. We propose a numerical
      comparison of the tightness and effectiveness of theoretical error
      bounds for support vector classifiers trained on several randomized
      experiments from 13 real-life problems. This analysis allows for a
      fair comparison of different approaches from both conceptual and
      experimental standpoints. Based on the numerical results, we argue
      that the error guarantees derived from scenario theory are often
      tighter for realizable problems and always yield informative results,
      i.e., probability bounds tighter than a vacuous [0,1] interval. This work
      promotes scenario theory as an alternative tool for model selection,
      structural-risk minimization, and generalization error analysis of SVMs.
      In this way, we hope to bring the communities of scenario and
      statistical learning theory closer, so that they can benefit from
      each other’s insights.
  }
}

Generated by bib2html.pl (written by Patrick Riley) on Thu Nov 06, 2025 10:14:50 UTC