論文の概要: Sharp Degree Bounds for Putinar Certificates in Terms of the Positivity Margin via Analytic Sums of Squares
- arxiv url: http://arxiv.org/abs/2610.26976v2
- Date: Thu, 22 Oct 2026 17:36:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-24 02:08:44.046932
- Title: Sharp Degree Bounds for Putinar Certificates in Terms of the Positivity Margin via Analytic Sums of Squares
- Title（参考訳）: 正方形解析による正弦率マージンにおけるプチナー証明書のシャープ深さ境界
- Abstract要約: Putinar sum-of-squares証明のシャープな次数境界を、肯定的なマージンの$$で定めます。
不等式生成器の数が最適次数に影響を及ぼすことを示す。
また,鳥居に三角SOS証明書の急激な等級境界を定めている。
- 参考スコア（独自算出の注目度）: 3.2797526928683287
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We establish sharp degree bounds for Putinar sum-of-squares (SOS) certificates in terms of the positivity margin $δ$. For any fixed Archimedean quadratic module with prescribed generators and any fixed degree bound on the objective, normalized polynomial objectives admit a uniform certificate-degree upper bound of $O(δ^{-1/2}\log^2(2/δ))$. The bound is sharp: we construct a matching lower-bound example in three variables. We further show that the number of inequality generators affects the optimal degree bound. For quadratic modules with at most two inequality generators, the bound improves to $O(δ^{-1/2}\log(2/δ))$, which is also sharp. This improvement is obtained by directly converting two-generator Stengle refutations into certificates for the original quadratic module. We also establish sharp degree bounds for trigonometric SOS certificates on tori. In particular, for the full torus without additional constraints, the optimal worst-case order improves to $δ^{-1/4}$, whereas additional equality constraints can lead the order to $δ^{-1/2}\log(2/δ)$. These results also yield sharp worst-case convergence rates for the Lasserre hierarchy.
- Abstract（参考訳）: プーチナー和(SOS)証明の鋭い次数境界を正のマージンであるδ$で定めている。
所定の生成元と目的に有界な任意の固定アルキメデス二次加群に対して、正規化多項式の目的は、一様証明次数$O(δ^{-1/2}\log^2(2/δ))$を許容する。
境界はシャープで、3つの変数で一致する下界の例を構築します。
さらに、不等式生成子の数が最適次数境界に影響を与えることを示す。
2つの不等式生成元を持つ二次加群に対して、境界は$O(δ^{-1/2}\log(2/δ))$に改善され、これも鋭い。
この改善は、2世代Stengleの難燃剤を直接元の二次モジュールの証明書に変換することで得られる。
また,鳥居に三角SOS証明書の急激な等級境界を定めている。
特に、追加の制約を伴わないフルトーラスの場合、最適の最悪ケース順序は$δ^{-1/4}$に改善されるが、追加の等式制約は$δ^{-1/2}\log(2/δ)$に順序を導くことができる。
これらの結果は、ラッサール階層に対する急激な最悪の収束率をもたらす。
関連論文リスト
- Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds [61.41272490044518]
REINFORCEの分散還元バージョンは、$O(-3)$サンプルの複雑さを改善して$$-stationary点を求める。
本稿では, 従来の重みの分散を仮定することなく, 同一レートを達成できる, 防御重要度サンプリングに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-10-02T11:43:52Z) - Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise [66.13091490213743]
グラディエントクリッピングはトレーニングを安定させるために広く用いられているが、平均的なSGDの統計的精度を改善する必要はない。
有限条件の$p$-th モーメント,$pge2$ の条件下で, クリッピングおよび非クリッピングのPolyak-Ruppert平均 SGD の比較を導出した。
我々の主な結果は、$p>2$の場合、ガウス項が未開偏差境界を独占する明確な精度と信頼条件を与える。
論文 参考訳（メタデータ） (2026-09-26T21:47:14Z) - On the SoS Certifiability of Log-Concave Distributions [51.56484100374058]
圏 $(Cm)m|v|m - mathbbE_Xsim Plangle X,vranglem$ は、すべての偶数 mge2$ に対する平方の和であり、$C>0$ は普遍定数である。
これにより、コタリとシュタインハルト(arXiv:1711.07465)の定理におけるポアンカレ定数への依存を排除し、対数凹面分布の最適モーメント境界を回復する。
論文 参考訳（メタデータ） (2026-09-24T16:48:02Z) - Stability-Constrained Approximation in Spline KANs: Exact Layer Balancing and Budget-Compatible Saturation [51.56484100374058]
我々は、ハードレイヤーワイドリプシッツ予算の下で近似を研究する。
構成条件下では、対応するレイヤエラーをキャンセルする必要はないことを示す。
クラスのすべての作用素に対して、安定した深さ-$L$タワーが存在し、累積誤差の定数分を実現できる。
論文 参考訳（メタデータ） (2026-09-14T20:17:04Z) - Unbounded degree overhead for Alice-conditioned quantum Bell certificates [0.0]
アリスの測度に関する質問の1つだけを含むために、各2乗の総和項を必要とすると、無拘束の認証コストが課せられる。
Alice-conditioned NPA 階層の有限レベルには標準レベル2のベル証明書が存在しないことを証明した。
論文 参考訳（メタデータ） (2026-09-09T13:38:25Z) - Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning [0.9558392439655014]
定数対応比較プロトコルを導入し、MPPを通信するための明示的な有限下位証明書を導出する。
共通閉形式エンベロープは有限フロンティアで発行された係数を0.015$に改善する。
論文 参考訳（メタデータ） (2026-08-07T19:28:58Z) - AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
すべての許容関数に対して下界が成り立ち、より強い境界を与える凸緩和から従うことを示す。
理論は各エージェントを検証し、反例を検索し、報告されたすべての境界はインターバルにおける明示的な二重実現可能な点によって認証される。
論文 参考訳（メタデータ） (2026-06-30T06:10:25Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling [6.908972852063454]
相関クラスタリング(CC)は基本的な教師なし学習プリミティブである。
LPベースの保証を維持するためには,どの程度のエッジ情報が必要であるかを検討する。
ヤオのミニマックス原理を通して、擬距離構造がなければ、任意のアルゴリズムが$o(n)$一様ランダムエッジを観測すると近似比が生じることを示す。
論文 参考訳（メタデータ） (2026-02-14T09:12:15Z) - Kitaev model in regular hyperbolic tilings [0.0]
正規双曲型三価タイリングの北エフモデルについて検討する。
我々は、正確な対角化を通して位相図を計算し、実効ハミルトニアンに対する解析式を導出する。
論文 参考訳（メタデータ） (2025-06-22T10:44:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。