論文の概要: Resilient Byzantine Agreement with Predictions
- arxiv url: http://arxiv.org/abs/2605.19452v1
- Date: Tue, 19 May 2026 07:06:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-20 15:03:09.177332
- Title: Resilient Byzantine Agreement with Predictions
- Title（参考訳）: 予測による回復力のあるビザンチン協定
- Authors: Julien Dallot, Darya Melnyk, Tijana Milentijevic, Stefan Schmid, Patrik Welters,
- Abstract要約: 本研究では,ノードが予測器にアクセス可能なビザンチン合意問題について検討する。
アルゴリズムのレジリエンス - アルゴリズムが許容できる最大障害ノード数。
我々は、その数が一定割合の$n$に留まる限り、レジリエンスは間違った予測数で線形に減少することを示した。
- 参考スコア（独自算出の注目度）: 4.2331787771494875
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies the Byzantine Agreement problem where the nodes have access to a predictor that flags nodes for suspicion of faulty (Byzantine) behavior. We focus on algorithmic resilience -- the maximum number of faulty nodes an algorithm can tolerate -- and present algorithms and impossibility results whose resilience depend on the accuracy of the predictor. As our first main result, we bring a complete characterization of the consistency--robustness trade-offs in both the non-authenticated and authenticated settings: for $n$ nodes and a parameter $α\in [0, 1]$, we present algorithms that tolerate up to $α\cdot n$ faulty nodes when the predictor is correct (consistency), and up to $\frac{1-α}{2} \cdot n - 1$ faulty nodes when the predictor is arbitrarily wrong (robustness); in the authenticated setting the robustness bound improves to $(1-α) \cdot n - 1$. These trade-offs are exactly tight as we show that one additional faulty node renders the problem impossible. Our second main result characterizes smoothness: the rate at which resilience degrades as the predictor becomes less accurate. We show that resilience linearly decreases in the number of wrong predictions as long as that number stays within a constant fraction of $n$. Concretely, in the non-authenticated setting each additional wrong prediction loses one unit of resilience, whereas in the authenticated setting the decline is halved since two wrong predictions are needed to lose one unit of resilience.
- Abstract（参考訳）: 本稿では、ノードが予測器にアクセスでき、ノードに障害(ビザンチン)の挙動を疑うよう警告するビザンチン合意問題について検討する。
我々はアルゴリズムのレジリエンス(アルゴリズムが許容できる障害ノードの最大数)に注目し、予測器の精度に依存するアルゴリズムと不合理性の結果を示す。
例えば、$n$ノードとパラメータ$α\in [0, 1]$の場合、予測者が正しい場合(一貫性)に最大$α\cdot n$障害ノードを許容するアルゴリズムと、予測者が任意に間違っている場合の最大$$$\frac{1-α}{2} \cdot n - 1$障害ノードを許容するアルゴリズムを提示します。
これらのトレードオフは、ひとつの障害ノードが問題を不可能にしていることを示すため、非常に厳密です。
予測器の精度が低下するにつれてレジリエンスが低下する速度が低下する。
我々は、その数が一定割合の$n$に留まる限り、レジリエンスは間違った予測数で線形に減少することを示した。
具体的には、非認証環境では、追加の誤予測はそれぞれ1つのレジリエンス単位を失うが、認証された設定では2つの誤った予測が1つのレジリエンス単位を失うために必要となるため、その低下は半減する。
関連論文リスト
- Fundamental Novel Consistency Theory: $H$-Consistency Bounds [19.493449206135296]
機械学習では、トレーニング中に最適化された損失関数は、タスクのパフォーマンスを定義するターゲット損失とは異なることが多い。
本稿では,サロゲート損失推定誤差に対する目標損失推定誤差について詳細に検討する。
私たちの分析では、$H$-一貫性境界が導かれ、これは仮説セットの$H$に対する説明が保証される。
論文 参考訳（メタデータ） (2025-12-28T11:02:20Z) - Beyond Greedy Exits: Improved Early Exit Decisions for Risk Control and Reliability [14.00844847268286]
早期のDeep Neural Networksは、中間層での予測を可能にすることで、適応推論を可能にする。
我々のフレームワークは、フルモデルのパフォーマンスと比較して、パフォーマンス低下(2%)を最小限に抑えながら、スピードアップ(1.70-2.10x)が一貫した改善を示している。
論文 参考訳（メタデータ） (2025-09-28T06:05:24Z) - Uncertainty-Aware Graph Neural Networks: A Multi-Hop Evidence Fusion Approach [55.43914153271912]
グラフニューラルネットワーク(GNN)は、グラフ構造とノード機能を統合することにより、グラフ表現学習に優れる。
既存のGNNでは、モデルの深さによって異なるクラス確率の不確実性を考慮することができず、現実のシナリオでは信頼できない、リスクの高い予測が生じる。
本稿では,信頼に値する予測を達成し,ノード分類精度を高め,誤予測のリスクを明らかにするために,新しいEvidence Fusing Graph Neural Network (EFGNN)を提案する。
論文 参考訳（メタデータ） (2025-06-16T03:59:38Z) - Adversarial Robustness of Nonparametric Regression [13.139603473712425]
回帰関数が2階ソボレフ空間に属することを前提として、非パラメトリック回帰における対向ロバスト性を特徴づける。
古典的なスムーズなスプライン推定器が適切に正規化されると、敵の汚職に対して頑健であることを示す。
論文 参考訳（メタデータ） (2025-05-23T00:18:20Z) - Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification [50.717692060500696]
対数損失を伴う次のトーケン予測は自己回帰シーケンスモデリングの基盤となる。
次トーケン予測は、適度な誤差増幅を表す$C=tilde O(H)$を達成するために堅牢にすることができる。
C=e(log H)1-Omega(1)$。
論文 参考訳（メタデータ） (2025-02-18T02:52:00Z) - Collective Robustness Certificates: Exploiting Interdependence in Graph
Neural Networks [71.78900818931847]
ノード分類、画像分割、名前付き一致認識といったタスクでは、複数の予測を同時に出力する分類器があります。
既存の対向ロバスト性証明は、それぞれの予測を独立に考慮し、従ってそのようなタスクに対して過度に悲観的である。
本稿では,摂動下で安定に保たれることが保証される予測数を計算した最初の集合ロバスト性証明を提案する。
論文 参考訳（メタデータ） (2023-02-06T14:46:51Z) - Learning to Predict Trustworthiness with Steep Slope Loss [69.40817968905495]
本研究では,現実の大規模データセットにおける信頼性の予測問題について検討する。
我々は、先行技術損失関数で訓練された信頼性予測器が、正しい予測と誤った予測の両方を信頼に値するものとみなす傾向があることを観察する。
そこで我々は,2つのスライド状の曲線による不正確な予測から,特徴w.r.t.正しい予測を分離する,新たな急勾配損失を提案する。
論文 参考訳（メタデータ） (2021-09-30T19:19:09Z) - Almost Tight L0-norm Certified Robustness of Top-k Predictions against
Adversarial Perturbations [78.23408201652984]
トップk予測は、マシンラーニング・アズ・ア・サービス、レコメンダ・システム、Web検索など、多くの現実世界のアプリケーションで使用されている。
我々の研究はランダム化平滑化に基づいており、入力をランダム化することで、証明可能なロバストな分類器を構築する。
例えば、攻撃者がテスト画像の5ピクセルを任意に摂動できる場合に、ImageNet上で69.2%の認定トップ3精度を達成する分類器を構築することができる。
論文 参考訳（メタデータ） (2020-11-15T21:34:44Z) - A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
より弱い仮定として, 2$-adjacency faithfulness を提案します。
より弱い仮定の下で適用可能な因果発見のための音方向規則を提案する。
論文 参考訳（メタデータ） (2020-10-27T13:04:08Z) - Revisiting One-vs-All Classifiers for Predictive Uncertainty and
Out-of-Distribution Detection in Neural Networks [22.34227625637843]
識別型分類器における確率のパラメトリゼーションが不確実性推定に与える影響について検討する。
画像分類タスクのキャリブレーションを改善するために, 1-vs-all の定式化が可能であることを示す。
論文 参考訳（メタデータ） (2020-07-10T01:55:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。