論文の概要: Fast-MWEM: Private Data Release in Sublinear Time

• arxiv url: http://arxiv.org/abs/2602.03732v1
• Date: Tue, 03 Feb 2026 16:51:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-04 18:37:15.588025
• Title: Fast-MWEM: Private Data Release in Sublinear Time
• Title（参考訳）: Fast-MWEM: サブラインタイムでプライベートデータリリース
• Authors: Themistoklis Haris, Steve Choi, Mutiraj Laksanawisit,
• Abstract要約: MWEM(Multiplicative Weights Exponential Mechanism)は、個人データ分析のための基本的な反復的フレームワークである。 MWEMフレームワークに修正を加えて,設定実行時の依存性を期待値$(sqrtm)$に改善する。 これは、Gumbelノイズと$k$-Nearest Neighborデータ構造を用いて効率的に実装するReport-Noisy-Maxメカニズムへの遅延サンプリング手法によって実現される。
• 参考スコア（独自算出の注目度）: 3.8233569758620054
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Multiplicative Weights Exponential Mechanism (MWEM) is a fundamental iterative framework for private data analysis, with broad applications such as answering $m$ linear queries, or privately solving systems of $m$ linear constraints. However, a critical bottleneck hindering its scalability is the $Θ(m)$ time complexity required to execute the exponential mechanism in each iteration. We introduce a modification to the MWEM framework that improves the per-iteration runtime dependency to $Θ(\sqrt{m})$ in expectation. This is done via a lazy sampling approach to the Report-Noisy-Max mechanism, which we implement efficiently using Gumbel noise and a $k$-Nearest Neighbor data structure. This allows for the rapid selection of the approximate score in the exponential mechanism without an exhaustive linear scan. We apply our accelerated framework to the problems of private linear query release and solving Linear Programs (LPs) under neighboring constraint conditions and low-sensitivity assumptions. Experimental evaluation confirms that our method provides a substantial runtime improvement over classic MWEM.
• Abstract（参考訳）: Multiplicative Weights Exponential Mechanism (MWEM) は、$m$リニアクエリの応答や$m$リニア制約のシステムをプライベートに解決するといった幅広いアプリケーションを備えた、プライベートデータ分析のための基本的な反復フレームワークである。 しかし、そのスケーラビリティを妨げる重要なボトルネックは、各イテレーションで指数的なメカニズムを実行するのに必要な$(m)$時間複雑さである。 本稿では,MWEMフレームワークを改良し,設定実行時の依存性を期待値の$(\sqrt{m})$に改善する。 これは、Gumbelノイズと$k$-Nearest Neighborデータ構造を用いて効率的に実装するReport-Noisy-Maxメカニズムへの遅延サンプリング手法によって実現される。 これにより、指数的なメカニズムにおける近似スコアの迅速な選択が、徹底的な線形スキャンなしで可能となる。 本稿では,近傍の制約条件および低感度仮定下での線形クエリリリースと線形プログラム(LP)の解問題に対して,高速化されたフレームワークを適用した。 実験により,本手法が従来のMWEMよりも大幅なランタイム改善を実現することを確認した。

関連論文リスト

• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$は、投機的デコードにインスパイアされた遅延対応のテスト時間スケーリングメソッドである。 我々の結果は、$textttSPECS$matchはビームサーチの精度を上回り、最大$sim$19.1%のレイテンシを削減していることを示している。
  論文  参考訳（メタデータ） (2025-06-15T05:50:05Z)
• Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints [14.341123057506827]
  大規模言語モデル(LLM)は、今日のアプリケーションでは必須であるが、推論手順は重要な計算資源を必要とする。 本稿では,多段階オンラインスケジューリング問題としてLLM推論最適化を定式化する。 我々は,アルゴリズム設計をガイドするトラクタブルなベンチマークを提供するために,流体力学近似を開発した。
  論文  参考訳（メタデータ） (2025-04-15T16:00:21Z)
• Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits [8.013444110633223]
  自動機構設計のための線形プログラム(LP)に最適解のクラスを解析的に導出する。 これらの解は、元の定式化における変数の総数よりも指数関数的に小さい基本変数の集合を用いて表すことができる。 本稿では,この用語の評価をマルチアーム・バンディット(MAB)問題に翻訳することでこの問題に対処する。
  論文  参考訳（メタデータ） (2024-11-30T03:59:36Z)
• Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement Learning in Discounted Linear MDPs [16.006893624836554]
  本稿では,VBMLE (Value-Biased Maximum Likelihood Estimation) のレンズによる線形MDPの解法を提案する。 VBMLEは、各時間ステップで1つの最適化問題だけを解決する必要があるため、計算的により効率的である。 後悔する解析では、線形MDPにおけるMLEの一般収束結果が、新しいスーパーマーチンゲール構造を通して提供される。
  論文  参考訳（メタデータ） (2023-10-17T18:27:27Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints [26.008426384903764]
  オフライン強化学習(RL)は、事前に収集されたデータセットを使用して、マルコフ決定プロセス(MDP)の最適ポリシーを見つけることを目的としている。 本研究では,オフラインRLにおけるマルコフ決定過程の線形プログラミング (LP) の再検討を行う。
  論文  参考訳（メタデータ） (2022-12-28T15:28:12Z)
• Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences [52.6022911513076]
  トランスフォーマーベースのモデルは、自己アテンションモジュールの二次空間と時間的複雑さのために、長いシーケンスを処理するのに効率的ではない。 我々はLinformerとInformerを提案し、低次元投影と行選択により2次複雑性を線形(モジュラー対数因子)に還元する。 理論的解析に基づいて,Skeinformerを提案することにより,自己注意の促進と,自己注意への行列近似の精度の向上を図ることができる。
  論文  参考訳（メタデータ） (2021-12-10T06:58:05Z)

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

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