論文の概要: Output-sensitive ERM-based techniques for data-driven algorithm design
- arxiv url: http://arxiv.org/abs/2204.03569v2
- Date: Sat, 30 Sep 2023 00:54:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-03 21:28:24.465156
- Title: Output-sensitive ERM-based techniques for data-driven algorithm design
- Title(参考訳): データ駆動型アルゴリズム設計のための出力感度ERMに基づく手法
- Authors: Maria-Florina Balcan, Christopher Seiler and Dravyansh Sharma
- Abstract要約: データ駆動型アルゴリズム設計のための効率的な学習アルゴリズムを開発するための技術について研究する。
提案手法は,超平面の集合によって誘導されるポリトープを列挙する出力感受性アルゴリズムである。
本稿では、価格問題、リンクベースのクラスタリング、動的プログラミングに基づくシーケンスアライメントのアルゴリズムを提供することにより、我々の技術を説明する。
- 参考スコア(独自算出の注目度): 29.582038951852553
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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(参考訳): データ駆動型アルゴリズム設計は、調整可能なパラメータを持つアルゴリズムの最悪のケース分析を超えた、有望な学習ベースのアプローチである。
重要なオープン問題は、複数のパラメータを持つ組合せアルゴリズムファミリーのための計算効率の良いデータ駆動アルゴリズムの設計である。
問題のインスタンスを修正してパラメータを変更すると、「双対」損失関数は通常、断片的に分解可能な構造を持つ。
本研究では,問題インスタンスの集合に対する和双対損失関数を列挙することにより,データ駆動アルゴリズム設計のための効率的なerm学習アルゴリズムを開発する手法の研究を開始する。
私たちのアプローチの実行時間は、ピース数に対する最悪のケース上限とは対照的に、実際のピース数でスケールします。
計算幾何学のツールを用いて超平面群によって誘導されるポリトープを列挙する出力センシティブアルゴリズムと、アルゴリズムが可能な全てのパラメータ値に対して達成可能な全ての状態をコンパクトに表現する実行グラフである。
提案手法は,価格問題,リンクベースのクラスタリング,動的プログラミングに基づくシーケンスアライメントなどのアルゴリズムを提供することにより,本手法を説明する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。