論文の概要: Better Bounds for the Distributed Experts Problem

• arxiv url: http://arxiv.org/abs/2603.09168v1
• Date: Tue, 10 Mar 2026 04:17:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-11 15:25:24.023569
• Title: Better Bounds for the Distributed Experts Problem
• Title（参考訳）: 分散専門家問題のためのより良い境界
• Authors: David P. Woodruff, Samson Zhou,
• Abstract要約: 我々は分散専門家の問題を調査し、$n$の専門家が$s$サーバに分散して$T$タイムステップを提供する。 約$Rgtrsimfrac1sqrtTcdottextpolylog(nsT)$, using $mathcalOleft(fracnR2+fracsR2right)cdotmax(s1-2/p, 1)cdottextpolylog(nsT)$
• 参考スコア（独自算出の注目度）: 69.88181841362488
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study the distributed experts problem, where $n$ experts are distributed across $s$ servers for $T$ timesteps. The loss of each expert at each time $t$ is the $\ell_p$ norm of the vector that consists of the losses of the expert at each of the $s$ servers at time $t$. The goal is to minimize the regret $R$, i.e., the loss of the distributed protocol compared to the loss of the best expert, amortized over the all $T$ times, while using the minimum amount of communication. We give a protocol that achieves regret roughly $R\gtrsim\frac{1}{\sqrt{T}\cdot\text{poly}\log(nsT)}$, using $\mathcal{O}\left(\frac{n}{R^2}+\frac{s}{R^2}\right)\cdot\max(s^{1-2/p},1)\cdot\text{poly}\log(nsT)$ bits of communication, which improves on previous work.
• Abstract（参考訳）: 本稿では,$n$の専門家が$s$サーバに分散して$T$タイムステップを行う分散専門家問題について検討する。 各時点でのエキスパートの損失は$t$で、そのベクトルの$\ell_p$ノルムは、専門家の損失である。 目標は、最小の通信量を使用しながら、T$のすべての時間で償却された、最良専門家の損失と比較して、分散プロトコルの損失を最小化することである。 約$R\gtrsim\frac{1}{\sqrt{T}\cdot\text{poly}\log(nsT)}$, $\mathcal{O}\left(\frac{n}{R^2}+\frac{s}{R^2}\right)\cdot\max(s^{1-2/p},1)\cdot\text{poly}\log(nsT)$ bits of communication。

関連論文リスト

• Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach [26.085126064745378]
  そこでは,N$エージェントが協力してグローバルな平均損失を最小限に抑えつつ,ローカルな損失のみを観察する。 この問題のミニマックス後悔は$tilde(sqrt(-1/2+K/N)T)$であり、$T$は地平線、$K$は行動の数、$は通信行列のスペクトルギャップである。
  論文  参考訳（メタデータ） (2026-02-06T05:53:38Z)
• High-Dimensional Calibration from Swap Regret [40.9736612423411]
  任意の凸集合 $mathcalP 部分集合 mathbbRd$ 上での多次元予測のオンライン校正について検討する。 我々は、$O(sqrtrho T)$$$T$ラウンド後の最悪の後悔を保証できるならば、$T = exp(logd/epsilon2) の後、$epsilon$-calibrated 予測を得ることができることを示した。
  論文  参考訳（メタデータ） (2025-05-27T17:31:47Z)
• Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
  本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。 我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
  論文  参考訳（メタデータ） (2024-04-16T00:56:36Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
  強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。 改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
  論文  参考訳（メタデータ） (2023-05-24T17:40:57Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)

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

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