論文の概要: Semi-Bandit Learning for Monotone Stochastic Optimization

• arxiv url: http://arxiv.org/abs/2312.15427v1
• Date: Sun, 24 Dec 2023 07:46:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-27 18:02:33.163580
• Title: Semi-Bandit Learning for Monotone Stochastic Optimization
• Title（参考訳）: 単調確率最適化のための半バンド学習
• Authors: Arpit Agarwal and Rohan Ghuge and Viswanath Nagarajan
• Abstract要約: モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。 我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
• 参考スコア（独自算出の注目度）: 20.776114616154242
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic optimization is a widely used approach for optimization under uncertainty, where uncertain input parameters are modeled by random variables. Exact or approximation algorithms have been obtained for several fundamental problems in this area. However, a significant limitation of this approach is that it requires full knowledge of the underlying probability distributions. Can we still get good (approximation) algorithms if these distributions are unknown, and the algorithm needs to learn them through repeated interactions? In this paper, we resolve this question for a large class of "monotone" stochastic problems, by providing a generic online learning algorithm with $\sqrt{T \log T}$ regret relative to the best approximation algorithm (under known distributions). Importantly, our online algorithm works in a semi-bandit setting, where in each period, the algorithm only observes samples from the r.v.s that were actually probed. Our framework applies to several fundamental problems in stochastic optimization such as prophet inequality, Pandora's box, stochastic knapsack, stochastic matchings and stochastic submodular optimization.
• Abstract（参考訳）: 確率最適化は不確実性の下での最適化において広く用いられる手法であり、不確実な入力パラメータは確率変数によってモデル化される。 この領域のいくつかの基本的な問題に対して、エクササイズあるいは近似アルゴリズムが得られた。 しかし、このアプローチの重大な制限は、基礎となる確率分布の完全な知識を必要とすることである。 これらの分布が未知であれば、それでも良い(近似)アルゴリズムが得られ、アルゴリズムは繰り返しの相互作用を通じてそれらを学ぶ必要があるだろうか? 本稿では,この問題に対して,最も優れた近似アルゴリズム(既知の分布の下で)に対して,$\sqrt{T \log T}$後悔のオンライン学習アルゴリズムを提供することにより,大規模な「モノトーン」確率問題に対して解決する。 重要なことに、我々のオンラインアルゴリズムは半帯域設定で動作し、それぞれの期間に実際に調査されたr.v.sのサンプルのみを観測する。 本フレームワークは,確率的不等式,Pandoraのボックス,確率的knapsack,確率的マッチング,確率的部分モジュラー最適化などの確率的最適化の基本的な問題に適用する。

関連論文リスト

• Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing [7.143879014059895]
  ビルベル問題の解法としてゼロ階近似アルゴリズムを研究・解析する。 我々の知る限りでは、完全ゼロ階二階最適化アルゴリズムのためにサンプル境界が確立されたのはこれが初めてである。
  論文  参考訳（メタデータ） (2024-03-29T21:12:25Z)
• Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance [17.199063087458907]
  我々は一様凸ミラーマップのクラスを用いてミラーDescentアルゴリズムの収束率を定量化する。 このアルゴリズムは明確な勾配クリッピングや正規化を必要としない。 我々は,1次オラクルのみを用いた他のアルゴリズムでは改善率を達成できないことを示す情報理論の下界を補完する。
  論文  参考訳（メタデータ） (2022-02-23T17:08:40Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)

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

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