論文の概要: PopArt: Efficient Sparse Regression and Experimental Design for Optimal
Sparse Linear Bandits
- arxiv url: http://arxiv.org/abs/2210.15345v2
- Date: Fri, 8 Sep 2023 19:56:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-12 23:00:40.354701
- Title: PopArt: Efficient Sparse Regression and Experimental Design for Optimal
Sparse Linear Bandits
- Title（参考訳）: PopArt: 効率的なスパース回帰と最適スパース線形帯域の実験的設計
- Authors: Kyoungseok Jang, Chicheng Zhang, Kwang-Sung Jun
- Abstract要約: そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。
我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
- 参考スコア（独自算出の注目度）: 29.097522376094624
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In sparse linear bandits, a learning agent sequentially selects an action and
receive reward feedback, and the reward function depends linearly on a few
coordinates of the covariates of the actions. This has applications in many
real-world sequential decision making problems. In this paper, we propose a
simple and computationally efficient sparse linear estimation method called
PopArt that enjoys a tighter $\ell_1$ recovery guarantee compared to Lasso
(Tibshirani, 1996) in many problems. Our bound naturally motivates an
experimental design criterion that is convex and thus computationally efficient
to solve. Based on our novel estimator and design criterion, we derive sparse
linear bandit algorithms that enjoy improved regret upper bounds upon the state
of the art (Hao et al., 2020), especially w.r.t. the geometry of the given
action set. Finally, we prove a matching lower bound for sparse linear bandits
in the data-poor regime, which closes the gap between upper and lower bounds in
prior work.
- Abstract（参考訳）: 疎線形帯域では、学習エージェントが順次アクションを選択し、報酬フィードバックを受け取り、報酬関数はアクションの共変量の数座標に線形に依存する。
これは多くの現実世界のシーケンシャルな意思決定問題に適用できる。
本稿では,多くの問題に対するlasso(tibshirani, 1996)と比較して,より厳密な$\ell_1$リカバリ保証を享受するpopartと呼ばれる簡易かつ計算効率のよいスパース線形推定法を提案する。
我々の境界は自然に凸であり、計算的に解ける実験的な設計基準を動機付けている。
新たな推定法と設計基準に基づき, 与えられたアクションセットの幾何について, 芸術的状態(Hao et al., 2020)の残酷な上界の改善を享受する, 疎線形バンディットアルゴリズムを導出する。
最後に, 前処理における上下境界のギャップを埋めるデータポーア方式において, 疎線形包帯に対して, 一致した下界を証明した。
関連論文リスト
- Neural Dueling Bandits [58.90189511247936]
ニューラルネットワークを用いて、予め選択した腕の好みフィードバックを用いて報酬関数を推定する。
次に、理論結果を二項フィードバックによる文脈的帯域幅問題に拡張し、それはそれ自体は自明な寄与ではない。
論文 参考訳（メタデータ） (2024-07-24T09:23:22Z) - Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits [25.88978373435619]
低ランク行列のトレースレグレッションとその関連問題について検討する。
本稿では,LowPopArtと呼ばれる新しい低ランク行列推定手法を提案する。
提案手法は, 古典的核規範の最小二乗法よりも厳密な回復保証を提供できることを示す。
論文 参考訳（メタデータ） (2024-02-17T00:51:29Z) - Exploration in Linear Bandits with Rich Action Sets and its Implications
for Inference [23.364534479492715]
期待行列の最小固有値は、アルゴリズムの累積後悔が$sqrtn)$であるときに、$Omega(sqrtn)として増加することを示す。
本研究は, 線形帯域におけるEmphmodel selectionとEmphclusteringの2つの実践シナリオに適用する。
論文 参考訳（メタデータ） (2022-07-23T20:25:07Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Online and Distribution-Free Robustness: Regression and Contextual
Bandits with Huber Contamination [29.85468294601847]
線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。
従来の手法が失敗した場合にアルゴリズムが成功することを示す。
論文 参考訳（メタデータ） (2020-10-08T17:59:05Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳（メタデータ） (2020-09-04T04:10:39Z) - Structure Adaptive Algorithms for Stochastic Bandits [22.871155520200773]
構造化多武装バンディット問題のクラスにおける報酬最大化について検討する。
平均的な武器の報酬は、与えられた構造的制約を満たす。
我々は、反復的なサドルポイントソルバを用いて、インスタンス依存の低バウンドからのアルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-07-02T08:59:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。