論文の概要: Choosing the Right Algorithm With Hints From Complexity Theory
- arxiv url: http://arxiv.org/abs/2109.06584v1
- Date: Tue, 14 Sep 2021 11:12:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-15 15:31:29.481653
- Title: Choosing the Right Algorithm With Hints From Complexity Theory
- Title（参考訳）: 複雑性理論のヒントで正しいアルゴリズムを選ぶ
- Authors: Shouda Wang and Weijie Zheng and Benjamin Doerr
- Abstract要約: 我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。
O(n log n)$ランタイムを持つこのタイプの人工アルゴリズムは、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)がDLB問題を時間内に解くことができるという結果をもたらす。
- 参考スコア（独自算出の注目度）: 4.38301148531795
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Choosing a suitable algorithm from the myriads of different search heuristics
is difficult when faced with a novel optimization problem. In this work, we
argue that the purely academic question of what could be the best possible
algorithm in a certain broad class of black-box optimizers can give fruitful
indications in which direction to search for good established optimization
heuristics. We demonstrate this approach on the recently proposed DLB
benchmark, for which the only known results are $O(n^3)$ runtimes for several
classic evolutionary algorithms and an $O(n^2 \log n)$ runtime for an
estimation-of-distribution algorithm. Our finding that the unary unbiased
black-box complexity is only $O(n^2)$ suggests the Metropolis algorithm as an
interesting candidate and we prove that it solves the DLB problem in quadratic
time. Since we also prove that better runtimes cannot be obtained in the class
of unary unbiased algorithms, we shift our attention to algorithms that use the
information of more parents to generate new solutions. An artificial algorithm
of this type having an $O(n \log n)$ runtime leads to the result that the
significance-based compact genetic algorithm (sig-cGA) can solve the DLB
problem also in time $O(n \log n)$. Our experiments show a remarkably good
performance of the Metropolis algorithm, clearly the best of all algorithms
regarded for reasonable problem sizes.
- Abstract（参考訳）: 異なる探索ヒューリスティックのミリアードから適切なアルゴリズムを選択することは、新しい最適化問題に直面すると困難である。
本研究では,ブラックボックスオプティマイザの幅広いクラスにおいて,どのようなアルゴリズムが最良かという純粋に学術的な疑問は,適切な最適化ヒューリスティックを探索する方向を示す実りある指標を与えることができると論じる。
最近提案されたdlbベンチマークでこのアプローチを実証し、既知の結果はいくつかの古典的な進化アルゴリズムの$o(n^3)$ランタイムと、推定分布アルゴリズムの$o(n^2 \log n)$ランタイムのみである。
単項ブラックボックスの複雑性が$O(n^2)$であることは、メトロポリスアルゴリズムを興味深い候補として提案し、二次時間でDLB問題を解くことを証明した。
我々はまた、より良いランタイムが偏りのないアルゴリズムのクラスでは得られないことを証明するので、より多くの親の情報を使って新しいソリューションを生成するアルゴリズムに注意を移す。
このタイプの人工アルゴリズムは、$O(n \log n)$ランタイムを持つので、意味に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、時間$O(n \log n)$でもDLB問題を解決することができる。
我々の実験はメトロポリスのアルゴリズムの優れた性能を示しており、明らかに妥当な問題サイズとみなす全てのアルゴリズムの中で最高のものである。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and
Tree-Search Algorithms [13.152347996965297]
混合プログラム(MIP)は、コンピュータサイエンス、オペレーションリサーチ、ファイナンシャルエンジニアリングに関心を持つ多くの最適化問題をモデル化する。
Branch-and-Cutアルゴリズムは、ブランチ・アンド・バウンド論理とカットプレーンルーチンを組み合わせることで、現代のMIPソルバのコアとなる。
本稿では,古典的分岐と境界のアルゴリズムを用いた量子アルゴリズムIncremental-Quantum-Branch-and-Boundを提案する。
論文 参考訳（メタデータ） (2022-10-06T21:08:46Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - First Steps Towards a Runtime Analysis When Starting With a Good
Solution [8.34061303235504]
現実的な応用では、ランダムな解よりも優れた解を推測することができる。
我々は、異なるアルゴリズムがより良い初期解と全く異なる程度に利益を得ることを示す。
このことは、進化的アルゴリズムが良い初期解をうまく活用していることがまだ見つからないことを示唆している。
論文 参考訳（メタデータ） (2020-06-22T11:46:42Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。