Fugu-MT 論文翻訳(概要): Fast Simulation Algorithms for OLH using Binomial Modeling

論文の概要: Fast Simulation Algorithms for OLH using Binomial Modeling

arxiv url: http://arxiv.org/abs/2608.15778v1
Date: Sun, 16 Aug 2026 14:58:13 GMT
ステータス: 翻訳完了
システム内更新日: 2026-08-18 19:59:03.420914
Title: Fast Simulation Algorithms for OLH using Binomial Modeling
Title（参考訳）: 二項モデリングを用いたOLHの高速シミュレーションアルゴリズム
Abstract要約: 二項モデリングに基づくOLHの高速シミュレーションアルゴリズムを2つ提案する。我々のアルゴリズムは、統計的等価性を損なうことなく、シミュレーションの複雑さを$O(n + d)$に減らす。実世界のデータセットの実験では、両方のアプローチが実行時間を数分からミリ秒に短縮することを確認した。
参考スコア（独自算出の注目度）: 1.529342790344802
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: Optimized Local Hashing (OLH) is a widely used hash-based Local Differential Privacy (LDP) protocol, and simulation-based experimentation is the standard approach for evaluating OLH and OLH-based applications in research. However, the existing OLH simulations have $O(nd)$ computational complexity, where $n$ is the user population size and $d$ is the domain size, and can lead to significant execution times as $n$ and $d$ grow. In this paper, we propose two fast simulation algorithms for OLH (2-Binom and 3-Binom) grounded in Binomial modeling. Our key insight is that, for any domain value $v$, the total number of users whose perturbed reports support $v$ can be decomposed into a sum of two or three Binomial random variables. Using this insight, our algorithms reduce the simulation complexity to $O(n + d)$ without hurting statistical equivalence. In particular, we theoretically prove that both algorithms yield unbiased frequency estimations with variances identical to those of the original OLH simulations. Experiments on real-world datasets confirm that both approaches reduce execution times from several minutes to milliseconds, yielding significant speedups with no change in utility.
Abstract（参考訳）: 最適化ローカルハッシュ(OLH)は、広く使われているハッシュベースのローカル微分プライバシー(LDP)プロトコルであり、シミュレーションベースの実験は、研究におけるOLHおよびOLHベースのアプリケーションを評価する標準的なアプローチである。しかし、既存のOLHシミュレーションでは、$O(nd)$計算の複雑さがあり、$n$はユーザ人口サイズ、$d$はドメインサイズであり、$n$と$d$の成長という大きな実行時間につながる可能性がある。本稿では,二項モデリングに基づくOLH(2-ビノムと3-ビノム)の高速シミュレーションアルゴリズムを提案する。私たちのキーとなる洞察は、任意のドメイン値$v$に対して、混乱したレポートが$v$をサポートするユーザの総数は、2つまたは3つのバイナリランダム変数の和に分解できるということです。この知見を用いて、我々のアルゴリズムは、統計的等価性を損なうことなく、シミュレーションの複雑さを$O(n + d)$に減らした。特に、両アルゴリズムが元のOLHシミュレーションと同一のばらつきで非バイアス周波数推定を行うことを理論的に証明する。実世界のデータセットの実験では、どちらのアプローチも実行時間を数分からミリ秒に短縮し、ユーティリティの変更なしに大幅なスピードアップを実現している。

関連論文リスト

$V_1$: Unifying Generation and Self-Verification for Parallel Reasoners [69.66089681814013]
$V_$は、効率的なペアワイドランキングを通じて生成と検証を統合するフレームワークである。 V_$-Inferはポイントワイド検証でPass@1を最大10%改善する。 V_$-PairRLは、標準のRLとポイントワイドのジョイントトレーニングよりも、テストタイムのスケーリングが7ドル--9%で向上する。
論文参考訳（メタデータ） (2026-03-04T17:22:16Z)
Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文参考訳（メタデータ） (2024-11-29T05:29:47Z)
Scalable Time-Series Causal Discovery with Approximate Causal Ordering [5.430532390358285]
時系列データにおける因果発見は、重要な計算上の課題を示す。 VarLiNGAM法は反復探索に依存し、各ステップの後に統計的依存関係を再計算する。提案アルゴリズムは,標準実装よりも7-13倍の高速化を実現し,GPUアクセラレーション版より4.5倍の高速化を実現している。
論文参考訳（メタデータ） (2024-09-09T10:52:58Z)
Quantum Advantage via Efficient Post-processing on Qudit Classical Shadow tomography [3.040305634723913]
計算量と記憶量の両方を削減できるquditシャドウトモグラフィーに基づく量子的アプローチを提案する。 (operatornametr(rho O)) は (textpoly(log d)) 計算で効率的に推定できる。
論文参考訳（メタデータ） (2024-08-29T03:56:16Z)
Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima [12.009357100208353]
本稿では,最適化アルゴリズムが大規模最適集合を処理する方法の研究を支援するために,テスト関数EqualBlocksOneMax(EBOM)を提案する。 EBOM は EBOM の理論的に理想的なモデルと非常によく似ており、このモデルは同じ最大確率で指数的に多くの最適値のそれぞれをサンプリングする。
論文参考訳（メタデータ） (2023-10-06T06:32:07Z)
Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimization [41.28002701420715]
ミニマックス最適化は多くの機械学習タスクに広く応用されている。我々は,本手法が特定の型に依存することなく,最もよく知られたサンプル複雑性を有することを示す。
論文参考訳（メタデータ） (2023-03-07T15:33:12Z)
Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文参考訳（メタデータ） (2023-02-20T23:29:43Z)
Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文参考訳（メタデータ） (2022-02-23T02:39:04Z)
Quantum Algorithms for Reinforcement Learning with a Generative Model [16.168901236223117]
強化学習は、エージェントがその累積報酬を最大化するために環境とどのように相互作用するかを研究する。最適ポリシー(pi*$)、最適値関数(v*$)、最適値関数(q*$)を近似する量子アルゴリズムを設計する。一致する量子下界を証明して、q*$を計算するための量子アルゴリズムが最適であることを示す。
論文参考訳（メタデータ） (2021-12-15T19:51:49Z)
Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文参考訳（メタデータ） (2020-07-15T03:25:24Z)
Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文参考訳（メタデータ） (2020-02-21T18:30:48Z)
Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文参考訳（メタデータ） (2020-01-17T18:47:02Z)

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

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