論文の概要: Rounding Meets Approximate Model Counting
- arxiv url: http://arxiv.org/abs/2305.09247v1
- Date: Tue, 16 May 2023 07:53:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-17 15:56:48.479798
- Title: Rounding Meets Approximate Model Counting
- Title（参考訳）: Roundingが近似モデルカウントを発表
- Authors: Jiong Yang and Kuldeep S. Meel
- Abstract要約: モデルカウントは、幅広い応用のコンピュータ科学における基本的な問題である。
我々は,より小さな$delta$の値に対して,実行時の大幅な削減を実現するためのラウンドリングに基づく新しいアプローチを提案する。
RoundMCと呼ばれる結果のカウンタは,現在の最先端カウンタであるApproxMCに対して,大幅なランタイムパフォーマンスの向上を実現している。
- 参考スコア（独自算出の注目度）: 37.83201307518836
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of model counting, also known as #SAT, is to compute the number
of models or satisfying assignments of a given Boolean formula $F$. Model
counting is a fundamental problem in computer science with a wide range of
applications. In recent years, there has been a growing interest in using
hashing-based techniques for approximate model counting that provide
$(\varepsilon, \delta)$-guarantees: i.e., the count returned is within a
$(1+\varepsilon)$-factor of the exact count with confidence at least
$1-\delta$. While hashing-based techniques attain reasonable scalability for
large enough values of $\delta$, their scalability is severely impacted for
smaller values of $\delta$, thereby preventing their adoption in application
domains that require estimates with high confidence.
The primary contribution of this paper is to address the Achilles heel of
hashing-based techniques: we propose a novel approach based on rounding that
allows us to achieve a significant reduction in runtime for smaller values of
$\delta$. The resulting counter, called RoundMC, achieves a substantial runtime
performance improvement over the current state-of-the-art counter, ApproxMC. In
particular, our extensive evaluation over a benchmark suite consisting of 1890
instances shows that RoundMC solves 204 more instances than ApproxMC, and
achieves a $4\times$ speedup over ApproxMC.
- Abstract（参考訳）: モデルカウントの問題は、#SATとしても知られ、モデルの数を計算したり、与えられたブール式$F$の割り当てを満たすことである。
モデルカウントは、幅広い応用のコンピュータ科学における基本的な問題である。
近年では、(\varepsilon, \delta)$-guarantees を提供する近似モデルカウントにハッシュベースのテクニックを使うことへの関心が高まっている。
ハッシュベースのテクニックは、$\delta$の十分な値に対して合理的なスケーラビリティを実現する一方で、そのスケーラビリティは$\delta$の小さな値に対して深刻な影響を受けており、高い信頼性の見積を必要とするアプリケーションドメインでの採用を妨げます。
この論文の主な貢献は、ハッシュベースの手法のアキレス腱に対処することである。我々は、より小さい値の$\delta$のランタイムを大幅に削減できる丸めに基づく新しいアプローチを提案します。
RoundMCと呼ばれる結果のカウンタは,現在の最先端カウンタであるApproxMCに対して,大幅なランタイムパフォーマンスの向上を実現している。
特に、1890年のインスタンスからなるベンチマークスイートに対する我々の広範な評価は、RoundMCがApproxMCよりも204以上のインスタンスを解決し、ApproxMCよりも4\times$のスピードアップを実現していることを示している。
関連論文リスト
- On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis [22.641550077885686]
我々は,Visual Autoregressive(mathsf/$)モデルの計算限界と効率基準を分析する。
より詳細な複雑性理論からStrong Exponential Time hypothesis(mathsfSETH$)を仮定すると、$mathsf/$モデルに対する準量子時間アルゴリズムは不可能である。
私たちの技術は、$mathsf/$フレームワークでスケーラブルで効率的な画像生成を推し進めることに重点を置いています。
論文 参考訳（メタデータ） (2025-01-08T09:34:15Z) - Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - On the Fine-Grained Hardness of Inverting Generative Models [21.566795159091747]
生成モデル反転は、コンピュータビジョンとNLPを含む多くの現代のアプリケーションにおいて、コア計算プリミティブである。
本稿では,この問題に対する計算硬さの景観を詳細に把握することを目的としている。
強い指数時間仮説 (SETH) の下では、正確な逆転の計算複雑性が$Omega (2n)$で制限されることを示した。
近似反転のより実践的な問題として、モデル範囲の点が与えられた目標に近いかどうかを決定することが目的である。
論文 参考訳（メタデータ） (2023-09-11T20:03:25Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - SoS Degree Reduction with Applications to Clustering and Robust Moment
Estimation [3.6042575355093907]
我々は,新しい変数を導入することにより,二乗証明の総和の程度を大幅に減少させる汎用フレームワークを開発した。
クラスタリングとロバストモーメント推定という2つの重要な推定問題に対して,2乗和に基づくアルゴリズムを高速化する。
論文 参考訳（メタデータ） (2021-01-05T13:49:59Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Improving Robustness and Generality of NLP Models Using Disentangled
Representations [62.08794500431367]
スーパービジョンニューラルネットワークはまず入力$x$を単一の表現$z$にマップし、次に出力ラベル$y$にマッピングする。
本研究では,非交叉表現学習の観点から,NLPモデルの堅牢性と汎用性を改善する手法を提案する。
提案した基準でトレーニングしたモデルは、広範囲の教師付き学習タスクにおいて、より堅牢性とドメイン適応性を向上することを示す。
論文 参考訳（メタデータ） (2020-09-21T02:48:46Z) - Sparse Regression at Scale: Branch-and-Bound rooted in First-Order
Optimization [6.037383467521294]
我々は $ell_0$ 正規化回帰のための新しい正確な MIP フレームワークを提案する。
私たちのフレームワークは、$p sim 107$までスケールでき、少なくとも5,000$xのスピードアップを達成できます。
実装をツールキットL0BnBでオープンソースにしています。
論文 参考訳（メタデータ） (2020-04-13T18:45:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。