A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators

• URL: http://arxiv.org/abs/2107.14527v1
• Date: Fri, 30 Jul 2021 10:20:38 GMT
• Title: A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
• Authors: Idan Attias, Edith Cohen, Moshe Shechner, Uri Stemmer
• Abstract summary: We study streaming algorithms that provide provable guarantees even when the input stream is chosen by an adaptive adversary. We propose a novel framework for adversarial streaming that hybrids two recently suggested frameworks.
• Score: 26.151761714896118
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Streaming algorithms are algorithms for processing large data streams, using only a limited amount of memory. Classical streaming algorithms operate under the assumption that the input stream is fixed in advance. Recently, there is a growing interest in studying streaming algorithms that provide provable guarantees even when the input stream is chosen by an adaptive adversary. Such streaming algorithms are said to be {\em adversarially-robust}. We propose a novel framework for adversarial streaming that hybrids two recently suggested frameworks by Hassidim et al. (2020) and by Woodruff and Zhou (2021). These recently suggested frameworks rely on very different ideas, each with its own strengths and weaknesses. We combine these two frameworks (in a non-trivial way) into a single hybrid framework that gains from both approaches to obtain superior performances for turnstile streams.

Related papers

• Fast White-Box Adversarial Streaming Without a Random Oracle [48.45771871410984]
  We consider a strong white-box adversarial model, in which the adversary has access to all past random coins and the parameters used by the streaming algorithm. We focus on the sparse recovery problem and extend our result to other tasks such as distinct element estimation. We construct a near-optimal solution for the sparse recovery problem in white-box adversarial streams, based on the subexponentially secure Learning with Errors assumption.
  arXiv  Detail & Related papers  (2024-06-10T21:23:19Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  We propose a new learning framework for neural networks, namely Cascaded Forward (CaFo) algorithm, which does not rely on BP optimization as that in FF. Unlike FF, our framework directly outputs label distributions at each cascaded block, which does not require generation of additional negative samples. In our framework each block can be trained independently, so it can be easily deployed into parallel acceleration systems.
  arXiv  Detail & Related papers  (2023-03-17T02:01:11Z)
• Revisiting Random Channel Pruning for Neural Network Compression [159.99002793644163]
  Channel (or 3D filter) pruning serves as an effective way to accelerate the inference of neural networks. In this paper, we try to determine the channel configuration of the pruned models by random search. We show that this simple strategy works quite well compared with other channel pruning methods.
  arXiv  Detail & Related papers  (2022-05-11T17:59:04Z)
• Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
  We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles. We use a trained oracle that can predict certain properties of the stream elements to improve on prior "classical" algorithms. Our methodology expands upon prior work on "classical" streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases.
  arXiv  Detail & Related papers  (2022-03-17T19:26:00Z)
• Improved Multi-objective Data Stream Clustering with Time and Memory Optimization [0.0]
  This paper introduces a new data stream clustering method (IMOC-Stream) It uses two different objective functions to capture different aspects of the data. The experiments show the ability of our method to partition the data stream in arbitrarily shaped, compact, and well-separated clusters.
  arXiv  Detail & Related papers  (2022-01-13T17:05:56Z)
• Adversarial Robustness of Streaming Algorithms through Importance Sampling [29.957317489789745]
  We introduce adversarially robust streaming algorithms for central machine learning and algorithmic tasks. Our results are based on a simple, but powerful, observation that many importance sampling-based algorithms give rise to adversarial robustness. We empirically confirm the robustness of our algorithms on various adversarial attacks and demonstrate that by contrast, some common existing algorithms are not robust.
  arXiv  Detail & Related papers  (2021-06-28T19:24:11Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  We improve the scalability of Branch and Bound (BaB) algorithms for formally proving input-output properties of neural networks. We present a novel activation-based branching strategy and a BaB framework, named Branch and Dual Network Bound (BaDNB) BaDNB outperforms previous complete verification systems by a large margin, cutting average verification times by factors up to 50 on adversarial properties.
  arXiv  Detail & Related papers  (2021-04-14T09:22:42Z)
• Ranking and benchmarking framework for sampling algorithms on synthetic data streams [0.0]
  In big data, AI, and streaming processing, we work with large amounts of data from multiple sources. Due to memory and network limitations, we process data streams on distributed systems to alleviate computational and network loads. We provide algorithms that react to concept drifts and compare those against the state-of-the-art algorithms using our framework.
  arXiv  Detail & Related papers  (2020-06-17T14:25:07Z)
• Adversarially Robust Streaming Algorithms via Differential Privacy [68.3608356069755]
  A streaming algorithm is said to be adversarially robust if its accuracy guarantees are maintained even when the data stream is chosen maliciously. We establish a connection between adversarial robustness of streaming algorithms and the notion of differential privacy.
  arXiv  Detail & Related papers  (2020-04-13T14:49:38Z)

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.