論文の概要: Robust Non-Clairvoyant Scheduling with Classification Models
- arxiv url: http://arxiv.org/abs/2610.01343v1
- Date: Thu, 01 Oct 2026 09:16:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-03 01:19:24.024323
- Title: Robust Non-Clairvoyant Scheduling with Classification Models
- Title（参考訳）: 分類モデルを用いたロバストな非サーベイラントスケジューリング
- Abstract要約: 非クレアボイアント環境におけるジョブの完了時間の総和を最小化する古典的な単一マシンスケジューリング問題について検討する。
頑健な最適化と学習強化アルゴリズムに着想を得て,この制限を克服するための新しい枠組みを導入する。
- 参考スコア（独自算出の注目度）: 0.3441021278275805
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the classical single-machine scheduling problem of minimizing the sum of completion times of jobs in a non-clairvoyant setting, where the processing time of each job remains unknown until its completion. This is a hard problem for which no constant competitive algorithm is possible. Inspired by robust optimization and learning-augmented algorithms, we introduce a novel robustness framework that leverages structural information provided by a classification model to overcome this limitation. Specifically, we assume that jobs are partitioned into classes and we have access to the confusion matrix of the classifier, whose entry $(k,\ell)$ indicates the number of jobs predicted to belong to class~$k$ but that actually belong to class~$\ell$. In this manner, we are able to characterize uncertainty as a set of permutations within each predicted class, rather than as a collection of discrete numerical scenarios, avoiding the computational difficulty of classical robust metrics, such as Min-Max and Min-Max Regret. In addition to these worst-case metrics, we also consider the expected objective over all scenarios. We first propose an optimal non-adaptive strategy that is oblivious with respect to all three robust criteria. We then investigate adaptive and randomized algorithms, showing that they can outperform the optimal non-adaptive strategy when the matrix exhibits particular structural properties.
- Abstract（参考訳）: 従来の単一機械スケジューリング問題において,ジョブの完了までの処理時間が不明な非階層環境において,ジョブの完了時間の総和を最小化する手法について検討した。
これは、一定の競合アルゴリズムが不可能な難しい問題である。
頑健な最適化と学習強化アルゴリズムに着想を得て、分類モデルによって提供される構造情報を活用して、この制限を克服する新しいロバストネスフレームワークを導入する。
具体的には、ジョブがクラスに分割されていると仮定し、そのエントリ$(k,\ell)$はクラス~$k$に属すると予測されるジョブの数を示すが、実際にはクラス~$\ell$に属する。
このようにして、予測クラス内の置換の集合として不確実性を特徴付けることができ、離散的な数値シナリオの集合としてではなく、Min-MaxやMin-Max Regretのような古典的なロバストなメトリクスの計算困難を避けることができる。
これらの最悪のメトリクスに加えて、すべてのシナリオに対して期待される目標も考慮しています。
まず,3つのロバストな基準をすべて考慮し,最適な非適応戦略を提案する。
次に、適応的およびランダムなアルゴリズムを調査し、行列が特定の構造特性を示すとき、最適な非適応的戦略より優れていることを示す。
関連論文リスト
- Active Learning via Regression Beyond Realizability [7.544720605294129]
そこで本研究では,実際のリスクを前提として,サロゲート学習サロゲートに基づく分類のための新たなアクティブラーニングフレームワークを提案する。
我々の新しいアクティブラーニングフレームワークは、既存のアクティブラーニングアルゴリズムよりも複雑であることを示す。
論文 参考訳（メタデータ） (2025-05-31T00:04:07Z) - Minimalistic Predictions to Schedule Jobs with Online Precedence
Constraints [117.8317521974783]
オンライン優先制約による非サーボ的スケジューリングについて検討する。
アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
論文 参考訳（メタデータ） (2023-01-30T13:17:15Z) - Algorithmic Foundations of Empirical X-risk Minimization [51.58884973792057]
この原稿は、機械学習とAIの新しい最適化フレームワーク、bf empirical X-risk baseline (EXM)を紹介している。
Xリスク(X-risk)は、構成測度または目的の族を表すために導入された用語である。
論文 参考訳（メタデータ） (2022-06-01T12:22:56Z) - Efficient and Differentiable Conformal Prediction with General Function
Classes [96.74055810115456]
本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。
本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。
実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
論文 参考訳（メタデータ） (2022-02-22T18:37:23Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。
我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。
これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文 参考訳（メタデータ） (2022-02-21T13:18:11Z) - A new perspective on classification: optimally allocating limited
resources to uncertain tasks [4.169130102668252]
例えば、クレジットカード詐欺検出では、銀行は詐欺捜査チームに少数の取引しか割り当てることができない。
我々は、タスクの不確実性に対処するために分類を使うことは、利用可能な能力を考慮していないため、本質的には最適ではないと論じる。
本稿では,限られた能力しか持たない課題の期待利益を直接最適化することで,ランク付けのための学習を用いた新しいソリューションを提案する。
論文 参考訳（メタデータ） (2022-02-09T10:14:45Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Scalable Optimal Classifiers for Adversarial Settings under Uncertainty [10.90668635921398]
本稿では,攻撃者に対して目的が不明な攻撃者がクラス-1データを生成する対角的設定において,最適な分類器を見つけることの問題点を考察する。
この低次元キャラクタリゼーションにより,ほぼほぼ最適な分類器をスケーラブルに計算する訓練手法が開発可能であることを示す。
論文 参考訳（メタデータ） (2021-06-28T13:33:53Z) - Towards Costless Model Selection in Contextual Bandits: A Bias-Variance
Perspective [7.318831153179727]
文脈的包帯設定における累積的後悔最小化のための同様の保証の実現可能性について検討した。
提案アルゴリズムは, 新たな不特定性テストに基づいており, モデル選択による報酬推定の利点を実証する。
論文 参考訳（メタデータ） (2021-06-11T16:08:03Z) - Early Classification of Time Series. Cost-based Optimization Criterion
and Algorithms [0.0]
本稿では,誤分類のコストと決定を遅らせるコストの両方を考慮して,新たな最適化基準を提案する。
我々は、待ち時間とバランスを取りながら、将来期待される情報獲得を予想する非ミオピックアルゴリズムのファミリーを考案した。
論文 参考訳（メタデータ） (2020-05-20T10:08:30Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。