論文の概要: Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization

• arxiv url: http://arxiv.org/abs/2410.17945v1
• Date: Wed, 23 Oct 2024 15:18:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-24 13:54:38.461504
• Title: Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization
• Title（参考訳）: 制約付き離散最適化のための大集合の理論的に接地されたプルーニング
• Authors: Ankur Nath, Alan Kuhnle,
• Abstract要約: 最適解にはならない要素を破棄する軽量プルーニングアルゴリズムを開発した。 軽微な仮定の下では、最適値が保持される割合と、得られたプルーニングされた基底集合のサイズに関する理論的保証が証明される。 私たちのアルゴリズムであるQuickPruneは、地面の90%以上を効率よくプルーンし、最先端の古典的および機械学習より優れている。
• 参考スコア（独自算出の注目度）: 12.016449555335976
• License:
• Abstract: Modern instances of combinatorial optimization problems often exhibit billion-scale ground sets, which have many uninformative or redundant elements. In this work, we develop light-weight pruning algorithms to quickly discard elements that are unlikely to be part of an optimal solution. Under mild assumptions on the instance, we prove theoretical guarantees on the fraction of the optimal value retained and the size of the resulting pruned ground set. Through extensive experiments on real-world datasets for various applications, we demonstrate that our algorithm, QuickPrune, efficiently prunes over 90% of the ground set and outperforms state-of-the-art classical and machine learning heuristics for pruning.
• Abstract（参考訳）: 現代の組合せ最適化問題の例は、多くの非形式的あるいは冗長な要素を持つ数十億の基底集合を示すことが多い。 本研究では,最適解の一部である可能性が低い要素を迅速に破棄する軽量プルーニングアルゴリズムを開発した。 ケース上の軽微な仮定の下では、最適値が保持される割合と、得られたプルーニングされた基底集合のサイズに関する理論的保証が証明される。 さまざまなアプリケーションのための実世界のデータセットに関する広範な実験を通じて、我々のアルゴリズムであるQuickPruneが、地上の90%以上を効率よくプーンし、最先端の古典的および機械学習ヒューリスティックスより優れていることを実証した。

関連論文リスト

• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Fast Bayesian Optimization of Needle-in-a-Haystack Problems using Zooming Memory-Based Initialization [73.96101108943986]
  Needle-in-a-Haystack問題は、データセットのサイズに対して最適な条件が極端に不均衡であるときに発生する。 本稿では,従来のベイズ最適化原理に基づくズームメモリに基づく初期化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T23:57:41Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• Data-Efficient Structured Pruning via Submodular Optimization [32.574190896543705]
  部分モジュラ最適化に基づくデータ効率の高い構造化プルーニング手法を提案する。 この選択問題は弱い部分モジュラー問題であり、効率的なグリードアルゴリズムを用いて証明可能な近似が可能であることを示す。 本手法は,限られた数のトレーニングデータのみを使用し,ラベルを含まない文献の中では数少ない手法の一つである。
  論文  参考訳（メタデータ） (2022-03-09T18:40:29Z)
• Automatic Mapping of the Best-Suited DNN Pruning Schemes for Real-Time Mobile Acceleration [71.80326738527734]
  本稿では,汎用的,きめ細かな構造化プルーニング手法とコンパイラの最適化を提案する。 提案手法は,より微細な構造化プルーニング手法とともに,最先端のDNN最適化フレームワークよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-11-22T23:53:14Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。 理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。 我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
  論文  参考訳（メタデータ） (2021-08-11T20:21:30Z)
• Strong Optimal Classification Trees [8.10995244893652]
  最適二分分類木を学習するための直感的なフローベースMIO定式化を提案する。 我々の定式化は、解釈可能かつ公平な決定木の設計を可能にするために、サイド制約を満たすことができる。 提案手法は最先端MIO技術よりも29倍高速であることを示す。
  論文  参考訳（メタデータ） (2021-03-29T21:40:58Z)
• Stochastic Optimization Forests [60.523606291705214]
  標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。 概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
  論文  参考訳（メタデータ） (2020-08-17T16:56:06Z)
• Structure Adaptive Algorithms for Stochastic Bandits [22.871155520200773]
  構造化多武装バンディット問題のクラスにおける報酬最大化について検討する。 平均的な武器の報酬は、与えられた構造的制約を満たす。 我々は、反復的なサドルポイントソルバを用いて、インスタンス依存の低バウンドからのアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-07-02T08:59:54Z)

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

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