論文の概要: A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick Model
- arxiv url: http://arxiv.org/abs/2611.05446v1
- Date: Tue, 03 Nov 2026 17:28:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-06 03:25:57.809486
- Title: A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick Model
- Title(参考訳): Sherrington-Kirkpatrickモデルに対する完全多項式近似アルゴリズム
- Abstract要約: Montanariのインクリメンタル近似メッセージパッシングアルゴリズム(FOC 2019; SIAM J. Comput., 2025)とEl Alaoui, Montanari and Sellke (AMS)のゼロ温度定式化
厳密なクエリ出力(GEG-IAMP)を備えたグループIAMPを導入する。
GEG-IAMPは、合計でN$と1/varepsilon$の近似アルゴリズムであり、閾値2021の上の有限サイズ保証である。
- 参考スコア(独自算出の注目度): 4.433169165028139
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Montanari's incremental approximate message passing (IAMP) algorithm [FOCS 2019; SIAM J. Comput., 2025] and the zero-temperature formulation of El Alaoui, Montanari and Sellke (AMS) [Ann. Probab., 2021] find a $(1-\varepsilon)$ approximation to the maximum Sherrington-Kirkpatrick (SK) energy in $C(\varepsilon)N^2$ operations for fixed accuracy, with probability tending to one as $N\to\infty$, under their respective full-support and access-model assumptions. However, it was unknown whether this approximation could be achieved with work polynomial in both $N$ and $1/\varepsilon$, together with quantitative guarantees at finite dimension. Under the same assumptions as AMS, we introduce grouped IAMP with exact Gaussian query outputs (GEG-IAMP), which is the first SK approximation algorithm with total work polynomial in $N$ and $1/\varepsilon$ and a finite-size guarantee above a dimension threshold polynomial in $1/\varepsilon$ and $\log(1/α)$. More precisely, for every $α\in(0,1/2)$, it returns a $(1-\varepsilon)$ approximation with probability at least $1-α$ whenever $N\ge \mathsf{K}\varepsilon^{-2}\log^2(e/\varepsilon)\log(\mathsf{K}/α)$, using $O(N^2/\varepsilon)$ work and $O(N^2)$ storage. GEG-IAMP replaces the Onsager correction by Reeves's coupling construction [arXiv:2508.10782] and groups Euler-Maruyama steps into $O(1/\varepsilon)$ matrix-vector products. We also prove a relative guarantee for AMS IAMP with $O(N^2\varepsilon^{-3}\log^2(e/\varepsilon))$ work but a sufficient dimension exponential in inverse accuracy. By returning a fixed configuration below its dimension threshold, GEG-IAMP also provides an asymptotic fully polynomial randomized approximation scheme (AFPRAS), with an additive error independent of dimension.
- Abstract(参考訳): Montanariのインクリメンタル近似メッセージパッシングアルゴリズム(FOCS 2019; SIAM J. Comput., 2025)とEl Alaoui, Montanari and Sellke (AMS) [Ann. Probab., 2021]のゼロ温度定式化[1-\varepsilon]は、C(\varepsilon)N^2$の最大シェリントン・キルクパトリック(SK)エネルギーに近似して、それぞれのフルサポートとアクセスモデルの仮定で確率が1N\to\infty$となる固定精度の演算を行う。
しかし、この近似が、有限次元の量的保証とともに、N$と1/\varepsilon$の作業多項式で達成できるかどうかは不明である。
AMS と同じ仮定で、Gaussian query outputs (GEG-IAMP) を持つグループ IAMP を導入し、これは総作業多項式が$N$ と $1/\varepsilon$ のSK近似アルゴリズムであり、1/\varepsilon$ と $\log(1/α)$ の次元しきい値多項式上の有限サイズ保証である。
より正確には、すべての$α\in(0,1/2)$に対して、$(1-\varepsilon)$近似を少なくとも1-α$の確率で返す:$N\ge \mathsf{K}\varepsilon^{-2}\log^2(e/\varepsilon)\log(\mathsf{K}/α)$、$O(N^2/\varepsilon)$ workと$O(N^2)$ storageを使用する。
GEG-IAMP は、リーヴスのカップリング構造 (arXiv:2508.10782) によって Onsager の補正を置き換え、オイラー・マルヤマのステップを$O(1/\varepsilon)$Matrix-vector product に分類する。
また、AMS IAMP に対して $O(N^2\varepsilon^{-3}\log^2(e/\varepsilon))$ work を相対的に保証するが、逆精度では十分次元指数的である。
GEG-IAMPは、その次元閾値以下の固定構成を返すことにより、漸近的完全多項式ランダム化近似スキーム(AFPRAS)も提供する。
関連論文リスト
- A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳(メタデータ) (2026-09-09T10:13:43Z) - Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。
我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
論文 参考訳(メタデータ) (2024-10-02T15:21:07Z) - Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs [35.22742439337603]
Proposed Primal-Dual based Regularized Accelerated Natural Policy Gradient (PDR-ANPG) algorithm using entropy and quadratic regularizers to reach this goal。
PDR-ANPGは、パラメータ化されたポリシークラスに変換互換性の近似誤差を持たせるため、最終値の$epsilon$Optimity gapを達成できる。
これは、汎用パラメータ化CMDPの最先端最終保証の大幅な改善である。
論文 参考訳(メタデータ) (2024-08-21T10:44:57Z) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。
1/varepsilonは$m2d log (1/varepsilon)$である。
以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
論文 参考訳(メタデータ) (2023-03-30T02:50:49Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication
Time [14.990725929840892]
ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。
我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
論文 参考訳(メタデータ) (2020-06-23T20:21:27Z) - Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。
次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。
Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
論文 参考訳(メタデータ) (2020-06-21T06:57:59Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。