論文の概要: Accelerating Matroid Optimization through Fast Imprecise Oracles

• arxiv url: http://arxiv.org/abs/2402.02774v2
• Date: Tue, 05 Nov 2024 16:34:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-06 14:55:43.194958
• Title: Accelerating Matroid Optimization through Fast Imprecise Oracles
• Title（参考訳）: 高速不正確オラクルによるマトロイド最適化の高速化
• Authors: Franziska Eberle, Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu, Nicole Megow, Jens Schlöter,
• Abstract要約: 汚いオラクルの品質について,クリーンなクエリをほとんど使用しない実用的なアルゴリズムを解析する。 特に、我々のアルゴリズムは、多くの点で、最も有益であることを示す。 我々は、他のマトロイドオラクルタイプ、非自由な汚いオークル、その他のマトロイド問題への拡張を概説する。
• 参考スコア（独自算出の注目度）: 40.94053997358159
• License:
• Abstract: Querying complex models for precise information (e.g. traffic models, database systems, large ML models) often entails intense computations and results in long response times. Thus, weaker models which give imprecise results quickly can be advantageous, provided inaccuracies can be resolved using few queries to a stronger model. In the fundamental problem of computing a maximum-weight basis of a matroid, a well-known generalization of many combinatorial optimization problems, algorithms have access to a clean oracle to query matroid information. We additionally equip algorithms with a fast but dirty oracle modelling an unknown, potentially different matroid. We design and analyze practical algorithms which only use few clean queries w.r.t. the quality of the dirty oracle, while maintaining robustness against arbitrarily poor dirty matroids, approaching the performance of classic algorithms for the given problem. Notably, we prove that our algorithms are, in many respects, best-possible. Further, we outline extensions to other matroid oracle types, non-free dirty oracles and other matroid problems.
• Abstract（参考訳）: 正確な情報(例えば、トラフィックモデル、データベースシステム、大規模なMLモデル)に対する複雑なモデルのクエリは、しばしば激しい計算と長い応答時間を必要とする。 このように、不正確な結果を素早く得る弱いモデルは有利であり、より強いモデルに対するクエリが少ないため、不正確さを解決できる。 マトロイドの最大ウェイト基底を計算する基本的な問題、多くの組合せ最適化問題のよく知られた一般化では、アルゴリズムはマトロイド情報をクエリするためのクリーンなオラクルにアクセスすることができる。 さらに、未知の、潜在的に異なるマトロイドをモデル化する高速だが汚いオラクルをアルゴリズムに装備する。 クリーンなクエリの少ない汚いオラクルの品質しか使用しない実用的なアルゴリズムを設計・解析し、また、任意に貧弱な汚いマトロイドに対するロバスト性を維持し、与えられた問題に対する古典的なアルゴリズムの性能にアプローチする。 特に、我々のアルゴリズムは、多くの点で、最も有益であることを示す。 さらに、他のマトロイドオラクルタイプ、非自由な汚いオークル、その他のマトロイド問題への拡張を概説する。

関連論文リスト

• Fast White-Box Adversarial Streaming Without a Random Oracle [48.45771871410984]
  我々は,従来の無作為なコインとストリーミングアルゴリズムが使用するパラメータに,敵対者がアクセス可能な強力なホワイトボックス逆数モデルを考える。 我々はスパースリカバリ問題に焦点を合わせ、その結果を異なる要素推定などのタスクに拡張する。 ホワイトボックス逆数ストリームにおけるスパースリカバリ問題に対する準最適解を構築し, 誤りを仮定した学習に基づく。
  論文  参考訳（メタデータ） (2024-06-10T21:23:19Z)
• ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers [60.6418431624873]
  大きな言語モデル(LLM)は、機能記述からコードを実装するのに優れているが、アルゴリズムの問題に悩まされている。 我々は,アルゴリズムプログラムを LLM 生成 Oracle で合成するフレームワーク ALGO を提案し,その生成をガイドし,その正確性を検証する。 実験の結果,ALGOを装着すると,Codexモデルよりも8倍,CodeTよりも2.6倍の1サブミッションパス率が得られることがわかった。
  論文  参考訳（メタデータ） (2023-05-24T00:10:15Z)
• Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs [0.0]
  混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。 近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。 本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
  論文  参考訳（メタデータ） (2022-02-07T18:52:56Z)
• Robust and Accurate Superquadric Recovery: a Probabilistic Approach [29.7543198254021]
  点雲から超四分儀を回収する最初の確率的手法を提案する。 提案手法は, 合成データセットと実世界のデータセットの精度, 効率, 堅牢性の観点から, 最先端の手法より優れている。
  論文  参考訳（メタデータ） (2021-11-29T13:17:17Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters [10.279748604797911]
  機械学習とデータサイエンスの主な問題は、最適化問題として日常的にモデル化され、最適化アルゴリズムによって解決される。 データ量の増加と、これらの不条件最適化タスクを定式化するために使用される統計モデルのサイズと複雑さにより、これらの課題に対処できる新しい効率的なアルゴリズムが必要である。 この論文では,これらの課題をそれぞれ異なる方法で処理する。ビッグデータ問題に効率的に対処するために,各イテレーションでトレーニングデータの小さなランダムサブセットのみを検査する新しい手法を開発する。 大きなモデル問題に対処するために、イテレーション毎に更新されるメソッドを開発します。
  論文  参考訳（メタデータ） (2020-08-26T21:15:18Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。 アルゴリズムは最悪の場合でも差分プライバシーを満たす。 現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
  論文  参考訳（メタデータ） (2020-07-10T15:46:05Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)
• Learning fine-grained search space pruning and heuristics for combinatorial optimization [5.72274610208488]
  本稿では,機械学習技術を利用して正確な最適化アルゴリズムをスケールアップするフレームワークを提案する。 我々のフレームワークは、問題インスタンスのサイズを減らすために、要素を刈り取るという比較的単純なタスクを学習します。 我々のフレームワークは入力グラフのかなりの部分を取り除き、なおも最大傾きのほとんどを検出可能であることを示す。
  論文  参考訳（メタデータ） (2020-01-05T13:10:39Z)

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

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