Fugu-MT 論文翻訳(概要): Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits

論文の概要: Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits

arxiv url: http://arxiv.org/abs/2402.11156v1
Date: Sat, 17 Feb 2024 00:51:29 GMT
ステータス: 処理完了
システム内更新日: 2024-02-20 23:00:38.548167
Title: Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits
Title（参考訳）: 効率的な低ランク行列推定、実験設計およびアームセット依存低ランクバンディット
Authors: Kyoungseok Jang, Chicheng Zhang, Kwang-Sung Jun
Abstract要約: 低ランク行列のトレースレグレッションとその関連問題について検討する。本稿では,LowPopArtと呼ばれる新しい低ランク行列推定手法を提案する。提案手法は, 古典的核規範の最小二乗法よりも厳密な回復保証を提供できることを示す。
参考スコア（独自算出の注目度）: 29.097522376094624
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study low-rank matrix trace regression and the related problem of low-rank matrix bandits. Assuming access to the distribution of the covariates, we propose a novel low-rank matrix estimation method called LowPopArt and provide its recovery guarantee that depends on a novel quantity denoted by B(Q) that characterizes the hardness of the problem, where Q is the covariance matrix of the measurement distribution. We show that our method can provide tighter recovery guarantees than classical nuclear norm penalized least squares (Koltchinskii et al., 2011) in several problems. To perform efficient estimation with a limited number of measurements from an arbitrarily given measurement set A, we also propose a novel experimental design criterion that minimizes B(Q) with computational efficiency. We leverage our novel estimator and design of experiments to derive two low-rank linear bandit algorithms for general arm sets that enjoy improved regret upper bounds. This improves over previous works on low-rank bandits, which make somewhat restrictive assumptions that the arm set is the unit ball or that an efficient exploration distribution is given. To our knowledge, our experimental design criterion is the first one tailored to low-rank matrix estimation beyond the naive reduction to linear regression, which can be of independent interest.
Abstract（参考訳）: 低ランク行列のトレースレグレッションとその関連問題について検討する。共変量の分布へのアクセスを仮定し, 低ポパルトと呼ばれる新しい低ランク行列推定法を提案し, q が測定分布の共分散行列である問題の硬さを特徴付ける b(q) で表される新しい量に依存する回復保証を提供する。提案手法は,いくつかの問題において,古典的核規範による最小二乗法 (Koltchinskii et al., 2011) よりも厳密な回復保証を提供できることを示す。任意に与えられた測定セットAから限られた数の測定値で効率的な推定を行うために,B(Q)を計算効率で最小化する新しい設計基準を提案する。我々は,新しい推定器と実験の設計を活用し,後悔の上限を改良した一般アームセットのための2つの低ランク線形バンディットアルゴリズムを導出する。これは、アームセットが単位球である、あるいは効率的な探索分布が与えられるというやや制限的な仮定を下級バンディットに関する以前の研究よりも改善する。私たちの知る限りでは、実験的な設計基準は、線形回帰へのナイーブな還元を超えた低ランク行列推定に適応した最初のものである。

関連論文リスト

Best Arm Identification with Minimal Regret [55.831935724659175]
最高の腕識別問題優雅にアマルガメートは、最小化とBAIを後悔している。エージェントの目標は、所定の信頼度で最高の腕を特定することである。二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
論文参考訳（メタデータ） (2024-09-27T16:46:02Z)
Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
論文参考訳（メタデータ） (2023-10-10T17:06:41Z)
PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits [29.097522376094624]
そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
論文参考訳（メタデータ） (2022-10-25T19:13:20Z)
Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery [37.05862765171643]
我々は、ランクに関する事前の知識を持たない低ランク行列のロバストな分解を考える。本稿では,行列のサイズを小さくする設計により,過度に最適化されたモデルにおける過度な適合を効果的に防止できることを示す。
論文参考訳（メタデータ） (2021-09-23T05:54:46Z)
Near-optimal inference in adaptive linear regression [60.08422051718195]
最小二乗法のような単純な方法でさえ、データが適応的に収集されるときの非正規な振る舞いを示すことができる。我々は,これらの分布異常を少なくとも2乗推定で補正するオンラインデバイアス推定器のファミリーを提案する。我々は,マルチアームバンディット,自己回帰時系列推定,探索による能動的学習などの応用を通して,我々の理論の有用性を実証する。
論文参考訳（メタデータ） (2021-07-05T21:05:11Z)
Implicit Regularization of Sub-Gradient Method in Robust Matrix Recovery: Don't be Afraid of Outliers [6.320141734801679]
簡単な部分勾配法が真の低ランク解に効率的に収束することを示す。また,本手法のロバスト性を証明するために,シグナ-RIPと呼ばれる制限等尺性の概念を新たに構築する。
論文参考訳（メタデータ） (2021-02-05T02:52:00Z)
Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number [34.0533596121548]
データ科学における多くの問題は、高度に不完全で、時には腐敗した観測から低いランクを推定するものとして扱われる。 1つの一般的なアプローチは行列分解に頼り、低ランク行列因子は滑らかな損失に対して一階法によって最適化される。
論文参考訳（メタデータ） (2020-10-26T06:21:14Z)
Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。従来の手法が失敗した場合にアルゴリズムが成功することを示す。
論文参考訳（メタデータ） (2020-10-08T17:59:05Z)
On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文参考訳（メタデータ） (2020-08-20T03:48:14Z)
A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
そこで我々は,適応的かつ音質の高い"核フロベニウスノルム"と呼ばれる新しい非スケーラブルな低ランク正規化器を提案する。特異値の計算をバイパスし、アルゴリズムによる高速な最適化を可能にする。既存の行列学習手法では最速でありながら、最先端の回復性能が得られる。
論文参考訳（メタデータ） (2020-08-14T18:47:58Z)
Learning Minimax Estimators via Online Learning [55.92459567732491]
確率分布のパラメータを推定するミニマックス推定器を設計する際の問題点を考察する。混合ケースナッシュ平衡を求めるアルゴリズムを構築した。
論文参考訳（メタデータ） (2020-06-19T22:49:42Z)

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

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