論文の概要: Support Selection Beyond Smooth DAG Exactness: Completion Geometry,Score Margins, and Selective Certificates
- arxiv url: http://arxiv.org/abs/2608.08103v1
- Date: Sat, 08 Aug 2026 12:33:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-11 19:16:36.666874
- Title: Support Selection Beyond Smooth DAG Exactness: Completion Geometry,Score Margins, and Selective Certificates
- Title（参考訳）: Smooth DAG Exactness以外のサポート選択:Completion Geometry、Score Margins、Selective Certificates
- Abstract要約: 最小サイクル完備化がDAG境界における平方自由単項イデアルを生成することを示す。
我々は孤立サイクルの正確な選択時間を導出する。
その結果,DAG実現可能性,スコアベースサポート選択,因果同定が分離された。
- 参考スコア（独自算出の注目度）: 6.269726879516811
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Smooth acyclicity constraints answer whether a weighted support is a DAG, whereas structure learning asks which support change should be made. Existing analyses establish degeneracy for particular constraint formulas but do not isolate what follows from smooth exactness itself. At a DAG boundary, we show that minimal cycle completions generate a squarefree monomial ideal containing every restricted Taylor jet of an exact representation. If the smallest completion has $q$ edges, the first possible response has order $q$ for a vector residual and $2q$ for a nonnegative scalar. Exponentially many constant-scale cyclic manifolds exhibit the same lack of ranking away from the boundary for NOTEARS and DAGMA. We derive the exact selection time for an isolated cycle. When $Ψ'(h)\asymp h^ν$, the feasibility-only time is $T_0(\varepsilon)=Θ(\varepsilon^{-(2ν+1)})$; a score margin changes the leading dynamics at scale $T_0^{-1}$ for $ν>0$, while $ν=0$ has a logarithmic boundary layer requiring $γT_0\log(1/\varepsilon)\to0$. Experiments verify this law, and a truth-free separation statistic predicts selection time on 320 official NOTEARS/DAGMA trajectories (Spearman $-0.52$ and $-0.66$, permutation $p<10^{-4}$). For finite samples, a parent-set confidence family and forced-opposite queries certify skeleton and unshielded-collider labels shared by every population optimum of a frozen score. Across 320 runs, every regret bound covers an independent oracle-score audit. None of 3,042 certified skeleton or 2,396 collider labels disagrees with the oracle-score optimum, although 4.4% and 5.5%, respectively, disagree with the generating graph. These results separate DAG feasibility, score-based support selection, and causal identification.
- Abstract（参考訳）: 滑らかな非循環性制約は、重み付けされた支持がDAGであるかどうかに答える一方、構造学習はどの支援を行うべきかを問う。
既存の分析は、特定の制約公式の縮退性を確立するが、スムーズな正確性そのものから何に従うかは分離しない。
DAG境界において、最小サイクル完備化は、正確な表現のすべての制限されたテイラージェットを含む平方自由単項イデアルを生成することを示す。
最小の完備化が$q$エッジを持つ場合、最初の応答はベクトル残基に対して$q$、非負のスカラーに対して$2q$である。
指数的に多くの定数スケールの巡回多様体は、NOTEARS と DAGMA の境界から外されるようなランク付けの欠如を示す。
我々は孤立サイクルの正確な選択時間を導出する。
a score margin change the leading dynamics at scale $T_0^{-1}$ for $ν>0$, $ν=0$ have a logarithmic boundary layer requires $γT_0\log(1/\varepsilon)\to0$。
実験によってこの法則が検証され、真理のない分離統計は320の公式NOTEARS/DAGMA軌道上の選択時間を予測する(Spearman $-0.52$と$-0.66$, permutation $p<10^{-4}$)。
有限標本に対して、親セット信頼ファミリーと強制オポポジトクエリは、凍結スコアの全ての個体群最適化によって共有される骨格と非シールドコライダーラベルを認証する。
320回の実行では、すべての後悔のバウンドが独立したオラクルスコア監査をカバーしている。
3,042個の認証された骨格または2,396個のコライダーラベルは、それぞれ4.4%と5.5%のオプティマムに一致しないが、それぞれ生成グラフに一致しない。
これらの結果から,DAG実現可能性,スコアベースサポート選択,因果同定を分離した。
関連論文リスト
- 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) - From Approachability Residuals to Anytime-Valid Evidence: The Online Convex Geometry of Testing by Betting [0.1624454100511275]
ギャンブリングベースのシーケンシャルテストとブラックウェルのアプローチ性は、支持関数による比例還元によってリンクされる。
正確な経路単位は$$dist(bar r_T,S) =frac1Tsum_t=1Tq_t+fracReg_TTである。
論文 参考訳（メタデータ） (2026-08-10T11:23:30Z) - Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。
多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
論文 参考訳（メタデータ） (2026-08-04T23:38:54Z) - ForgettingOT: Certified Speculative Batching from Sinkhorn's Projective Forgetting [0.0]
固定点ヤコビアン$J_tstar=QP=Pstar P$ の固有モードが厳密な補正テールを制御することを示す。
ForgettingOTは、この非線形ペロン-フロベニウスの事実をシンクホーン問題のストリームの認定執行者に変える。
論文 参考訳（メタデータ） (2026-07-27T17:59:36Z) - Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。
失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
論文 参考訳（メタデータ） (2026-07-22T07:42:19Z) - Online Convex Optimization with Sublinear Noisy Probes [6.998574163422056]
オンライン凸最適化(OCO)を凸集合として$Ksubseteq mathbb Rd$で検討する。
我々は最近の2つの作業の行を一般化する統一された探索モデルを導入する: 専門家設定におけるサブ線形ベストエキスパートクエリと、OCOの各ラウンドで利用できるペアワイズフィードバックである。
本研究の主目的は, サブリニアでノイズの多いプローブ予算であっても, OCO体制の完全なフィードバックにおける最悪の後悔を確実に改善できることである。
論文 参考訳（メタデータ） (2026-06-12T17:05:08Z) - Optimizing Explicit Unit-Distance Lower-Bound Certificates [0.0]
2026年のエルツの単位距離予想とサウィンの量的洗練の反証は、固定正の$varepsilon$に対して、n$平面点の間の単位距離の最大値$u(n)$が$n1+varepsilon$を超えることを示す。
本稿では、Sawinのパラメータ選択を非線形整数最適化問題として扱い、素集合$T$と$S_Q$を含む証明書のためのオープンソースのPythonパイプラインを開発する。
論文 参考訳（メタデータ） (2026-06-02T10:05:23Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
実数値関数クラスが一様収束と学習可能性を示す最適尺度について検討する。
本研究の主な成果は,PAC学習の基本定理のスケール敏感な一般化である。
また、定量的サンプルの複雑さと評価可能性に関するオープンな質問をいくつか取り上げる。
論文 参考訳（メタデータ） (2026-05-13T15:41:30Z) - Graph-SND: Sparse Aggregation for Behavioral Diversity in Multi-Agent Reinforcement Learning [0.0]
グラフSNDを導入し、任意のグラフのエッジ上の重み付き平均をG$で置き換える。
固定されたスパースグラフに対して、拡大器のフォワード・インデックス歪み境界と低ランク距離構造の下でのスペクトル改善を証明した。
ランダム $d$-正則グラフに対して、非条件確率 $widetildemathcalO(D_max/sqrtn)$bound を証明する。
VMASでは、リカバリ、不偏性、濃度、壁時計のスケーリングを検証する。
論文 参考訳（メタデータ） (2026-05-06T15:18:42Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Making Progress Based on False Discoveries [14.505867475659274]
本稿では,凸最適化の枠組みにおける適応データ解析の課題について考察する。
一般アナリスト(必ずしも勾配降下ではない)に対して、Omega (1/epsilon3)$サンプルが必要であることを示す。
第二に、オラクル上の特定の仮定の下では、勾配降下$tilde Omega (1/epsilon2.5)$サンプルが必要であることを示す。
論文 参考訳（メタデータ） (2022-04-19T11:17:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。