Do we really need the Rademacher complexities?

• URL: http://arxiv.org/abs/2502.15118v1
• Date: Fri, 21 Feb 2025 00:40:22 GMT
• Title: Do we really need the Rademacher complexities?
• Authors: Daniel Bartl, Shahar Mendelson,
• Abstract summary: We study the fundamental problem of learning with respect to the squared loss in a convex class.<n>We prove that, contrary to prevailing belief and under minimal assumptions, the sample complexity is not governed by the Rademacher complexities.
• Score: 3.683202928838613
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the fundamental problem of learning with respect to the squared loss in a convex class. The state-of-the-art sample complexity estimates in this setting rely on Rademacher complexities, which are generally difficult to control. We prove that, contrary to prevailing belief and under minimal assumptions, the sample complexity is not governed by the Rademacher complexities but rather by the behaviour of the limiting gaussian process. In particular, all such learning problems that have the same $L_2$-structure -- even those with heavy-tailed distributions -- share the same sample complexity. This constitutes the first universality result for general convex learning problems. The proof is based on a novel learning procedure, and its performance is studied by combining optimal mean estimation techniques for real-valued random variables with Talagrand's generic chaining method.

Related papers

• Lean Formalization of Generalization Error Bound by Rademacher Complexity [5.071436325424837]
  Generalization error quantifies the gap between a learning machine's performance on given training data versus unseen test data. We formalize the generalization error bound using Rademacher complexity in the Lean 4 theorem prover.
  arXiv  Detail & Related papers  (2025-03-25T12:40:43Z)
• Simplifying Adversarially Robust PAC Learning with Tolerance [9.973499768462888]
  We show the existence of a simpler learner that achieves a sample complexity linear in the VC-dimension without requiring additional assumptions on H.<n>Even though our learner is improper, it is "almost proper" in the sense that it outputs a hypothesis that is "similar" to a hypothesis in H.<n>We also use the ideas from our algorithm to construct a semi-supervised learner in the tolerant setting.
  arXiv  Detail & Related papers  (2025-02-11T03:48:40Z)
• The complexity of entanglement embezzlement [0.0]
  We study the circuit complexity of embezzlement using sequences of states that enable arbitrary precision for the process. We imply that circuit complexity acts as a physical obstruction to perfect embezzlement.
  arXiv  Detail & Related papers  (2024-10-24T18:00:33Z)
• Transductive Learning Is Compact [10.168670899305232]
  We show a compactness result holding broadly across supervised learning with a general class of loss functions. For realizable learning with improper metric losses, we show that exact compactness of sample complexity can fail. We conjecture that larger gaps are possible for the agnostic case.
  arXiv  Detail & Related papers  (2024-02-15T23:10:45Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks [25.832511407411637]
  A fundamental problem in adversarial machine learning is to quantify how much training data is needed in the presence of evasion attacks. We work with probability distributions on the input data that satisfy a Lipschitz condition: nearby points have similar probability. For every fixed $k$ the class of $k$-decision lists has sample complexity against a $log(n)$-bounded adversary.
  arXiv  Detail & Related papers  (2022-05-12T14:40:18Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  We study the problem of learning an adversarially robust predictor to test time attacks in the semi-supervised PAC model. We show that there is a significant benefit in semi-supervised robust learning even in the worst-case distribution-free model.
  arXiv  Detail & Related papers  (2022-02-11T03:01:45Z)
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? [108.94173231481355]
  Learning to plan for long horizons is a central challenge in episodic reinforcement learning problems. We show that long horizon RL is no more difficult than short horizon RL, at least in a minimax sense.
  arXiv  Detail & Related papers  (2020-05-01T17:56:38Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.