論文の概要: Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratio
- arxiv url: http://arxiv.org/abs/2601.06813v1
- Date: Sun, 11 Jan 2026 08:51:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-13 19:08:01.008493
- Title: Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratio
- Title（参考訳）: 分布ロバスト競争率に対する予測精度の影響の解析
- Authors: Toru Yoshinaga, Yasushi Kawase,
- Abstract要約: 我々は,Sunらが導入した分散ロバスト競争率(DRCR)に注目した(ICML 2024)。
既知の構造的特性は、任意の固定アルゴリズムに対して、予測精度が増加するにつれてDRCRは線形的に減少するということである。
我々は,オンライン最適化におけるベンチマーク問題であるスキーレンタル問題に適用し,最適DRCRに必要な予測精度の条件を特定する。
- 参考スコア（独自算出の注目度）: 3.616700653734583
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The field of algorithms with predictions aims to improve algorithm performance by integrating machine learning predictions into algorithm design. A central question in this area is how predictions can improve performance, and a key aspect of this analysis is the role of prediction accuracy. In this context, prediction accuracy is defined as a guaranteed probability that an instance drawn from the distribution belongs to the predicted set. As a performance measure that incorporates prediction accuracy, we focus on the distributionally-robust competitive ratio (DRCR), introduced by Sun et al.~(ICML 2024). The DRCR is defined as the expected ratio between the algorithm's cost and the optimal cost, where the expectation is taken over the worst-case instance distribution that satisfies the given prediction and accuracy requirement. A known structural property is that, for any fixed algorithm, the DRCR decreases linearly as prediction accuracy increases. Building on this result, we establish that the optimal DRCR value (i.e., the infimum over all algorithms) is a monotone and concave function of prediction accuracy. We further generalize the DRCR framework to a multiple-prediction setting and show that monotonicity and concavity are preserved in this setting. Finally, we apply our results to the ski rental problem, a benchmark problem in online optimization, to identify the conditions on prediction accuracies required for the optimal DRCR to attain a target value. Moreover, we provide a method for computing the critical accuracy, defined as the minimum accuracy required for the optimal DRCR to strictly improve upon the performance attainable without any accuracy guarantee.
- Abstract（参考訳）: 予測を伴うアルゴリズムの分野は、機械学習予測をアルゴリズム設計に統合することにより、アルゴリズム性能を向上させることを目的としている。
この領域における中心的な疑問は、予測がパフォーマンスを改善する方法であり、この分析の重要な側面は予測精度の役割である。
この文脈では、予測精度は、分布から引き出されたインスタンスが予測集合に属する保証された確率として定義される。
予測精度を組み込んだ性能指標として,Sunらが導入した分散ロバスト競争率(DRCR)に着目した。
DRCRはアルゴリズムのコストと最適コストの予測比として定義され、予測された予測と精度の要求を満たす最悪のインスタンス分布に期待が乗じられる。
既知の構造的特性は、任意の固定アルゴリズムに対して、予測精度が増加するにつれてDRCRは線形的に減少するということである。
この結果に基づいて、最適DRCR値(すなわち、全てのアルゴリズム上の無限小)が予測精度の単調で凹凸な関数であることを確かめる。
さらに、DRCRフレームワークを多重予測設定に一般化し、この設定で単調性と凹凸が保存されていることを示す。
最後に、オンライン最適化におけるベンチマーク問題であるスキーレンタル問題に適用し、最適DRCRが目標値を達成するのに必要な予測精度の条件を特定する。
さらに、最適DRCRが精度を保証することなく達成可能な性能を厳格に向上するために必要となる最小限の精度として定義される臨界精度を計算する方法を提案する。
関連論文リスト
- A Switching Framework for Online Interval Scheduling with Predictions [4.352962539265558]
我々は、各区間を即時に受け入れるか、到着時に拒否しなければならない、取り消し不能な環境でのオンライン区間スケジューリングについて検討する。
我々は,この問題を,アルゴリズムが(機械学習による)予測にアクセスできる学習拡張環境で考える。
私たちの主な貢献はSemiTrust-and-Switchフレームワークであり、予測ベースと古典的間隔スケジューリングアルゴリズムを組み合わせた統一的なアプローチを提供する。
論文 参考訳（メタデータ） (2025-11-20T10:01:09Z) - Persuasive Calibration [15.651406777700517]
我々は、予測を自身の値で非バイアス条件で行うように規制する標準校正フレームワークを採用する。
最適予測器は、高い(低い)真の期待結果に対して自信過剰であり、中央に完全に留まっていることを示す。
論文 参考訳（メタデータ） (2025-04-04T06:49:56Z) - Calibrated Probabilistic Forecasts for Arbitrary Sequences [58.54729945445505]
実際のデータストリームは、分散シフトやフィードバックループ、敵アクターによって予測不可能に変化する可能性がある。
データがどのように進化するかに関わらず、有効な不確実性推定を保証するための予測フレームワークを提案する。
論文 参考訳（メタデータ） (2024-09-27T21:46:42Z) - Improving Accuracy Without Losing Interpretability: A ML Approach for
Time Series Forecasting [4.025941501724274]
時系列予測では、分解に基づくアルゴリズムが集約データを意味のあるコンポーネントに分解する。
近年のアルゴリズムは、予測精度を向上させるために、機械学習(以下、ML)手法と分解を組み合わせていることが多い。
本稿では,分解とMLを組み合わせたハイブリッドアルゴリズムW-Rを提案する。
論文 参考訳（メタデータ） (2022-12-13T14:51:10Z) - Efficient and Differentiable Conformal Prediction with General Function
Classes [96.74055810115456]
本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。
本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。
実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
論文 参考訳（メタデータ） (2022-02-22T18:37:23Z) - Accurate Prediction and Uncertainty Estimation using Decoupled
Prediction Interval Networks [0.0]
精度を犠牲にすることなく、回帰に基づく予測の不確かさを確実に推定できるネットワークアーキテクチャを提案する。
予測と予測間隔(PI)推定の学習を2段階の学習プロセスに分解することで、これを実現する。
提案手法を,合成データセットおよびUCIベンチマーク上での最先端不確実性定量化アルゴリズムと比較し,予測誤差を23～34%削減した。
論文 参考訳（メタデータ） (2022-02-19T19:31:36Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-10T10:02:31Z) - CovarianceNet: Conditional Generative Model for Correct Covariance
Prediction in Human Motion Prediction [71.31516599226606]
本稿では,将来の軌道の予測分布に関連する不確かさを正確に予測する手法を提案する。
我々のアプローチであるCovariaceNetは、ガウス潜在変数を持つ条件付き生成モデルに基づいている。
論文 参考訳（メタデータ） (2021-09-07T09:38:24Z) - Optimized conformal classification using gradient descent approximation [0.2538209532048866]
コンフォーマル予測器は、ユーザ定義の信頼性レベルで予測を行うことができる。
我々は,共形予測器を直接最大予測効率で訓練する手法を検討する。
実世界の複数のデータセット上で本手法を検証し,本手法が有望であることを示す。
論文 参考訳（メタデータ） (2021-05-24T13:14:41Z) - AutoCP: Automated Pipelines for Accurate Prediction Intervals [84.16181066107984]
本稿では、自動予測のための自動機械学習(Automatic Machine Learning for Conformal Prediction, AutoCP)というAutoMLフレームワークを提案する。
最高の予測モデルを選択しようとする慣れ親しんだAutoMLフレームワークとは異なり、AutoCPは、ユーザが指定したターゲットカバレッジ率を達成する予測間隔を構築する。
さまざまなデータセットでAutoCPをテストしたところ、ベンチマークアルゴリズムを著しく上回っていることがわかった。
論文 参考訳（メタデータ） (2020-06-24T23:13:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。