論文の概要: Follow The Approximate Sparse Leader for No-Regret Online Sparse Linear Approximation

• arxiv url: http://arxiv.org/abs/2501.00799v2
• Date: Tue, 07 Jan 2025 17:32:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-08 12:28:42.630872
• Title: Follow The Approximate Sparse Leader for No-Regret Online Sparse Linear Approximation
• Title（参考訳）: No-Regretオンラインスパース線形近似のための近似スパースリーダーのフォロー
• Authors: Samrat Mukhopadhyay, Debasmita Mukherjee,
• Abstract要約: 我々は, 与えられた測定行列の列の線形結合の観点から, 測定列の最良のスパース近似を予測できるような, テキストトンラインスパース線形近似の問題を考察する。 本稿では、このオンライン問題に対処するための効率的なオンラインメタ政治であるFollow-The-Approximate-Sparse-Leaderを提案する。
• 参考スコア（独自算出の注目度）: 0.46040036610482665
• License:
• Abstract: We consider the problem of \textit{online sparse linear approximation}, where one predicts the best sparse approximation of a sequence of measurements in terms of linear combination of columns of a given measurement matrix. Such online prediction problems are ubiquitous, ranging from medical trials to web caching to resource allocation. The inherent difficulty of offline recovery also makes the online problem challenging. In this letter, we propose Follow-The-Approximate-Sparse-Leader, an efficient online meta-policy to address this online problem. Through a detailed theoretical analysis, we prove that under certain assumptions on the measurement sequence, the proposed policy enjoys a data-dependent sublinear upper bound on the static regret, which can range from logarithmic to square-root. Numerical simulations are performed to corroborate the theoretical findings and demonstrate the efficacy of the proposed online policy.
• Abstract（参考訳）: ここでは、与えられた測定行列の列の線形結合の観点から、測定列の最良のスパース近似を予測する。 このようなオンライン予測問題は、医学的な試行錯誤からWebキャッシュ、リソース割り当てまで、どこにでもある。 オフラインのリカバリが本質的に困難であることは、オンラインの問題を難しくしている。 本稿では、このオンライン問題に対処するための効率的なオンラインメタ政治であるFollow-The-Approximate-Sparse-Leaderを提案する。 詳細な理論的解析により, 提案手法は, 対数から平方根まで, 静的後悔点上のデータ依存サブ線形上界を満足することを示した。 理論的知見を裏付ける数値シミュレーションを行い,提案したオンライン政策の有効性を実証する。

関連論文リスト

• Regret Analysis of Policy Optimization over Submanifolds for Linearly Constrained Online LQG [12.201535821920624]
  制御器に与えられた線形制約を持つオンライン線形二次ガウス問題について検討する。 関数列の第1次および第2次情報に対する予測に基づいてオンラインコントローラを提供するオンライン楽観的ニュートン(OONM)を提案する。
  論文  参考訳（メタデータ） (2024-03-13T14:06:18Z)
• Multivariate Online Linear Regression for Hierarchical Forecasting [1.5361702135159843]
  我々は、よく知られたVovk-Azoury-Warmuthアルゴリズムを多変量設定に拡張するMultiVAWを紹介する。 本稿では,オンライン階層予測問題に適用し,この論文からアルゴリズムを復元する。
  論文  参考訳（メタデータ） (2024-02-22T14:33:54Z)
• Low-rank extended Kalman filtering for online learning of neural networks from streaming data [71.97861600347959]
  非定常データストリームから非線形関数のパラメータを推定するための効率的なオンライン近似ベイズ推定アルゴリズムを提案する。 この方法は拡張カルマンフィルタ (EKF) に基づいているが、新しい低ランク+斜角行列分解法を用いている。 変分推論に基づく手法とは対照的に,本手法は完全に決定論的であり,ステップサイズチューニングを必要としない。
  論文  参考訳（メタデータ） (2023-05-31T03:48:49Z)
• An Online Algorithm for Chance Constrained Resource Allocation [10.791923293928987]
  本稿では,オンライン資源配分問題 (RAP) を確率制約で検討する。 私たちの知る限りでは、オンラインRAP問題に制約が導入されるのはこれが初めてです。
  論文  参考訳（メタデータ） (2023-03-06T16:17:19Z)
• Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression [14.521929085104441]
  オンライン勾配勾配(SGD)の線形関数に対する高次元中央極限定理(CLT)を確立する。 我々は、CLTに現れる予測と分散項を推定するオンライン手法を開発し、開発したオンライン推定器の高確率境界を確立する。 我々は、CLT結果と分散推定結果とともに、信頼区間を数値的に構築する完全オンラインおよびデータ駆動の方法として、2段階の完全オンラインバイアス補正手法を提案する。
  論文  参考訳（メタデータ） (2023-02-20T02:38:36Z)
• Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality [57.91411772725183]
  本稿では,状態空間と動作空間が有限である場合のオフライン最短経路問題について考察する。 オフラインポリシ評価(OPE)とオフラインポリシ学習タスクの両方を扱うための,シンプルな値ベースアルゴリズムを設計する。 これらの単純なアルゴリズムの解析は、極小値に近い最悪のケース境界を示唆する強いインスタンス依存境界をもたらす。
  論文  参考訳（メタデータ） (2022-06-10T07:44:56Z)
• Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes [99.26864533035454]
  半可観測マルコフ決定過程におけるオフライン強化学習(RL)について検討する。 本稿では,UnderlineProxy変数 underlinePessimistic UnderlinePolicy UnderlineOptimization (textttP3O)アルゴリズムを提案する。 textttP3Oは、確立されたデータセットを持つPOMDPのための証明可能な最初のオフラインRLアルゴリズムである。
  論文  参考訳（メタデータ） (2022-05-26T19:13:55Z)
• Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge [24.880035784304834]
  オンラインリッジ回帰とフォワードアルゴリズムに対して高い確率的後悔境界を導出する。 これにより、オンライン回帰アルゴリズムをより正確に比較し、有界な観測と予測の仮定を排除できる。
  論文  参考訳（メタデータ） (2021-11-02T13:57:53Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  最小二乗法のような単純な方法でさえ、データが適応的に収集されるときの非正規な振る舞いを示すことができる。 我々は,これらの分布異常を少なくとも2乗推定で補正するオンラインデバイアス推定器のファミリーを提案する。 我々は,マルチアームバンディット,自己回帰時系列推定,探索による能動的学習などの応用を通して,我々の理論の有用性を実証する。
  論文  参考訳（メタデータ） (2021-07-05T21:05:11Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• GELATO: Geometrically Enriched Latent Model for Offline Reinforcement Learning [54.291331971813364]
  オフライン強化学習アプローチは、近近法と不確実性認識法に分けられる。 本研究では,この2つを潜在変動モデルに組み合わせることのメリットを実証する。 提案したメトリクスは、分布サンプルのアウトの品質と、データ内のサンプルの不一致の両方を測定します。
  論文  参考訳（メタデータ） (2021-02-22T19:42:40Z)

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

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