論文の概要: A Regression Approach to Learning-Augmented Online Algorithms
- arxiv url: http://arxiv.org/abs/2205.08717v1
- Date: Wed, 18 May 2022 04:29:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-19 19:30:14.004642
- Title: A Regression Approach to Learning-Augmented Online Algorithms
- Title（参考訳）: 学習強化オンラインアルゴリズムへの回帰アプローチ
- Authors: Keerti Anand, Rong Ge, Amit Kumar, Debmalya Panigrahi
- Abstract要約: 本論文では,本手法について紹介し,一般的なオンライン検索フレームワークの文脈で考察する。
この回帰問題におけるサンプルの複雑さにほぼ厳密な境界を示し、その結果を不可知的な設定にまで拡張する。
技術的観点から、回帰問題に対する損失関数の設計にオンライン最適化ベンチマークを組み込むことが重要であることを示す。
- 参考スコア（独自算出の注目度）: 17.803569868141647
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The emerging field of learning-augmented online algorithms uses ML techniques
to predict future input parameters and thereby improve the performance of
online algorithms. Since these parameters are, in general, real-valued
functions, a natural approach is to use regression techniques to make these
predictions. We introduce this approach in this paper, and explore it in the
context of a general online search framework that captures classic problems
like (generalized) ski rental, bin packing, minimum makespan scheduling, etc.
We show nearly tight bounds on the sample complexity of this regression
problem, and extend our results to the agnostic setting. From a technical
standpoint, we show that the key is to incorporate online optimization
benchmarks in the design of the loss function for the regression problem,
thereby diverging from the use of off-the-shelf regression tools with standard
bounds on statistical error.
- Abstract（参考訳）: 学習強化オンラインアルゴリズムの新たな分野は、ML技術を用いて将来の入力パラメータを予測し、オンラインアルゴリズムの性能を向上させる。
これらのパラメータは一般に実数値関数であるため、回帰法を用いて予測を行うのが自然な方法である。
本稿では,この手法を導入し,(一般化)スキーレンタル,ビンパッキング,最小限のメースパンスケジューリングなどの古典的問題を捉える,一般的なオンライン検索フレームワークの文脈で検討する。
この回帰問題のサンプル複雑性についてほぼ厳密な境界を示し、その結果を不可知な設定に拡張する。
技術的観点からは、回帰問題に対する損失関数の設計にオンライン最適化ベンチマークを組み込むことが重要であり、したがって統計的誤差に標準的制約がある既製の回帰ツールの使用から逸脱することを示す。
関連論文リスト
- Mutual Information Learned Regressor: an Information-theoretic Viewpoint
of Training Regression Systems [10.314518385506007]
回帰問題を解くための既存の慣習は平均二乗誤差(MSE)最小化アプローチである。
近年,Yiらは相互情報に基づく教師あり学習フレームワークを提案し,ラベルエントロピー正規化を導入した。
本稿では,相互情報に基づく教師あり学習フレームワークにおける回帰について検討する。
論文 参考訳（メタデータ） (2022-11-23T03:43:22Z) - Vector-Valued Least-Squares Regression under Output Regularity
Assumptions [73.99064151691597]
最小二乗回帰問題を無限次元出力で解くために,還元ランク法を提案し,解析する。
提案手法の学習バウンダリを導出し、フルランク手法と比較して統計的性能の設定を改善する研究を行う。
論文 参考訳（メタデータ） (2022-11-16T15:07:00Z) - A Novel Plug-and-Play Approach for Adversarially Robust Generalization [38.72514422694518]
本稿では,MLモデルを摂動テストデータから保護するために,逆向きに堅牢なトレーニングを採用する頑健なフレームワークを提案する。
私たちの貢献は、計算学と統計学の両方の観点から見ることができます。
論文 参考訳（メタデータ） (2022-08-19T17:02:55Z) - Domain-Adjusted Regression or: ERM May Already Learn Features Sufficient
for Out-of-Distribution Generalization [52.7137956951533]
既存の特徴から予測器を学習するためのよりシンプルな手法を考案することは、将来の研究にとって有望な方向である、と我々は主張する。
本稿では,線形予測器を学習するための凸目標である領域調整回帰(DARE)を紹介する。
自然モデルの下では、DARE解が制限されたテスト分布の集合に対する最小最適予測器であることを証明する。
論文 参考訳（メタデータ） (2022-02-14T16:42:16Z) - Stochastic Online Linear Regression: the Forward Algorithm to Replace
Ridge [24.880035784304834]
オンラインリッジ回帰とフォワードアルゴリズムに対して高い確率的後悔境界を導出する。
これにより、オンライン回帰アルゴリズムをより正確に比較し、有界な観測と予測の仮定を排除できる。
論文 参考訳（メタデータ） (2021-11-02T13:57:53Z) - Logistic Q-Learning [87.00813469969167]
MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。
提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
論文 参考訳（メタデータ） (2020-10-21T17:14:31Z) - A spectral algorithm for robust regression with subgaussian rates [0.0]
本研究では, 試料の分布に強い仮定がない場合の線形回帰に対する2次時間に対する新しい線形アルゴリズムについて検討する。
目的は、データが有限モーメントしか持たなくても最適な準ガウス誤差を達成できる手順を設計することである。
論文 参考訳（メタデータ） (2020-07-12T19:33:50Z) - Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
順序付き$L_1$ (OWL)正規化回帰は、高次元スパース学習のための新しい回帰分析である。
近勾配法はOWL回帰を解くための標準手法として用いられる。
未知の順序構造を持つ原始解の順序を探索することにより、OWL回帰の最初の安全なスクリーニングルールを提案する。
論文 参考訳（メタデータ） (2020-06-29T23:35:53Z) - Optimizing for the Future in Non-Stationary MDPs [52.373873622008944]
本稿では,今後の性能予測を最大化するポリシ勾配アルゴリズムを提案する。
我々のアルゴリズムであるPrognosticatorは2つのオンライン適応手法よりも非定常性に頑健であることを示す。
論文 参考訳（メタデータ） (2020-05-17T03:41:19Z) - Beyond UCB: Optimal and Efficient Contextual Bandits with Regression
Oracles [112.89548995091182]
我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。
我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
論文 参考訳（メタデータ） (2020-02-12T11:33:46Z) - Adaptive Approximate Policy Iteration [22.915651391812187]
均一なエルゴディックMDPの学習を継続する学習方法として,$tildeO(T2/3)$ regret bound for undiscounted, continuing learning in uniformly ergodic MDPを提案する。
これは、関数近似を持つ平均逆ケースに対する$tildeO(T3/4)$の最良の既存の境界よりも改善されている。
論文 参考訳（メタデータ） (2020-02-08T02:27:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。