論文の概要: Systematic Parameter Decision in Approximate Model Counting
- arxiv url: http://arxiv.org/abs/2504.05874v1
- Date: Tue, 08 Apr 2025 09:58:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-09 13:30:13.763681
- Title: Systematic Parameter Decision in Approximate Model Counting
- Title（参考訳）: 近似モデル計数における体系的パラメータ決定
- Authors: Jinping Lei, Toru Takisaka, Junqiang Peng, Mingyu Xiao,
- Abstract要約: 本稿ではハッシュベースの近似モデルカウントアルゴリズム$mathsfApproxMC$の内部パラメータを決定する新しい手法を提案する。
削減後、結果の最適化問題は極めて単純な形で行われ、基本的な探索アルゴリズムが利用可能となる。
実験の結果,最新の$mathsfApproxMC$のパラメータを1.6～2.4で改善した。
- 参考スコア（独自算出の注目度）: 15.68459774228961
- License:
- Abstract: This paper proposes a novel approach to determining the internal parameters of the hashing-based approximate model counting algorithm $\mathsf{ApproxMC}$. In this problem, the chosen parameter values must ensure that $\mathsf{ApproxMC}$ is Probably Approximately Correct (PAC), while also making it as efficient as possible. The existing approach to this problem relies on heuristics; in this paper, we solve this problem by formulating it as an optimization problem that arises from generalizing $\mathsf{ApproxMC}$'s correctness proof to arbitrary parameter values. Our approach separates the concerns of algorithm soundness and optimality, allowing us to address the former without the need for repetitive case-by-case argumentation, while establishing a clear framework for the latter. Furthermore, after reduction, the resulting optimization problem takes on an exceptionally simple form, enabling the use of a basic search algorithm and providing insight into how parameter values affect algorithm performance. Experimental results demonstrate that our optimized parameters improve the runtime performance of the latest $\mathsf{ApproxMC}$ by a factor of 1.6 to 2.4, depending on the error tolerance.
- Abstract（参考訳）: 本稿ではハッシュベースの近似モデルカウントアルゴリズム$\mathsf{ApproxMC}$の内部パラメータを決定する新しい手法を提案する。
この問題では、選択されたパラメータ値は、$\mathsf{ApproxMC}$がほぼ正しいことを保証すると同時に、可能な限り効率的にする必要がある。
本稿では,パラメータ値に対する$\mathsf{ApproxMC}$'s correctness proofの一般化から生じる最適化問題として定式化することによって,この問題を解決する。
提案手法では,アルゴリズムの健全性と最適性に関する懸念を分離し,ケース・バイ・ケースの議論を繰り返すことなく前者に対応するとともに,後者の明確な枠組みを確立する。
さらに、削減後の最適化問題は、基本探索アルゴリズムの使用を可能にし、パラメータ値がアルゴリズムのパフォーマンスにどのように影響するかを洞察するなど、非常に単純な形式を採っている。
実験結果から,最新の$\mathsf{ApproxMC}$の最適化されたパラメータは,エラー耐性に応じて1.6～2.4の係数で実行性能を向上することが示された。
関連論文リスト
- Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
パスワイズ法は、ペナライズされた推定器の完全な経路を効率的に計算することができる。
これらのアルゴリズムを離散時間で観測されたプロセスのペナル化推定に適用する。
論文 参考訳（メタデータ） (2024-12-05T10:38:29Z) - RIGA: A Regret-Based Interactive Genetic Algorithm [14.388696798649658]
そこで本研究では,多目的最適化問題を優先的精度で解くための対話型遺伝的アルゴリズムを提案する。
我々のアルゴリズムはRIGAと呼ばれ、集約関数がパラメータ内で線形であることから、任意の多目的最適化問題に適用できる。
いくつかのパフォーマンス指標(計算時間、最適性とクエリ数のギャップ)に対して、RIGAは最先端のアルゴリズムよりも優れた結果を得る。
論文 参考訳（メタデータ） (2023-11-10T13:56:15Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From
a Power-Law Distribution [8.34061303235504]
ほとんどの進化的アルゴリズムは複数のパラメータを持ち、その値は性能に大きな影響を及ぼす。
そこで本研究では,各繰り返しにおけるパラメータの値を,適切にスケールされたパワー・ロー分布からランダムに選択する,遅延だが効果的な解を提案する。
静的パラメータで知られている最高のパフォーマンスに匹敵する性能を保証する。
論文 参考訳（メタデータ） (2021-04-14T09:17:18Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。
本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。
本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-04T00:26:56Z) - Alternating Direction Method of Multipliers for Quantization [15.62692130672419]
量子化のための乗算器の交互方向法(texttADMM-Q$)アルゴリズムの性能について検討する。
不正確な更新ルールを処理できる$texttADMM-Q$のいくつかのバリエーションを開発しています。
提案手法の有効性を実証的に評価した。
論文 参考訳（メタデータ） (2020-09-08T01:58:02Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - MATE: A Model-based Algorithm Tuning Engine [2.4693304175649304]
モデルに基づくアルゴリズム変換エンジン、すなわちMATEを導入し、アルゴリズムのパラメータを目標最適化問題の特徴の表現として表現する。
パラメータと問題の特徴の関係を象徴的回帰問題として求める問題を定式化し,遺伝子プログラミングを用いてこれらの表現を抽出する。
本評価では,OneMax,LeadingOnes,BinValue,Jumpの最適化問題に対して,(1+1) EAおよびRSSアルゴリズムの構成に適用する。
論文 参考訳（メタデータ） (2020-04-27T12:50:48Z) - Tightly Robust Optimization via Empirical Domain Reduction [22.63829081634384]
提案手法は,解が良好な目的値を持つようなスケールを決定するアルゴリズムである。
いくつかの規則性条件下では、我々のアルゴリズムで得られるスケールは$O(sqrtn)$、標準アプローチで得られるスケールは$O(sqrtd/n)$である。
論文 参考訳（メタデータ） (2020-02-29T12:24:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。