論文の概要: Linear Bandit Algorithms with Sublinear Time Complexity

• arxiv url: http://arxiv.org/abs/2103.02729v1
• Date: Wed, 3 Mar 2021 22:42:15 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-07 13:56:55.872743
• Title: Linear Bandit Algorithms with Sublinear Time Complexity
• Title（参考訳）: 線形時間複雑度をもつ線形帯域アルゴリズム
• Authors: Shuo Yang, Tongzheng Ren, Sanjay Shakkottai, Eric Price, Inderjit S. Dhillon, Sujay Sanghavi
• Abstract要約: 既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。 提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
• 参考スコア（独自算出の注目度）: 67.21046514005029
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose to accelerate existing linear bandit algorithms to achieve per-step time complexity sublinear in the number of arms $K$. The key to sublinear complexity is the realization that the arm selection in many linear bandit algorithms reduces to the maximum inner product search (MIPS) problem. Correspondingly, we propose an algorithm that approximately solves the MIPS problem for a sequence of adaptive queries yielding near-linear preprocessing time complexity and sublinear query time complexity. Using the proposed MIPS solver as a sub-routine, we present two bandit algorithms (one based on UCB, and the other based on TS) that achieve sublinear time complexity. We explicitly characterize the tradeoff between the per-step time complexity and regret, and show that our proposed algorithms can achieve $O(K^{1-\alpha(T)})$ per-step complexity for some $\alpha(T) > 0$ and $\widetilde O(\sqrt{T})$ regret, where $T$ is the time horizon. Further, we present the theoretical limit of the tradeoff, which provides a lower bound for the per-step time complexity. We also discuss other choices of approximate MIPS algorithms and other applications to linear bandit problems.
• Abstract（参考訳）: 既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。 サブリニア複雑さの鍵は、多くの線形バンディットアルゴリズムのアーム選択が最大内積探索(MIPS)問題に減少することである。 これに対応するアルゴリズムとして, 線形前処理時間とサブ線形クエリ時間を組み合わせた適応クエリ列のMIPS問題を大まかに解くアルゴリズムを提案する。 提案したMIPSソルバをサブルーチンとして、サブ線形時間複雑性を実現する2つのバンドレートアルゴリズム(UTBとTSをベースとする)を提案する。 我々は、ステップ毎の時間複雑性と後悔のトレードオフを明示的に特徴付け、提案したアルゴリズムが、ある$\alpha(T) > 0$および$\widetilde O(\sqrt{T})$ regretに対して$O(K^{1-\alpha(T)})$ステップ毎の複雑性を達成可能であることを示す。 さらに,ステップ毎の時間複雑性に対する下限を提供するトレードオフの理論的限界を提案する。 また、近似MIPSアルゴリズムの他の選択や線形帯域問題への応用についても論じる。

関連論文リスト

• EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
  EKM: 最悪の$Oleft(NK+1right)$複雑性でこの問題を正確に解くための新しいアルゴリズムを提案する。 EKMは、フォーマルなプログラムステップを用いて、変換プログラミングと生成の最近の進歩に従って開発されている。 我々は,アルゴリズムのウォールタイム実行時間が,合成データセット上での最悪の時間複雑性解析と一致することを示した。
  論文  参考訳（メタデータ） (2024-05-16T15:11:37Z)
• Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
  我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。 Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
  論文  参考訳（メタデータ） (2024-02-21T15:06:51Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint [16.02833173359407]
  この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。 $mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
  論文  参考訳（メタデータ） (2023-05-17T15:27:33Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time [16.26380955876814]
  マトロイド制約を受ける非単調で非負な部分モジュラ函数を最大化する問題について検討する。 この決定論的比は、$mathcalO(nr)$時間複雑さの下で$frac14$に改善できることを示す。 次に、TwinGreedyFastというより実用的なアルゴリズムを提案し、ほぼ直線的な実行時間で$frac14-epsilon$決定率を達成する。
  論文  参考訳（メタデータ） (2020-10-22T03:52:08Z)
• Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time [16.346069386394703]
  単調な部分モジュラー(submodular)の問題を、濃度制約に従えば$n$の基底集合上で考える。 線形時間複雑性を持つ最初の決定論的アルゴリズムを導入し,これらのアルゴリズムはストリーミングアルゴリズムである。 我々のシングルパスアルゴリズムは任意の$c ge 1$に対して$lceil n / c rceil + c$ oracle クエリの定数比を得る。
  論文  参考訳（メタデータ） (2020-09-10T16:35:54Z)

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

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