Adversarially Robust PAC Learnability of Real-Valued Functions

• URL: http://arxiv.org/abs/2206.12977v3
• Date: Sun, 5 May 2024 19:55:10 GMT
• Title: Adversarially Robust PAC Learnability of Real-Valued Functions
• Authors: Idan Attias, Steve Hanneke,
• Abstract summary: We show that classes of fat-shattering dimension are $ell_p$ learnable in $ell_p$ perturbation setting. We introduce a novel agnostic agnostic sample scheme for real functions, which may be independent interest.
• Score: 19.54399554114989
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study robustness to test-time adversarial attacks in the regression setting with $\ell_p$ losses and arbitrary perturbation sets. We address the question of which function classes are PAC learnable in this setting. We show that classes of finite fat-shattering dimension are learnable in both realizable and agnostic settings. Moreover, for convex function classes, they are even properly learnable. In contrast, some non-convex function classes provably require improper learning algorithms. Our main technique is based on a construction of an adversarially robust sample compression scheme of a size determined by the fat-shattering dimension. Along the way, we introduce a novel agnostic sample compression scheme for real-valued functions, which may be of independent interest.

Related papers

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
  A new complexity measure, called the emphspanning capacity, depends solely on the set $Pi$ and is independent of the MDP dynamics. We show there exists a policy class $Pi$ with a bounded spanning capacity that requires a superpolynomial number of samples to learn. This reveals a surprising separation for learnability between generative access and online access models.
  arXiv  Detail & Related papers  (2023-10-09T19:40:54Z)
• A Curriculum View of Robust Loss Functions [10.285812236489814]
  We show that most loss functions can be rewritten into a form with the same class-score margin and different sample-weighting functions. We show that simple fixes to the curriculums can make underfitting robust loss functions competitive with the state-of-the-art.
  arXiv  Detail & Related papers  (2023-05-03T14:13:03Z)
• Learnability, Sample Complexity, and Hypothesis Class Complexity for Regression Models [10.66048003460524]
  This work is inspired by the foundation of PAC and is motivated by the existing regression learning issues. The proposed approach, denoted by epsilon-Confidence Approximately Correct (epsilon CoAC), utilizes Kullback Leibler divergence (relative entropy) It enables the learner to compare hypothesis classes of different complexity orders and choose among them the optimum with the minimum epsilon.
  arXiv  Detail & Related papers  (2023-03-28T15:59:12Z)
• Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient [65.08966446962845]
  offline reinforcement learning, which aims at optimizing decision-making strategies with historical data, has been extensively applied in real-life applications. We take a step by considering offline reinforcement learning with differentiable function class approximation (DFA) Most importantly, we show offline differentiable function approximation is provably efficient by analyzing the pessimistic fitted Q-learning algorithm.
  arXiv  Detail & Related papers  (2022-10-03T07:59:42Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation. We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
  arXiv  Detail & Related papers  (2022-06-01T23:26:51Z)
• Data-Driven Reachability analysis and Support set Estimation with Christoffel Functions [8.183446952097528]
  We present algorithms for estimating the forward reachable set of a dynamical system. The produced estimate is the sublevel set of a function called an empirical inverse Christoffel function. In addition to reachability analysis, the same approach can be applied to general problems of estimating the support of a random variable.
  arXiv  Detail & Related papers  (2021-12-18T20:25:34Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  We study efficient algorithms for reinforcement learning in decision processes whose complexity is independent of the number of states. We give an efficient algorithm that is capable of improving the accuracy of such weak learning methods.
  arXiv  Detail & Related papers  (2021-08-22T16:00:45Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  We show how iteration under a more standard notion of low inherent Bellman error, typically employed in least-square value-style algorithms, can provide strong PAC guarantees on learning a near optimal value function. We present a computationally tractable algorithm for the reward-free setting and show how it can be used to learn a near optimal policy for any (linear) reward function.
  arXiv  Detail & Related papers  (2020-08-18T04:34:21Z)
• Batch Value-function Approximation with Only Realizability [17.692408242465763]
  We make progress in a long-standing problem of batch reinforcement learning (RL): learning $Qstar$ from an exploratory dataset. Our algorithm, BVFT, breaks the hardness conjecture (albeit under a stronger notion of exploratory data) via a tournament procedure. We also discuss how BVFT can be applied to model selection among other extensions and open problems.
  arXiv  Detail & Related papers  (2020-08-11T20:09:37Z)

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.