論文の概要: Buying Information for Stochastic Optimization
- arxiv url: http://arxiv.org/abs/2306.03607v1
- Date: Tue, 6 Jun 2023 11:50:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-07 15:46:35.035708
- Title: Buying Information for Stochastic Optimization
- Title（参考訳）: 確率最適化のための情報購入
- Authors: Mingchen Ma and Christos Tzamos
- Abstract要約: 最適化のための情報の購入方法と,オンライン学習問題としてこの問題を定式化する方法について検討する。
この比は、スキーレンタル問題の堅牢な一般化と同値であり、超マーチンゲール停止(super-martingale stop)と呼ぶことから、厳密であることを示す。
動作を選択し、根底にある要求に関する情報をいつ購入するかを判断する8ドルの競合アルゴリズムを時間内に実行します。
- 参考スコア（独自算出の注目度）: 16.272461309965284
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Stochastic optimization is one of the central problems in Machine Learning
and Theoretical Computer Science. In the standard model, the algorithm is given
a fixed distribution known in advance. In practice though, one may acquire at a
cost extra information to make better decisions. In this paper, we study how to
buy information for stochastic optimization and formulate this question as an
online learning problem. Assuming the learner has an oracle for the original
optimization problem, we design a $2$-competitive deterministic algorithm and a
$e/(e-1)$-competitive randomized algorithm for buying information. We show that
this ratio is tight as the problem is equivalent to a robust generalization of
the ski-rental problem, which we call super-martingale stopping.
We also consider an adaptive setting where the learner can choose to buy
information after taking some actions for the underlying optimization problem.
We focus on the classic optimization problem, Min-Sum Set Cover, where the goal
is to quickly find an action that covers a given request drawn from a known
distribution. We provide an $8$-competitive algorithm running in polynomial
time that chooses actions and decides when to buy information about the
underlying request.
- Abstract（参考訳）: 確率最適化は、機械学習と理論的コンピュータ科学における中心的な問題の1つである。
標準モデルでは、アルゴリズムは事前に知られている固定分布を与えられる。
しかし実際には、より良い意思決定を行うために、コストのかかる余分な情報を取得することができる。
本稿では,確率的最適化のための情報購入方法を検討し,この問題をオンライン学習問題として定式化する。
学習者が元の最適化問題に対してオラクルを持つと仮定すると、情報を購入するための2ドルの競争的決定論的アルゴリズムと$e/(e-1)$-競争的ランダム化アルゴリズムを設計する。
この比は、スキーレンタル問題の堅牢な一般化と同値であり、超マーチンゲール停止(super-martingale stop)と呼ぶことから、厳密であることを示す。
また,基礎となる最適化問題に対して何らかのアクションをとれば,学習者が情報購入を選択できる適応的な設定も検討する。
従来の最適化問題であるmin-sum set coverに注目し、既知のディストリビューションから引き出された要求をすばやくカバーするアクションを見つけることを目標としている。
多項式時間で動作し、アクションを選択し、基盤となるリクエストに関する情報をいつ購入するかを決定する8ドルの競合アルゴリズムを提供する。
関連論文リスト
- Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。
我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
論文 参考訳（メタデータ） (2023-12-24T07:46:37Z) - Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
各ラウンド$t$において、プレイヤーが2次的打撃コストと2次攻撃コストに応じてアクション$x_tをプレイし、アクションを切り替えるための2乗$ell$-normコストを加算する、スムーズなオンライン最適化(SOQO)問題について検討する。
この問題クラスは、スマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインと強いつながりを持っています。
本稿では, 最適に近い性能を同時に達成しつつ, 強健な対角性能を得るベスト・オブ・ザ・ワールドス・アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-31T22:59:23Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order
Information [37.70729542263343]
本稿では,大規模機械学習問題に対する適応最適化アルゴリズムを提案する。
我々の手法は方向とステップサイズを動的に適応させる。
我々の手法は退屈なチューニング率チューニングを必要としない。
論文 参考訳（メタデータ） (2021-09-11T06:39:50Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - First Steps Towards a Runtime Analysis When Starting With a Good
Solution [8.34061303235504]
現実的な応用では、ランダムな解よりも優れた解を推測することができる。
我々は、異なるアルゴリズムがより良い初期解と全く異なる程度に利益を得ることを示す。
このことは、進化的アルゴリズムが良い初期解をうまく活用していることがまだ見つからないことを示唆している。
論文 参考訳（メタデータ） (2020-06-22T11:46:42Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。