論文の概要: Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems

• arxiv url: http://arxiv.org/abs/2406.18752v2
• Date: Wed, 09 Jul 2025 14:20:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-10 17:37:43.211414
• Title: Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems
• Title（参考訳）: 学習強化オンラインクナップサック問題に対する準最適一貫性-ロバスト性トレードオフ
• Authors: Mohammadreza Daneshvaramoli, Helia Karisani, Adam Lechowicz, Bo Sun, Cameron Musco, Mohammad Hajiesmaili,
• Abstract要約: 本稿では,オンラインknapsack問題に対する学習強化アルゴリズムのファミリーを紹介する。 本稿では,オンラインアルゴリズム設計における新たな洞察を提供する新しい分数変換手法を提案する。
• 参考スコア（独自算出の注目度）: 16.793099279933163
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper introduces a family of learning-augmented algorithms for online knapsack problems that achieve near Pareto-optimal consistency-robustness trade-offs through a simple combination of trusted learning-augmented and worst-case algorithms. Our approach relies on succinct, practical predictions -- single values or intervals estimating the minimum value of any item in an offline solution. Additionally, we propose a novel fractional-to-integral conversion procedure, offering new insights for online algorithm design.
• Abstract（参考訳）: 本稿では,オンラインクナップサック問題に対する学習強化アルゴリズムの一群について紹介する。 我々のアプローチは簡潔で実践的な予測に依存します -- オフラインソリューションにおけるアイテムの最小値を見積もる単一値やインターバルです。 さらに,オンラインアルゴリズム設計における新たな洞察を提供する新しい分数変換手法を提案する。

関連論文リスト

• Learning-Augmented Online Bipartite Fractional Matching [7.721815606607016]
  各反復において提案されたマッチングの形式でアルゴリズムにアドバイスが与えられたとき、オンライン二部分数マッチングについて検討する。 我々のアルゴリズムは、アドバイスフォローとアドバイスフリーのアルゴリズムをランダムに選択する単純な「コインフリップ」戦略を支配している。 任意のアルゴリズムで達成可能な堅牢性と一貫性のトレードオフに縛られる硬さを確立する。
  論文  参考訳（メタデータ） (2025-05-25T18:15:29Z)
• Primal-dual algorithm for contextual stochastic combinatorial optimization [1.4999444543328293]
  本稿では,不確実性のある意思決定に対処するために,運用研究と機械学習を統合する,文脈最適化の新しいアプローチを提案する。 我々の目標は、不確実なパラメータやコンテキストに関する過去のデータから推定される経験的リスクを最小化することです。
  論文  参考訳（メタデータ） (2025-05-07T19:37:12Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Self-Supervised Penalty-Based Learning for Robust Constrained Optimization [4.297070083645049]
  本稿では,自己教師付きペナルティに基づく損失関数を用いた学習に基づいて,パラメータ化制約付きロバスト最適化のための新しい手法を提案する。 我々のアプローチは、従来の解法よりも推論時間がかなり小さいニューラルネットワーク近似を効果的に学習することができる。
  論文  参考訳（メタデータ） (2025-03-07T06:42:17Z)
• Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization [15.102119312523696]
  組合せ最適化(CO)の問題は、医学、物流、製造など幅広い領域で発生する。 本研究では,CO の非学習近似アルゴリズムを学習ベースで拡張する手法を提案する。 本手法は,近似アルゴリズムをブラックボックスとして扱う新しい勾配推定法を用いて,自己教師付き方式でエンドツーエンドに学習する。
  論文  参考訳（メタデータ） (2025-02-26T18:23:07Z)
• Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
  従来のアルゴリズムの近似保証よりも高い精度で予測を行う。 我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。 この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
  論文  参考訳（メタデータ） (2024-11-25T17:31:34Z)
• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。 我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
  論文  参考訳（メタデータ） (2024-08-07T23:15:21Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Algorithms with Prediction Portfolios [23.703372221079306]
  我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。 これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
  論文  参考訳（メタデータ） (2022-10-22T12:58:07Z)
• 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)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  予測器を学習するアルゴリズムに対して,一般的な設計手法を導入する。 オンライン学習の手法を応用して、敵のインスタンスに対して学習し、堅牢性と一貫性のあるトレードオフを調整し、新しい統計的保証を得る。 両部マッチング,ページマイグレーション,スキーレンタル,ジョブスケジューリングの手法を解析することにより,学習アルゴリズムの導出におけるアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-02-18T17:25:43Z)
• Parsimonious Learning-Augmented Caching [29.975391787684966]
  本稿では,学習補助アルゴリズムが同時に予測を利用できるような設定を導入し,研究する。 定量的に類似した結果が得られるが、予測のサブ線形数のみを用いることを示す。
  論文  参考訳（メタデータ） (2022-02-09T03:40:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation [92.3161051419884]
  線形関数近似を用いた強化学習について検討する。 既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たない。 我々はFLUTEと呼ばれる新しいアルゴリズムを提案し、高い確率で最適ポリシーへの均一PAC収束を享受する。
  論文  参考訳（メタデータ） (2021-06-22T08:48:56Z)
• End-to-End Constrained Optimization Learning: A Survey [69.22203885491534]
  機械学習アーキテクチャとソルバと最適化手法を統合する作業の調査に焦点を当てている。 これらのアプローチは、問題に対する迅速、近似、構造的、解決策を予測し、論理的推論を可能にする新しいハイブリッド機械学習と最適化手法を開発することを約束します。
  論文  参考訳（メタデータ） (2021-03-30T14:19:30Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)
• Logistic Q-Learning [87.00813469969167]
  MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。 提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
  論文  参考訳（メタデータ） (2020-10-21T17:14:31Z)

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

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