論文の概要: Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
- arxiv url: http://arxiv.org/abs/2502.05720v1
- Date: Sat, 08 Feb 2025 23:25:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-11 14:30:13.212391
- Title: Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
- Title(参考訳): 学習用ワンマックス探索におけるパレート最適性, 平滑性, 確率性
- Authors: Ziyad Benomar, Lorenzo Croissant, Vianney Perchet, Spyros Angelopoulos,
- Abstract要約: ワンマックス検索はオンライン意思決定における古典的な問題である。
学習強化環境における1マックス探索の解析に得られる滑らかさの活用法を示す。
- 参考スコア(独自算出の注目度): 20.536739487240318
- License:
- Abstract: One-max search is a classic problem in online decision-making, in which a trader acts on a sequence of revealed prices and accepts one of them irrevocably to maximise its profit. The problem has been studied both in probabilistic and in worst-case settings, notably through competitive analysis, and more recently in learning-augmented settings in which the trader has access to a prediction on the sequence. However, existing approaches either lack smoothness, or do not achieve optimal worst-case guarantees: they do not attain the best possible trade-off between the consistency and the robustness of the algorithm. We close this gap by presenting the first algorithm that simultaneously achieves both of these important objectives. Furthermore, we show how to leverage the obtained smoothness to provide an analysis of one-max search in stochastic learning-augmented settings which capture randomness in both the observed prices and the prediction.
- Abstract(参考訳): ワンマックス検索はオンライン意思決定において古典的な問題であり、トレーダーが明らかにされた価格の連続に作用し、利益を最大化するためにその中の1つを受け入れる。
この問題は、特に競合分析を通じて、確率的および最悪の場合の両方で研究され、最近では、トレーダーがシーケンス上の予測にアクセスできる学習強化された設定で研究されている。
しかし、既存のアプローチではスムーズさが欠如しているか、あるいは最適な最悪の保証が得られていない。
両重要な目的を同時に達成する最初のアルゴリズムを提示することで、このギャップを埋める。
さらに,得られた滑らかさを活用して,確率的学習強化環境での1-max探索の分析を行い,観測値と予測値の両方のランダム性を捉える方法を示す。
関連論文リスト
- Effectively Leveraging Momentum Terms in Stochastic Line Search Frameworks for Fast Optimization of Finite-Sum Problems [0.5156484100374059]
過度にパラメータ化された状態における深度最適化のための最近の線探索手法と運動量方向との関係について検討する。
モーメントパラメータの定義にデータ持続性、共役型ルールの混合を利用するアルゴリズムを導入する。
結果のアルゴリズムは、他の一般的な手法よりも優れていることを実証的に示している。
論文 参考訳(メタデータ) (2024-11-11T16:26:33Z) - Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。
我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
論文 参考訳(メタデータ) (2024-08-07T23:15:21Z) - Beyond Expectations: Learning with Stochastic Dominance Made Practical [88.06211893690964]
支配は、不確実な結果で意思決定を行うためのリスク-逆の選好をモデル化する。
理論上は魅力的だが、機械学習における優位性の応用は乏しい。
まず支配の概念を一般化し、任意の確率変数の任意のペア間の比較を可能にする。
次に、優位性の観点から最適解を見つけるための単純で効率的なアプローチを開発する。
論文 参考訳(メタデータ) (2024-02-05T03:21:23Z) - Bi-objective Ranking and Selection Using Stochastic Kriging [0.0]
両目的のランク付けと選択の問題について検討し,その2つの目的が不確実性をもって観測された。
そこで本研究では,競合する解に対して逐次サンプルを割り当てるバイーシアン双対象ランクと選別法を提案する。
実験結果から,提案手法は標準的なアロケーション手法よりも優れており,また,よく知られた最先端のアルゴリズムも優れていることがわかった。
論文 参考訳(メタデータ) (2022-09-05T23:51:07Z) - Online Search With Best-Price and Query-Based Predictions [2.3204178451683264]
本稿では,入力に関する誤予測が存在する可能性のある学習増強アルゴリズムについて検討する。
株式市場から得られたデータに関する実験結果を提供する。
論文 参考訳(メタデータ) (2021-12-02T20:18:37Z) - Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。
私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
論文 参考訳(メタデータ) (2021-08-19T17:59:28Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。
目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。
機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
論文 参考訳(メタデータ) (2020-10-22T04:51:01Z) - Provable tradeoffs in adversarially robust classification [96.48180210364893]
我々は、ロバストなイソペリメトリに関する確率論の最近のブレークスルーを含む、新しいツールを開発し、活用する。
この結果から,データの不均衡時に増加する標準精度とロバスト精度の基本的なトレードオフが明らかになった。
論文 参考訳(メタデータ) (2020-06-09T09:58:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。