Asymptotic sequential Rademacher complexity of a finite function class

DOI10.1007/S00013-016-1002-3zbMATH Open1366.60090arXiv1605.03843OpenAlexW2963608618MaRDI QIDQ517475FDOQ517475

Authors: D. B. Rokhlin 

Publication date: 23 March 2017

Published in: Archiv der Mathematik (Search for Journal in Brave)

Abstract: For a finite function class we describe the large sample limit of the sequential Rademacher complexity in terms of the viscosity solution of a $G$-heat equation. In the language of Peng's sublinear expectation theory, the same quantity equals to the expected value of the largest order statistics of a multidimensional $G$-normal random variable. We illustrate this result by deriving upper and lower bounds for the asymptotic sequential Rademacher complexity.

Full work available at URL: https://arxiv.org/abs/1605.03843

Recommendations

• Rademacher Margin Complexity
• Complexity of pattern classes and the Lipschitz property
• Algorithmic Learning Theory
• 10.1162/153244303321897690
• Local Rademacher complexities

zbMATH Keywords

central limit theoremviscosity solutions\(G\)-heat equationsequential Rademacher complexity

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Viscosity solutions to PDEs (35D40) Applications of stochastic analysis (to PDEs, etc.) (60H30)

Cites Work

• Prediction, Learning, and Games
• Concentration inequalities. A nonasymptotic theory of independence
• Uniqueness Results for Second-Order Bellman--Isaacs Equations under Quadratic Growth Assumptions and Applications
• User’s guide to viscosity solutions of second order partial differential equations
• Title not available (Why is that?)
• The Generic Chaining
• Multi-dimensional \(G\)-Brownian motion and related stochastic calculus under \(G\)-expectation
• Title not available (Why is that?)
• Markov Processes, Gaussian Processes, and Local Times
• Title not available (Why is that?)
• Exponentially growing solutions of parabolic Isaacs' equations
• Encyclopedia of machine learning
• A new convex objective function for the supervised learning of single-layer neural networks
• Sequential complexities and uniform martingale laws of large numbers
• VC dimension, fat-shattering dimension, Rademacher averages, and their applications
• Online learning via sequential complexities
• Central limit theorem under uncertain linear transformations

Cited In (1)

• Optimal unbiased estimation for maximal distribution

This page was built for publication: Asymptotic sequential Rademacher complexity of a finite function class

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517475)