論文の概要: Accelerating ERM for data-driven algorithm design using output-sensitive techniques

• arxiv url: http://arxiv.org/abs/2204.03569v3
• Date: Wed, 23 Oct 2024 20:21:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-27 22:31:31.572485
• Title: Accelerating ERM for data-driven algorithm design using output-sensitive techniques
• Title（参考訳）: 出力感度技術を用いたデータ駆動型アルゴリズム設計のためのEMMの高速化
• Authors: Maria-Florina Balcan, Christopher Seiler, Dravyansh Sharma,
• Abstract要約: データ駆動型アルゴリズム設計のための効率的な学習アルゴリズムを開発するための技術について研究する。 提案手法は,超平面の集合によって誘導されるポリトープを列挙する出力感受性アルゴリズムである。 本稿では、価格問題、リンクベースのクラスタリング、動的プログラミングに基づくシーケンスアライメントのアルゴリズムを提供することにより、我々の技術を説明する。
• 参考スコア（独自算出の注目度）: 26.32088674030797
• License:
• Abstract: Data-driven algorithm design is a promising, learning-based approach for beyond worst-case analysis of algorithms with tunable parameters. An important open problem is the design of computationally efficient data-driven algorithms for combinatorial algorithm families with multiple parameters. As one fixes the problem instance and varies the parameters, the "dual" loss function typically has a piecewise-decomposable structure, i.e. is well-behaved except at certain sharp transition boundaries. In this work we initiate the study of techniques to develop efficient ERM learning algorithms for data-driven algorithm design by enumerating the pieces of the sum dual loss functions for a collection of problem instances. The running time of our approach scales with the actual number of pieces that appear as opposed to worst case upper bounds on the number of pieces. Our approach involves two novel ingredients -- an output-sensitive algorithm for enumerating polytopes induced by a set of hyperplanes using tools from computational geometry, and an execution graph which compactly represents all the states the algorithm could attain for all possible parameter values. We illustrate our techniques by giving algorithms for pricing problems, linkage-based clustering and dynamic-programming based sequence alignment.
• Abstract（参考訳）: データ駆動型アルゴリズム設計は、調整可能なパラメータを持つアルゴリズムの最悪のケース分析を超えた、有望な学習ベースのアプローチである。 重要なオープン問題は、複数のパラメータを持つ組合せアルゴリズムファミリーのための計算効率の良いデータ駆動アルゴリズムの設計である。 問題のインスタンスを修正してパラメータを変更すると、「双対」損失関数は通常、断片的に分解可能な構造を持つ。 本研究では,データ駆動型アルゴリズム設計のための効率的なEMM学習アルゴリズムを開発するための手法の研究を,問題インスタンスの集合に対する和二重損失関数のピースを列挙することによって開始する。 アプローチの実行時間は,最悪の場合のピース数上限に対して,実際のピース数でスケールする。 提案手法は,計算幾何学のツールを用いて超平面の集合によって誘導されるポリトープを列挙する出力感受性アルゴリズムと,アルゴリズムが可能な全てのパラメータ値に対して達成できる全ての状態をコンパクトに表現する実行グラフである。 本稿では,価格問題,リンケージに基づくクラスタリング,動的プログラミングに基づくシーケンスアライメントのアルゴリズムを提案する。

関連論文リスト

• GreedyML: A Parallel Algorithm for Maximizing Submodular Functions [2.9998889086656586]
  分散メモリマルチプロセッサ上での単調部分モジュラ関数の最大化のための並列近似アルゴリズムについて述べる。 我々の研究は、データ要約、機械学習、グラフスカラー化といった分野における実践的な応用のために、大規模データセットのサブモジュラー最適化問題を解決する必要性によって動機付けられている。
  論文  参考訳（メタデータ） (2024-03-15T14:19:09Z)
• Learning the hub graphical Lasso model with the structured sparsity via an efficient algorithm [1.0923877073891446]
  ハブグラフィカルモデルを推定する二相アルゴリズムを提案する。 提案アルゴリズムはまず,乗算器の2つの交互方向法を用いてよい初期点を生成する。 その後、半滑らかなニュートン(SSN)ベースの拡張ラグランジアン法(ALM)を温め、実用的なタスクに十分正確な解を計算する。
  論文  参考訳（メタデータ） (2023-08-17T08:24:28Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms [5.478671305092084]
  本稿では,ParlayANNについて紹介する。ParlayANNは決定論的および並列グラフに基づく近接探索アルゴリズムのライブラリである。 我々は、数十億のデータセットにスケールする4つの最先端グラフベースのANNSアルゴリズムに対して、新しい並列実装を開発する。
  論文  参考訳（メタデータ） (2023-05-07T19:28:23Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Data-driven Algorithm Design [21.39493074700162]
  データ駆動型アルゴリズム設計は、現代のデータ科学とアルゴリズム設計の重要な側面である。 パラメータの小さな微調整は、アルゴリズムの振る舞いのカスケードを引き起こす可能性がある。 バッチおよびオンラインシナリオに対して、強力な計算および統計的パフォーマンス保証を提供する。
  論文  参考訳（メタデータ） (2020-11-14T00:51:57Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)
• MATE: A Model-based Algorithm Tuning Engine [2.4693304175649304]
  モデルに基づくアルゴリズム変換エンジン、すなわちMATEを導入し、アルゴリズムのパラメータを目標最適化問題の特徴の表現として表現する。 パラメータと問題の特徴の関係を象徴的回帰問題として求める問題を定式化し,遺伝子プログラミングを用いてこれらの表現を抽出する。 本評価では,OneMax,LeadingOnes,BinValue,Jumpの最適化問題に対して,(1+1) EAおよびRSSアルゴリズムの構成に適用する。
  論文  参考訳（メタデータ） (2020-04-27T12:50:48Z)

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

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