論文の概要: Optimal Lower Bounds for Networked Information Aggregation

• arxiv url: http://arxiv.org/abs/2608.15472v1
• Date: Sun, 16 Aug 2026 01:36:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-18 19:59:03.317065
• Title: Optimal Lower Bounds for Networked Information Aggregation
• Title（参考訳）: ネットワーク情報集約のための最適下界
• Abstract要約: 最悪のケースでは、ガウスのインスタンス上のネットワーク情報アグリゲーションが$ell$-errorを$(1/sqrtD)でバウンドする。
• 参考スコア（独自算出の注目度）: 3.130458422860269
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of networked information aggregation, studied in Kearns et al. (2026), involves a group of learners situated on the vertices of a directed acyclic graph $G$, each learning a linear predictor $\widehat Y$ for a fixed random variable $Y$ given access to a local feature, as well as the predictors learnt by its parents. Learning proceeds iteratively, with learners ordered according to a topological sort of $G$. The main quantity of interest is the error incurred by the current learner, constrained to this flow of information, with respect to the best linear predictor using all the features seen so far. When the studied error is the MSE, i.e., $\mathbb{E} (\widehat Y - Y)^2$, Kearns et al. (2026) show that the error is at most $O(1/\sqrt{D})$ along a path of length $D$. They also obtain a hard instance where the MSE is lower bounded by $Ω(1/D)$, leaving the correct order open. In this work, we resolve this central open problem, and obtain a family of worst case problem instances with a MSE lower bound of $Ω(1/\sqrt{D})$. By exploiting invariances in the structure of the learnt predictors, our analysis generalizes to all convex loss functions $\ell(\widehat Y, Y)$ satisfying regularity conditions which include strong convexity in a ball around the origin, and that the ideal predictor minimizing the population loss is positively correlated with the label. We show that networked information aggregation on a gaussian instance in our worst case family incurs an $\ell$-error lower bounded by $Ω(1/\sqrt{D})$ with respect to this ideal predictor. We demonstrate that a variety of common losses satisfy these regularity conditions. In particular, the logistic loss satisfies them, and hence our analysis also closes the gap between the upper and lower bounds in Bateni et al. (2026).
• Abstract（参考訳）: Kearns et al (2026) で研究されているネットワーク情報集約の問題は、有向非巡回グラフの頂点に位置する学習者のグループ$G$、各学習者は、局所的特徴へのアクセスを与えられた固定確率変数$Y$に対して$\widehat Y$、およびその両親が学習した予測者を含む。 学習は反復的に進み、学習者はトポロジカルな$G$で注文される。 主な関心事は、この情報の流れに制約された現在の学習者が引き起こした誤りであり、これまで見た全ての特徴を用いた最良の線形予測器についてである。 研究された誤差が MSE であるとき、すなわち $\mathbb{E} (\widehat Y - Y)^2$, Kearns et al (2026) は、誤差が少なくとも$O(1/\sqrt{D})$であることを示す。 彼らはまた、MSE が$Ω(1/D)$ で下界し、正しい順序が開となるハードケースを得る。 本研究では、この中心的開問題を解き、MSE が $Ω(1/\sqrt{D})$ である最悪のケース問題の族を得る。 学習した予測器の構造の不変性を利用して、この分析は全ての凸損失関数 $\ell(\widehat Y, Y)$ に一般化され、原点付近の球に強い凸性を含む規則性条件を満たす。 最悪のケースでは、ガウスのインスタンス上のネットワーク情報集約は、この理想的な予測器に対して$$\ell$-errorを$Ω(1/\sqrt{D})$で束縛する。 様々な共通損失がこれらの規則性条件を満たすことを実証する。 特に、ロジスティックな損失はそれらを満たすため、我々の分析はBateni et al (2026) の上下境界のギャップを埋める。

関連論文リスト

• Optimal Rates for Agentic Networked Information Aggregation [14.181355030230309]
  ネットワーク学習モデルにおける情報集約について検討する。 エージェントはDAGに座り、それぞれが特徴とその両親の予測のサブセットしか見ず、線形予測器に適合し、予測のみを前方に通過する。 我々は,Bateni et alのロジットパスモデルにおいて,ロジスティックな分類に最適であることを示す。
  論文  参考訳（メタデータ） (2026-09-04T16:12:16Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  自己蒸留(英: Self-distillation, SD)とは、教師自身の予測と地道の混合で学生を訓練する過程である。 任意の予測リスクに対して、各正規化レベルにおいて、最適に混合された学生がリッジ教師に改善されることが示される。 本稿では,グリッド探索やサンプル分割,再構成なしに$star$を推定する一貫したワンショットチューニング手法を提案する。
  論文  参考訳（メタデータ） (2026-02-19T17:21:15Z)
• Entangled Mean Estimation in High-Dimensions [36.97113089188035]
  信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。 最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
  論文  参考訳（メタデータ） (2025-01-09T18:31:35Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Optimal Multiclass U-Calibration Error and Beyond [31.959887895880765]
  オンラインマルチクラス境界U-キャリブレーションの問題は、予測器がU-キャリブレーション誤差の低いクラスをK$で逐次分布予測することを目的としている。 最適U校正誤差は$Theta(sqrtKT)$である。
  論文  参考訳（メタデータ） (2024-05-28T20:33:18Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Black-Box Generalization [31.80268332522017]
  微分一般化によるブラックボックス学習のための最初の誤り解析を行う。 どちらの一般化も独立$d$,$K$であり、適切な選択の下では学習率がわずかに低下していることを示す。
  論文  参考訳（メタデータ） (2022-02-14T17:14:48Z)
• An Improved Analysis of Gradient Tracking for Decentralized Machine Learning [34.144764431505486]
  トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。 エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。 ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
  論文  参考訳（メタデータ） (2022-02-08T12:58:14Z)
• Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers [13.244654316770815]
  我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。 スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。 PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
  論文  参考訳（メタデータ） (2021-11-04T15:59:44Z)
• Locality defeats the curse of dimensionality in convolutional teacher-student scenarios [69.2027612631023]
  学習曲線指数$beta$を決定する上で,局所性が重要であることを示す。 我々は、自然の仮定を用いて、トレーニングセットのサイズに応じて減少するリッジでカーネルレグレッションを実行すると、リッジレスの場合と同じような学習曲線指数が得られることを証明して結論付けた。
  論文  参考訳（メタデータ） (2021-06-16T08:27:31Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。 ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。 本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T19:08:53Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)

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

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