論文の概要: Linear Stochastic Bandits over a Bit-Constrained Channel
- arxiv url: http://arxiv.org/abs/2203.01198v1
- Date: Wed, 2 Mar 2022 15:54:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-03 19:31:10.182510
- Title: Linear Stochastic Bandits over a Bit-Constrained Channel
- Title（参考訳）: ビット制約チャネル上の線形確率帯域
- Authors: Aritra Mitra, Hamed Hassani and George J. Pappas
- Abstract要約: 我々は,ビット制約チャネル上に線形バンドレットの新たな定式化を導入する。
サーバの目標は、未知のモデルパラメータの推定値に基づいてアクションを取ることで、累積的後悔を最小限に抑えることである。
未知のモデルが$d$-dimensionalである場合、チャネル容量は$O(d)$ bits suffices で順序最適後悔を実現する。
- 参考スコア（独自算出の注目度）: 37.01818450308119
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: One of the primary challenges in large-scale distributed learning stems from
stringent communication constraints. While several recent works address this
challenge for static optimization problems, sequential decision-making under
uncertainty has remained much less explored in this regard. Motivated by this
gap, we introduce a new linear stochastic bandit formulation over a
bit-constrained channel. Specifically, in our setup, an agent interacting with
an environment transmits encoded estimates of an unknown model parameter to a
server over a communication channel of finite capacity. The goal of the server
is to take actions based on these estimates to minimize cumulative regret. To
this end, we develop a novel and general algorithmic framework that hinges on
two main components: (i) an adaptive encoding mechanism that exploits
statistical concentration bounds, and (ii) a decision-making principle based on
confidence sets that account for encoding errors. As our main result, we prove
that when the unknown model is $d$-dimensional, a channel capacity of $O(d)$
bits suffices to achieve order-optimal regret. To demonstrate the generality of
our approach, we then show that the same result continues to hold for
non-linear observation models satisfying standard regularity conditions.
Finally, we establish that for the simpler unstructured multi-armed bandit
problem, $1$ bit channel-capacity is sufficient for achieving optimal regret
bounds. Overall, our work takes a significant first step towards paving the way
for statistical decision-making over finite-capacity channels.
- Abstract（参考訳）: 大規模分散学習の主な課題の1つは、厳密なコミュニケーション制約にある。
最近のいくつかの研究は静的最適化問題に対するこの問題に対処しているが、不確実性の下でのシーケンシャルな意思決定は、この点に関してあまり検討されていない。
このギャップに動機づけられ,ビット制約されたチャネル上での新しい線形確率バンディット定式化を導入する。
具体的には,環境と対話するエージェントが未知のモデルパラメータの符号化された推定値を,有限容量の通信チャネル上のサーバに送信する。
サーバの目標は、これらの見積もりに基づいてアクションを取り、累積的な後悔を最小限に抑えることです。
この目的のために,2つの主成分に係わる新しい汎用アルゴリズムフレームワークを開発した。
(i)統計濃度境界を利用する適応符号化機構、
(二 誤りのエンコーディングを理由とする信頼度に基づく意思決定原則。)
主な結果として、未知のモデルが$d$-dimensionalである場合、チャネル容量は$O(d)$ bits で、順序-最適後悔を達成するのに十分であることを示す。
提案手法の一般性を示すため, 標準正則性条件を満たす非線形観測モデルに対して, 同じ結果が引き続き成り立つことを示す。
最後に、より単純な非構造的マルチアームバンディット問題に対して、最適な後悔境界を達成するのに1ドルのビットチャネル容量が十分であることを示す。
全体として、我々の研究は、有限容量チャネルに対する統計的意思決定の道を開くための重要な第一歩を踏み出した。
関連論文リスト
- Neighbor-Aware Calibration of Segmentation Networks with Penalty-Based
Constraints [19.897181782914437]
本稿では,ロジット値の等式制約に基づく基本的かつ単純な解を提案し,強制制約と罰則の重みを明示的に制御する。
我々のアプローチは、広範囲のディープセグメンテーションネットワークのトレーニングに利用できる。
論文 参考訳（メタデータ） (2024-01-25T19:46:57Z) - Towards Model-Free LQR Control over Rate-Limited Channels [2.908482270923597]
作業者エージェントが(LQRコストの)量子化ポリシー勾配を有限ビットレートのノイズレスチャネル上でサーバに送信する環境について検討する。
我々は、適応量子化グラディエントDescent (textttAQGD) という新しいアルゴリズムを提案し、ある有限しきい値ビットレートを超えると、textttAQGDは、グローバルな最適ポリシーへの指数的に高速な収束を保証することを証明した。
論文 参考訳（メタデータ） (2024-01-02T15:59:00Z) - A Pseudo-Semantic Loss for Autoregressive Models with Logical
Constraints [87.08677547257733]
ニューロシンボリックAIは、純粋にシンボリックな学習とニューラルな学習のギャップを埋める。
本稿では,ニューラルネットワークの出力分布に対するシンボリック制約の可能性を最大化する方法を示す。
また,スドクと最短経路予測の手法を自己回帰世代として評価した。
論文 参考訳（メタデータ） (2023-12-06T20:58:07Z) - Sub-linear Regret in Adaptive Model Predictive Control [56.705978425244496]
本稿では,STT-MPC (Self-Tuning tube-based Model Predictive Control) について述べる。
システム力学を最初に認識したアルゴリズムと比較して,アルゴリズムの後悔を解析する。
論文 参考訳（メタデータ） (2023-10-07T15:07:10Z) - Trust your neighbours: Penalty-based constraints for model calibration [19.437451462590108]
SVLSの制約付き最適化の観点を示し、周辺画素のソフトクラス比に暗黙の制約を課すことを示した。
本稿では,ロジット値の等式制約に基づく基本的かつ単純な解を提案し,強制制約と罰則の重みを明示的に制御する。
論文 参考訳（メタデータ） (2023-03-11T01:10:26Z) - Toward Certified Robustness Against Real-World Distribution Shifts [65.66374339500025]
我々は、データから摂動を学ぶために生成モデルを訓練し、学習したモデルの出力に関して仕様を定義する。
この設定から生じるユニークな挑戦は、既存の検証者がシグモイドの活性化を厳密に近似できないことである。
本稿では,古典的な反例誘導的抽象的洗練の概念を活用するシグモイドアクティベーションを扱うための一般的なメタアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-08T04:09:13Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳（メタデータ） (2020-08-20T03:48:14Z) - Breaking the Communication-Privacy-Accuracy Trilemma [19.399122892615573]
分散学習における2つの大きな課題は、ローカルサンプルのプライバシを保持し、それらを中央サーバに効率的に伝達することである。
我々は、最適なプライバシーと通信効率を同時に達成する新しい符号化・復号機構を開発する。
論文 参考訳（メタデータ） (2020-07-22T22:43:01Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z) - Robust-Adaptive Control of Linear Systems: beyond Quadratic Costs [14.309243378538012]
線形システムのロバストかつ適応的なモデル予測制御(MPC)の問題を考える。
この設定に対して、最初のエンドツーエンドのサブ最適トラクティリティ解析を提供する。
論文 参考訳（メタデータ） (2020-02-25T12:24:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。