論文の概要: Faster algorithms for learning to link, align sequences, and price
two-part tariffs
- arxiv url: http://arxiv.org/abs/2204.03569v1
- Date: Thu, 7 Apr 2022 17:27:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-08 15:58:50.431582
- Title: Faster algorithms for learning to link, align sequences, and price
two-part tariffs
- Title（参考訳）: リンク、配列調整、価格2部関税を学習するための高速アルゴリズム
- Authors: Maria-Florina Balcan, Christopher Seiler and Dravyansh Sharma
- Abstract要約: 効率的な(出力-ポリノミカルな)多次元パラメータチューニングのためのアルゴリズムを提供する。
重要な問題固有の課題は、パラメータ空間の分割が1つのアルゴリズムのステップでどのように変化するかを効率的に計算することである。
リンクベースのクラスタリング、シーケンスアライメント、および2部分の価格設定において、これまで最もよく知られていた結果のランタイムを改善するアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 21.934701175543555
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Data-driven algorithm configuration is a promising, learning-based approach
for beyond worst-case analysis of algorithms with tunable parameters. An
important open problem is the design of efficient data-driven algorithms for
algorithm families with more than one parameter. In this work we provide
algorithms for efficient (output-polynomial) multidimensional parameter tuning,
i.e. for families with a small constant number of parameters, for three very
different combinatorial problems -- linkage-based clustering, dynamic
programming for sequence alignment, and auction design for two-part tariff
schemes. We extend the single-parameter clustering algorithm of Balcan et al.
2020 arXiv:1907.00533 to multiple parameters and to the sequence alignment
problem by proposing an execution graph which compactly represents all the
states the algorithm could attain for all possible parameter values. A key
problem-specific challenge is to efficiently compute how the partition of the
parameter space (into regions with unique algorithmic states) changes with a
single algorithmic step. We give algorithms which improve on the runtime of
previously best known results for linkage-based clustering, sequence alignment
and two-part tariff pricing.
- Abstract（参考訳）: データ駆動アルゴリズムの構成は、調整可能なパラメータを持つアルゴリズムの最悪のケース分析を越えて、有望で学習ベースのアプローチである。
重要なオープン問題は、複数のパラメータを持つアルゴリズムファミリのための効率的なデータ駆動アルゴリズムの設計である。
本研究では,3つの非常に異なる組合せ問題 - 連鎖型クラスタリング,シーケンスアライメントのための動的プログラミング,二部関税体系のオークション設計 - に対して,効率的な(出力多項)多次元パラメータチューニングのためのアルゴリズムを提供する。
我々は,Balcanらによる単一パラメータクラスタリングアルゴリズムであるarXiv:1907.00533を複数のパラメータに拡張し,アルゴリズムが可能なすべてのパラメータ値に対して達成できる全ての状態をコンパクトに表現する実行グラフを提案する。
問題に特有な課題は、パラメータ空間(一意なアルゴリズム状態を持つ領域)の分割が単一のアルゴリズムステップでどのように変化するかを効率的に計算することである。
リンクベースのクラスタリング,シーケンスアライメント,二部関税価格といった,これまで最もよく知られた結果のランタイムを改善するアルゴリズムを提供する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。