On the power of adaptivity in statistical adversaries

• URL: http://arxiv.org/abs/2111.10352v1
• Date: Fri, 19 Nov 2021 18:26:25 GMT
• Title: On the power of adaptivity in statistical adversaries
• Abstract summary: We study a fundamental question concerning adversarial noise models in statistical problems. Can the behavior of an algorithm $mathcalA'$ in the presence of oblivious adversaries always be well-approximated by that of an algorithm $mathcalA'$ in the presence of adaptive adversaries?
• Score: 18.973408992715203
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a fundamental question concerning adversarial noise models in statistical problems where the algorithm receives i.i.d. draws from a distribution $\mathcal{D}$. The definitions of these adversaries specify the type of allowable corruptions (noise model) as well as when these corruptions can be made (adaptivity); the latter differentiates between oblivious adversaries that can only corrupt the distribution $\mathcal{D}$ and adaptive adversaries that can have their corruptions depend on the specific sample $S$ that is drawn from $\mathcal{D}$. In this work, we investigate whether oblivious adversaries are effectively equivalent to adaptive adversaries, across all noise models studied in the literature. Specifically, can the behavior of an algorithm $\mathcal{A}$ in the presence of oblivious adversaries always be well-approximated by that of an algorithm $\mathcal{A}'$ in the presence of adaptive adversaries? Our first result shows that this is indeed the case for the broad class of statistical query algorithms, under all reasonable noise models. We then show that in the specific case of additive noise, this equivalence holds for all algorithms. Finally, we map out an approach towards proving this statement in its fullest generality, for all algorithms and under all reasonable noise models.

Related papers

• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise [5.296855056439798]
  We study linear contextual bandits under adversarial corruption and heavy-tailed noise.<n>Our algorithm achieves robustness to both adversarial corruption and heavy-tailed noise.
  arXiv  Detail & Related papers  (2026-03-16T17:53:06Z)
• Is nasty noise actually harder than malicious noise? [5.887031992513966]
  We consider the relative abilities and limitations of computationally efficient algorithms for learning in the presence of noise.<n>For distribution-independent learning, we prove a strong equivalence between the two noise models.<n>We show that for these algorithms, malicious noise and nasty noise are equivalent up to a factor of two in the noise rate.
  arXiv  Detail & Related papers  (2025-11-12T21:56:15Z)
• Adaptive and oblivious statistical adversaries are equivalent [18.385321286452747]
  We show that for all types of corruptions, sample-adaptive and sample-oblivious adversaries are emph up to equivalent factors in the sample size. We show that there is an algorithm $A'$ that solves the same task when the corresponding sample-adaptive adversary corrupts its input.
  arXiv  Detail & Related papers  (2024-10-17T13:42:56Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  Learning from human feedback plays an important role in aligning generative models, such as large language models (LLM) We study a model within this problem domain--contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary. We propose an algorithm namely robust contextual dueling bandit (algo), which is based on uncertainty-weighted maximum likelihood estimation.
  arXiv  Detail & Related papers  (2024-04-16T17:59:55Z)
• Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs [39.468324211376505]
  We study the efficient learnability of low-degree threshold functions (PTFs) in the presence of a constant fraction of adversarial corruptions. Our algorithm employs an iterative approach inspired by localization techniques previously used in the context of learning linear threshold functions.
  arXiv  Detail & Related papers  (2024-03-31T02:03:35Z)
• Corruption-Robust Offline Reinforcement Learning with General Function Approximation [60.91257031278004]
  We investigate the problem of corruption in offline reinforcement learning (RL) with general function approximation. Our goal is to find a policy that is robust to such corruption and minimizes the suboptimality gap with respect to the optimal policy for the uncorrupted Markov decision processes (MDPs)
  arXiv  Detail & Related papers  (2023-10-23T04:07:26Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  We show the first algorithms for the problem of regression for generalized linear models (GLMs) in the presence of additive oblivious noise. We present an algorithm that tackles newthis problem in its most general distribution-independent setting. This is the first newalgorithmic result for GLM regression newwith oblivious noise which can handle more than half the samples being arbitrarily corrupted.
  arXiv  Detail & Related papers  (2023-09-20T21:41:59Z)
• Minimax Rates for Robust Community Detection [19.229475414802213]
  We study the problem of community detection in the block model with adversarial node corruptions. Our main result is an efficient algorithm that can tolerate an $epsilon$-fraction of corruptions and unbounded error $O(epsilon) + e-fracC2 (1 pm o(1))$ where $C = (sqrta - sqrtb)2$ is the signal-to-noise ratio. We show that our algorithms are doubly-robust in the sense that they work in an even more
  arXiv  Detail & Related papers  (2022-07-25T04:45:16Z)
• Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions [98.75618795470524]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We propose a new algorithm based on the principle of optimism in the face of uncertainty.
  arXiv  Detail & Related papers  (2022-05-13T17:58:58Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
  arXiv  Detail & Related papers  (2021-10-25T02:53:24Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  We provide two variants of a Robust Phased Elimination algorithm, one that knows $C$ and one that does not. We show that both variants attain near-optimal regret in the non-corrupted case $C = 0$, while incurring additional additive terms respectively. In a contextual setting, we show that a simple greedy algorithm is provably robust with a near-optimal additive regret term, despite performing no explicit exploration and not knowing $C$.
  arXiv  Detail & Related papers  (2020-07-07T09:00:57Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack [41.060507338755784]
  This paper investigates the attack model where an adversary attacks with a certain probability at each round, and its attack value can be arbitrary and unbounded if it attacks. We propose a novel sample median-based and exploration-aided UCB algorithm (called med-E-UCB) and a median-based $epsilon$-greedy algorithm (called med-$epsilon$-greedy) Both algorithms are provably robust to the aforementioned attack model. More specifically we show that both algorithms achieve $mathcalO(log T)$ pseudo-regret (i.e
  arXiv  Detail & Related papers  (2020-02-17T19:21:08Z)

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.