論文の概要: Adaptive Oracle-Efficient Online Learning

• arxiv url: http://arxiv.org/abs/2210.09385v1
• Date: Mon, 17 Oct 2022 19:32:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-19 13:36:16.929688
• Title: Adaptive Oracle-Efficient Online Learning
• Title（参考訳）: 適応型オラクル効率のオンライン学習
• Authors: Guanghui Wang, Zihao Hu, Vidya Muthukumar, Jacob Abernethy
• Abstract要約: オラクル効率のアルゴリズムは指数関数的に大きい決定空間を探索し、どのデータセットでも最善を尽くしたかを選択する。 我々は、オラクル効率が良く、小さな環境に順応する、後続のリーダーアルゴリズムを設計するための新しいフレームワークを提供する。 我々は、オンラインオークションや、近似可能性を保持するトランスダクティブオンライン分類を含む、現実世界の一連の設定を識別する。
• 参考スコア（独自算出の注目度）: 23.185655992407742
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The classical algorithms for online learning and decision-making have the benefit of achieving the optimal performance guarantees, but suffer from computational complexity limitations when implemented at scale. More recent sophisticated techniques, which we refer to as oracle-efficient methods, address this problem by dispatching to an offline optimization oracle that can search through an exponentially-large (or even infinite) space of decisions and select that which performed the best on any dataset. But despite the benefits of computational feasibility, oracle-efficient algorithms exhibit one major limitation: while performing well in worst-case settings, they do not adapt well to friendly environments. In this paper we consider two such friendly scenarios, (a) "small-loss" problems and (b) IID data. We provide a new framework for designing follow-the-perturbed-leader algorithms that are oracle-efficient and adapt well to the small-loss environment, under a particular condition which we call approximability (which is spiritually related to sufficient conditions provided by Dud\'{i}k et al., [2020]). We identify a series of real-world settings, including online auctions and transductive online classification, for which approximability holds. We also extend the algorithm to an IID data setting and establish a "best-of-both-worlds" bound in the oracle-efficient setting.
• Abstract（参考訳）: オンライン学習と意思決定のための古典的なアルゴリズムは、最適な性能保証を達成する利点があるが、大規模に実装すると計算の複雑さが制限される。 より最近の高度な手法は、オラクル効率のよい手法と呼ばれ、オフラインの最適化オラクルにディスパッチすることでこの問題に対処し、指数関数的に大きい(あるいは無限の)決定空間を探索し、どのデータセット上で最高の結果を得たかを選択できる。 しかし、計算可能性の利点にもかかわらず、オラクルの効率的なアルゴリズムは1つの大きな制限を示している。 本稿では,この2つの友好的シナリオについて考察する。 (a)「小さな損失」問題、及び (b)IDデータ。 本研究は, 近似性(Dud\'{i}k et al., [2020] によって提供される十分条件に精神的に関係している)と呼ばれる, 小空間環境に順応し, オラクル効率のよい探索型リーダアルゴリズムを設計するための新しい枠組みを提供する。 我々は、オンラインオークションや、近似可能性を保持するトランスダクティブオンライン分類を含む、現実世界の一連の設定を識別する。 また,このアルゴリズムを iid データセットに拡張し,oracle 効率のよい設定にバインドした "両世界のベスト" を確立する。

関連論文リスト

• Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions [10.225358400539719]
  本稿では,線形作用が特徴写像に一般化される決定法(MDP)の効率的な強化アルゴリズムを提案する。 具体的には、この設定において、最適に近いポリシーを効率的に見つける新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-07T14:38:05Z)
• Adaptive Resource Allocation for Virtualized Base Stations in O-RAN with Online Learning [60.17407932691429]
  基地局(vBS)を備えたオープンラジオアクセスネットワークシステムは、柔軟性の向上、コスト削減、ベンダーの多様性、相互運用性のメリットを提供する。 本研究では,予期せぬ「混み合う」環境下であっても,効率的なスループットとvBSエネルギー消費のバランスをとるオンライン学習アルゴリズムを提案する。 提案手法は, 課題のある環境においても, 平均最適性ギャップをゼロにすることで, サブ線形後悔を実現する。
  論文  参考訳（メタデータ） (2023-09-04T17:30:21Z)
• Non-Convex Bilevel Optimization with Time-Varying Objective Functions [57.299128109226025]
  本稿では,時間変化の可能なオンライン二段階最適化を提案し,エージェントがオンラインデータを用いて決定を継続的に更新する。 既存のアルゴリズムと比較して、SOBOWは計算効率が良く、以前の関数を知る必要がない。 軽度条件下では,SOBOWはサブリニアな局所的後悔を達成できることを示す。
  論文  参考訳（メタデータ） (2023-08-07T06:27:57Z)
• Riemannian Projection-free Online Learning [5.918057694291832]
  プロジェクション操作は、オンライン勾配降下(OGD)のような最適化アルゴリズムにおける重要な要素である。 これは高次元の設定における計算上の制限や、不条件の制約セットを扱う際に悩まされる。 本稿では,曲面空間上でのオンライン測地線凸最適化において,線形後悔の保証を得る手法を提案する。
  論文  参考訳（メタデータ） (2023-05-30T18:22:09Z)
• Adaptive Decision-Making with Constraints and Dependent Losses: Performance Guarantees and Applications to Online and Nonlinear Identification [5.787117733071415]
  エージェントが有限の選択肢の中から繰り返し選択することで累積性能目標を最適化する適応的意思決定問題を考える。 我々のアルゴリズムと分析はインスタンス依存であり、つまり、環境の最適以下の選択は、我々の後悔の限界に利用され、反映される。 得られたアルゴリズムの性能は2つの数値例で強調される。
  論文  参考訳（メタデータ） (2023-04-06T18:32:26Z)
• Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making [73.48977854003697]
  この研究は、複雑性という新しい概念、一般化ブラケット数を導入し、空間の大きさに対する敵の制約を結婚させる。 次に、オンライン予測や断片的連続関数の計画など、関心のあるいくつかの問題で境界をインスタンス化する。
  論文  参考訳（メタデータ） (2023-02-10T18:45:52Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。 アルゴリズムは最悪の場合でも差分プライバシーを満たす。 現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
  論文  参考訳（メタデータ） (2020-07-10T15:46:05Z)

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

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