論文の概要: Learning-Augmented Algorithms for $k$-median via Online Learning
- arxiv url: http://arxiv.org/abs/2603.18157v1
- Date: Wed, 18 Mar 2026 18:00:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-20 17:19:05.789613
- Title: Learning-Augmented Algorithms for $k$-median via Online Learning
- Title（参考訳）: オンライン学習による$k$-medianのための学習補助アルゴリズム
- Authors: Anish Hebbar, Rong Ge, Amit Kumar, Debmalya Panigrahi,
- Abstract要約: オンライン学習に触発された学習強化アルゴリズムの新しいモデルを提案する。
我々は問題の一連のインスタンスを与えられ、学習強化アルゴリズムの目標は、問題の将来のインスタンスに対する解決策を提案するために、事前インスタンスを使用することである。
- 参考スコア（独自算出の注目度）: 16.98221371037775
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for learning-augmented algorithms inspired by online learning. In this model, we are given a sequence of instances of a problem and the goal of the learning-augmented algorithm is to use prior instances to propose a solution to a future instance of the problem. The performance of the algorithm is measured by its average performance across all the instances, where the performance on a single instance is the ratio between the cost of the algorithm's solution and that of an optimal solution for that instance. We apply this framework to the classic $k$-median clustering problem, and give an efficient learning algorithm that can approximately match the average performance of the best fixed $k$-median solution in hindsight across all the instances. We also experimentally evaluate our algorithm and show that its empirical performance is close to optimal, and also that it automatically adapts the solution to a dynamically changing sequence.
- Abstract（参考訳）: 学習強化アルゴリズムの分野は、過去の問題のインスタンスでML技術を使用して、将来のインスタンスのために設計されたアルゴリズムを知らせることを目指している。
本稿では,オンライン学習に触発された学習強化アルゴリズムの新しいモデルを提案する。
このモデルでは,問題の事例列が与えられ,学習補助アルゴリズムの目標は,先例を用いて問題の将来の事例に対する解決策を提案することである。
アルゴリズムの性能は、全てのインスタンスの平均的なパフォーマンスで測定され、1つのインスタンスのパフォーマンスは、アルゴリズムのソリューションのコストと、そのインスタンスの最適解の比率である。
このフレームワークを古典的な$k$-medianクラスタリング問題に適用し、すべてのインスタンスに対する最高の$k$-medianソリューションの平均性能とほぼ一致する、効率的な学習アルゴリズムを提供する。
また,提案アルゴリズムを実験的に評価し,実験性能が最適に近いことを示すとともに,動的に変化するシーケンスに自動的に適応することを示す。
関連論文リスト
- A Survey of Meta-features Used for Automated Selection of Algorithms for Black-box Single-objective Continuous Optimization [4.173197621837912]
単目的連続ブラックボックス最適化の分野におけるアルゴリズム選択への重要な貢献について概説する。
自動アルゴリズム選択、構成、性能予測のための機械学習モデルについて検討する。
論文 参考訳（メタデータ） (2024-06-08T11:11:14Z) - Large Language Model-Enhanced Algorithm Selection: Towards Comprehensive Algorithm Representation [27.378185644892984]
本稿では,Large Language Models (LLM) をアルゴリズム選択に導入する。
LLMはアルゴリズムの構造的・意味的な側面を捉えるだけでなく、文脈的認識とライブラリ機能理解も示している。
選択されたアルゴリズムは、与えられた問題と異なるアルゴリズムの一致度によって決定される。
論文 参考訳（メタデータ） (2023-11-22T06:23:18Z) - Dual Algorithmic Reasoning [9.701208207491879]
本稿では,基礎となるアルゴリズム問題の双対性を利用してアルゴリズムを学習することを提案する。
アルゴリズム学習における最適化問題の2つの定義を同時に学習することで、より良い学習が可能になることを実証する。
次に、難易度の高い脳血管分類タスクにデプロイすることで、二元アルゴリズム推論の現実的な実用性を検証する。
論文 参考訳（メタデータ） (2023-02-09T08:46:23Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳（メタデータ） (2022-10-02T05:03:38Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Algorithm Selection on a Meta Level [58.720142291102135]
本稿では,与えられたアルゴリズムセレクタの組み合わせに最適な方法を求めるメタアルゴリズム選択の問題を紹介する。
本稿では,メタアルゴリズム選択のための一般的な方法論フレームワークと,このフレームワークのインスタンス化として具体的な学習手法を提案する。
論文 参考訳（メタデータ） (2021-07-20T11:23:21Z) - Benchmarking Simulation-Based Inference [5.3898004059026325]
確率的モデリングの最近の進歩は、確率の数値的評価を必要としないシミュレーションに基づく推論アルゴリズムを多数もたらした。
推論タスクと適切なパフォーマンス指標を備えたベンチマークを,アルゴリズムの初期選択とともに提供する。
性能指標の選択は重要であり、最先端のアルゴリズムでさえ改善の余地があり、逐次推定によりサンプリング効率が向上することがわかった。
論文 参考訳（メタデータ） (2021-01-12T18:31:22Z) - Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。
学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。
従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文 参考訳（メタデータ） (2021-01-08T18:55:07Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。