論文の概要: Fast White-Box Adversarial Streaming Without a Random Oracle

• arxiv url: http://arxiv.org/abs/2406.06808v1
• Date: Mon, 10 Jun 2024 21:23:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-12 20:05:58.662111
• Title: Fast White-Box Adversarial Streaming Without a Random Oracle
• Title（参考訳）: ランダムなOracleのない高速なWhite-Box対応ストリーミング
• Authors: Ying Feng, Aayush Jain, David P. Woodruff,
• Abstract要約: 我々は,従来の無作為なコインとストリーミングアルゴリズムが使用するパラメータに,敵対者がアクセス可能な強力なホワイトボックス逆数モデルを考える。 我々はスパースリカバリ問題に焦点を合わせ、その結果を異なる要素推定などのタスクに拡張する。 ホワイトボックス逆数ストリームにおけるスパースリカバリ問題に対する準最適解を構築し, 誤りを仮定した学習に基づく。
• 参考スコア（独自算出の注目度）: 48.45771871410984
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, the question of adversarially robust streaming, where the stream is allowed to depend on the randomness of the streaming algorithm, has gained a lot of attention. In this work, we consider a strong white-box adversarial model (Ajtai et al. PODS 2022), 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 and low-rank approximation of matrices and tensors. The main drawback of previous work is that it requires a random oracle, which is especially problematic in the streaming model since the amount of randomness is counted in the space complexity of a streaming algorithm. Also, the previous work suffers from large update time. 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. Importantly, our solution does not require a random oracle and has a polylogarithmic per item processing time. We also give results in a related white-box adversarially robust distributed model. Our constructions are based on homomorphic encryption schemes satisfying very mild structural properties that are currently satisfied by most known schemes.
• Abstract（参考訳）: 近年,ストリームアルゴリズムのランダム性に依存してストリームを許す,逆向きに頑健なストリーミングの問題が注目されている。 本研究では,従来のランダムコインのすべてとストリーミングアルゴリズムが使用するパラメータにアクセス可能な,強力なホワイトボックス逆数モデル(Ajtai et al PODS 2022)について考察する。 我々はスパースリカバリ問題に焦点をあて、要素推定や行列やテンソルの低ランク近似といったタスクに結果を拡張した。 従来の研究の主な欠点は、ストリーミングアルゴリズムの空間的複雑さでランダム性がカウントされるため、ストリーミングモデルにおいて特に問題となるランダムオラクルを必要とすることである。 また、以前の作業は大きな更新時間に悩まされている。 ホワイトボックス逆数ストリームにおけるスパースリカバリ問題に対する準最適解を構築し, 誤りを仮定した学習に基づく。 重要なことは、我々のソリューションはランダムなオラクルを必要とせず、アイテム処理時間当たりの多対数性を持っている。 また、関連するホワイトボックスの頑健な分散モデルにも結果を与えます。 我々の構成は、現在知られているほとんどのスキームで満たされている非常に穏やかな構造特性を満たす同型暗号スキームに基づいている。

関連論文リスト

• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。 汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。 MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
  論文  参考訳（メタデータ） (2024-07-19T08:29:12Z)
• Correcting Subverted Random Oracles [55.4766447972367]
  簡単な構成は、少数の入力で元のものと矛盾する「反転」ランダムオラクルを、ランダム関数から微分不可能な対象に変換することができることを証明している。 この結果から, 暗号プリミティブの設計者は, 通常のクリプトグラフィ設定で, ランダムなオラクルを信頼できるブラックボックスとして使用することができる。
  論文  参考訳（メタデータ） (2024-04-15T04:01:50Z)
• Adversarially Robust Distributed Count Tracking via Partial Differential Privacy [17.43748116766233]
  分散機能監視(distributed functional monitoring)とも呼ばれる分散追跡モデルについて検討する。 このモデルは、各アイテムのストリームを受け取り、中央サーバと通信する、$k$のサイトを含む。 カウントトラッキングでは、決定論的アルゴリズムとランダム化アルゴリズムの通信に$sqrtk$ギャップがあることが知られている。
  論文  参考訳（メタデータ） (2023-11-01T07:42:13Z)
• Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model [14.204551125591022]
  逆ストリーミングアルゴリズムは、入力ストリームが適応的かつ逆方向に選択された場合でも、実用性を維持する必要がある。 不可避モデルと敵モデルとの補間を可能にする2つのモデルを提案する。 これにより、空間の複雑さを大幅に改善した堅牢なアルゴリズムを設計できる。
  論文  参考訳（メタデータ） (2023-01-22T21:13:13Z)
• Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
  三角形の数と4サイクルを推定するための,データ駆動型ワンパスストリーミングアルゴリズムを提案する。 従来の"古典的"アルゴリズムを改善するために、ストリーム要素の特定の特性を予測できるトレーニングされたオラクルを使用します。 提案手法は,従来のマルチパスおよびランダム順序ストリーミングアルゴリズムを特殊なケースとみなすことができるため,従来の"古典的"ストリーミングアルゴリズムの取り組みを拡大する。
  論文  参考訳（メタデータ） (2022-03-17T19:26:00Z)
• Correlation Clustering Reconstruction in Semi-Adversarial Models [70.11015369368272]
  相関クラスタリングは多くのアプリケーションにおいて重要なクラスタリング問題である。 本研究では,ランダムノイズや対向的な修正によって崩壊した潜伏クラスタリングを再構築しようとする,この問題の再構築版について検討する。
  論文  参考訳（メタデータ） (2021-08-10T14:46:17Z)
• A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators [26.151761714896118]
  本稿では,適応的相手が入力ストリームを選択した場合でも,証明可能な保証を提供するストリーミングアルゴリズムについて検討する。 本稿では,最近提案された2つのフレームワークをハイブリッドした,敵対的ストリーミングのための新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-07-30T10:20:38Z)
• Adversarial Robustness of Streaming Algorithms through Importance Sampling [29.957317489789745]
  我々は、中央の機械学習とアルゴリズムタスクに逆向きに頑健なストリーミングアルゴリズムを導入する。 我々の結果は、多くの重要なサンプリングベースのアルゴリズムが敵の堅牢性をもたらすという、単純だが強力で観察に基づいている。 我々は、様々な敵攻撃に対するアルゴリズムの堅牢性を実証的に確認し、対照的に、いくつかの一般的なアルゴリズムは堅牢ではないことを示す。
  論文  参考訳（メタデータ） (2021-06-28T19:24:11Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。