論文の概要: Optimal Rates for Agentic Networked Information Aggregation
- arxiv url: http://arxiv.org/abs/2609.05318v1
- Date: Fri, 04 Sep 2026 16:12:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-07 18:15:24.11253
- Title: Optimal Rates for Agentic Networked Information Aggregation
- Title（参考訳）: エージェントネットワーク情報集約のための最適レート
- Abstract要約: ネットワーク学習モデルにおける情報集約について検討する。
エージェントはDAGに座り、それぞれが特徴とその両親の予測のサブセットしか見ず、線形予測器に適合し、予測のみを前方に通過する。
我々は,Bateni et alのロジットパスモデルにおいて,ロジスティックな分類に最適であることを示す。
- 参考スコア（独自算出の注目度）: 14.181355030230309
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Building on the pioneering paper of Kearns, Roth, and Ryu (SODA'26), we study information aggregation in a networked learning model. The model captures a central pattern in agentic AI: each agent sees only part of the data and passes on only its own conclusion. Their model considers a linear regression problem with the mean squared error (MSE) loss. Agents sit in a DAG and each sees only a subset of the features and its parents' predictions, fits a linear predictor, and passes only its prediction forward. The benchmark is the full-feature learner that sees all raw features. A path of depth $D$ is $M$-covered if every block of $M$ consecutive agents collectively sees all raw features. Kearns, Roth, and Ryu proved that the excess mean squared error of the last agent on such a path is $O(M/\sqrt D)$, and gave a cyclic instance with excess error $Ω(M/D)$ for $D<M^2$. We close this gap: the correct rate is constant up to depth $M^2$, and $Θ(M^2/D)$ beyond it. We first give a sharper analysis of the cyclic instance and improve its lower bound to $Ω(\sqrt{M/D})$ for $D<M^2$. We then construct, for every depth $D\ge M^2$, an $M$-covered path of depth $D$ with excess error $Ω(M^2/D)$. The same instance gives the constant lower bound for all $D < M^2$. We also show that for any fixed distribution the excess error contracts geometrically along the path, ruling out any single instance that witnesses any polynomial lower bound at every depth. Finally, we prove the same optimal rate for logistic classification in the logit-passing model of Bateni et al., which considers the binary cross-entropy (BCE) loss. The same improved upper bound of $O(M^2/D)$ holds, and we transfer all the regression lower bounds by showing that on those examples the logistic path follows the least-squares path up to rescaling.
- Abstract（参考訳）: Kearns,Roth,Ryu(SODA'26)の先駆的な論文に基づいて,ネットワーク学習モデルにおける情報集約について検討する。
モデルはエージェントAIの中心的なパターンをキャプチャする。各エージェントはデータの一部だけを見て、独自の結論のみをパスする。
彼らのモデルは平均二乗誤差(MSE)損失を伴う線形回帰問題を考える。
エージェントはDAGに座り、それぞれが特徴とその両親の予測のサブセットしか見ず、線形予測器に適合し、予測のみを前方に通過する。
ベンチマークは、すべての生の機能を見ることができるフル機能の学習者だ。
深さ$D$のパスは、M$連続エージェントのすべてのブロックがすべての生のフィーチャを集合的に見る場合、$M$-coveredである。
Kearns, Roth, Ryu は、そのような経路上の最後のエージェントの余剰平均二乗誤差が$O(M/\sqrt D)$であり、過剰なエラーが$Ω(M/D)$ for $D<M^2$であることを示した。
我々はこのギャップを閉じる: 正しいレートは深さ$M^2$まで一定であり、それを超える$(M^2/D)$である。
まず、巡回インスタンスのよりシャープな解析を行い、その下限を$Ω(\sqrt{M/D})$ for $D<M^2$に改善する。
次に、すべての深さ$D\ge M^2$に対して、過剰な誤差$Ω(M^2/D)$を持つ深さ$D$のM$被覆パスを構築する。
同じ例はすべての$D < M^2$に対して定数下界を与える。
また、任意の固定分布に対して、過大な誤差は経路に沿って幾何的に制約され、すべての深さで下界の多項式を目撃する任意の単一のインスタンスを除外することを示した。
最後に,Bateni et al のロジスティック・パスモデルにおいて,二進的クロスエントロピー(BCE)損失を考慮したロジスティックな分類に最適であることを示す。
同じ改善された$O(M^2/D)$ hold の上界は、これらの例でロジスティックパスが再スケーリングまでの最小二乗パスに従うことを示すことによって、すべての回帰下界を転送する。
関連論文リスト
- Optimal Lower Bounds for Networked Information Aggregation [3.130458422860269]
最悪のケースでは、ガウスのインスタンス上のネットワーク情報アグリゲーションが$ell$-errorを$(1/sqrtD)でバウンドする。
論文 参考訳（メタデータ） (2026-08-16T01:36:33Z) - Optimal Reconstruction from Linear Queries [22.749520200232624]
近似線形クエリから$mathbbRd$の未知点を再構成する問題について検討する。
この設定は、低次元リモートセンシングや信号回復から高次元データ分析、プライバシーに敏感な推論まで、様々なアプリケーションで自然に発生する。
論文 参考訳（メタデータ） (2026-05-19T10:04:37Z) - The Hidden Width of Deep ResNets: Tight Error Bounds and Phase Diagrams [15.246178589173523]
大深度残差ネットワーク(ResNets)の勾配に基づくトレーニングについて検討する。
可変深さ$L$,固定埋め込み寸法$D$,任意の隠れ幅$M$で、トレーニングダイナミクスはニューラル平均ODEトレーニングダイナミクスに収束することを示す。
論文 参考訳（メタデータ） (2025-09-12T11:51:44Z) - Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。
この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。
この設定のための最初のポリシー最適化アルゴリズムを紹介します。
論文 参考訳（メタデータ） (2025-02-06T12:03:24Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。
SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Convergence Analysis of Probability Flow ODE for Score-based Generative Models [5.939858158928473]
確率フローODEに基づく決定論的サンプリング器の収束特性を理論的・数値的両面から検討する。
連続時間レベルでは、ターゲットと生成されたデータ分布の総変動を$mathcalO(d3/4delta1/2)$で表すことができる。
論文 参考訳（メタデータ） (2024-04-15T12:29:28Z) - Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Provably Efficient Offline Reinforcement Learning with Trajectory-Wise
Reward [66.81579829897392]
我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。
PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。
私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
論文 参考訳（メタデータ） (2022-06-13T19:11:22Z) - Understanding Gradual Domain Adaptation: Improved Analysis, Optimal Path
and Beyond [20.518134448156744]
グラデーショナルドメイン適応(GDA)は、ソースとターゲットをブリッジする未ラベルの中間ドメインのパスを$(T-1)と仮定する。
我々は、$widetildeOleft(varepsilon_0+Oleft(sqrtlog(T)/nright)$, $Delta$が連続ドメイン間の平均分布距離であることを示す。
論文 参考訳（メタデータ） (2022-04-18T07:39:23Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。