論文の概要: The Dimension of Nonterminating Resampling Computations

• arxiv url: http://arxiv.org/abs/2607.17469v1
• Date: Mon, 20 Jul 2026 01:54:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-21 18:48:37.47599
• Title: The Dimension of Nonterminating Resampling Computations
• Title（参考訳）: 非終端再サンプリング計算の次元
• Abstract要約: ランダム化されたアルゴリズムは、例外的にランダムなテープが永久に動作するとしても、ほぼ確実に終了する。 本稿では、生存尾、そのようなテープのコルモゴロフ複雑性、およびそれらすべてのハウスドルフ次元について研究する。
• 参考スコア（独自算出の注目度）: 5.082462420126421
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A randomized algorithm may terminate almost surely even though exceptional random tapes make it run forever. This paper studies the survival tail, the Kolmogorov complexity of one such tape, and the Hausdorff dimension of all of them. For each $s>0$ at which the powered repair matrices commute, the main theorem bounds $\sum_wP[w]^s$ over surviving prefixes $w$, uniformly over deterministic nonanticipating selectors. The case $s=1$ controls termination; the full family gives weak-source and dimension bounds. The source powers contain information absent even from the ordinary repair kernel and the complete stopping-time law. Under one common finite tape source, two overlapping disagreement-repair rules on a four-vertex path have the same ordinary kernels and the same stopping-time law for every selector, yet their nontermination dimensions can be arbitrarily close to zero and one. At one common source-power level, the same dominated tape source makes one rule run forever but gives the other an exponential stopping tail. The separation is caused by action labels that produce the same state transition and are therefore invisible at power one. For bounded-dependence $k$-SAT, conditional block min-entropy above the trace-growth threshold gives exponential termination, and the effective dimension of an individual infinite run is bounded by the trace growth induced by the clauses repaired infinitely often. Tree formulas asymptotically attain the maximum-degree dimension and global source bounds, while clique formulas attain the graph-specific one-step threshold in the stated regime. An exact backward likelihood identity complements these setwise results with tail and coding bounds for each run.
• Abstract（参考訳）: ランダム化されたアルゴリズムは、例外的にランダムなテープが永久に動作するとしても、ほぼ確実に終了する。 本稿では、生存尾、そのようなテープのコルモゴロフ複雑性、およびそれらすべてのハウスドルフ次元について研究する。 動力的補修行列が可換である$s>0$ に対して、主定理は、継続する接頭辞の$w$に対して$\sum_wP[w]^s$ を、決定論的非予想セレクタに対して一様に束縛する。 ケース $s=1$ は終了を制御し、フルファミリーはソースと次元の境界を弱める。 ソースパワーは、通常の修理カーネルや完全な停止時間法則から外れた情報を含む。 1つの共通有限テープ源の下では、4頂点パス上の2つの重なり合う不一致再ペア規則は、全てのセレクタに対して同じ通常のカーネルと同じ停止時間法則を持つが、それらの非終端次元は、任意に0と1に近づくことができる。 1つの共通のソースパワーレベルでは、同じ支配的なテープソースが1つのルールを永久に実行させるが、もう1つのルールは指数関数的に停止する。 この分離は、同じ状態遷移を発生させるアクションラベルによって引き起こされるため、パワー1では見えない。 有界依存$k$-SATの場合、トレース成長しきい値を超える条件付きブロック min-エントロピーは指数的終了を与え、個々の無限ランの有効次元は無限に修復された節によって誘導されるトレース成長によって境界づけられる。 木式は漸近的に最大次元と大域的なソース境界に達し、クリッド式はグラフ固有の1段階のしきい値に達する。 正確な後向き確率の恒等式は、各ランに対するテールと符号化バウンダリでこれらのセットワイズ結果を補完する。

関連論文リスト

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails [47.36630149538994]
  等方的準ガウス測度の場合、ベンチマークサンプルサイズは1+w(A)2$であり、$w(A)$は正規化降下円錐のガウス幅である。 ここで定式化された一般的な問題に対して、明示的で体系的な否定的な答えを与える:提案された法則は、その全次元自由で任意の集合形式で失敗する。 等方性の下では、アフィン次元倍の2乗半径で支配される分布のないフォールバックがこの族に鋭い。
  論文  参考訳（メタデータ） (2026-09-03T08:05:05Z)
• Uniform Statistical Convergence of Empirical Sinkhorn Potentials with Exponential and Polynomial Dependence on the Regularization Parameter [3.6552781109515853]
  本研究では,一様損失下でのエントロピー最適輸送電位の実験的シンクホーン推定器について検討した。 固定正規化パラメータ $varepsilon>0$ に対して、漸近的でない統計レート $n-1/2$ を確立する。 鍵となる要件は、シンクホーン写像の残留安定度推定である。
  論文  参考訳（メタデータ） (2026-08-29T08:59:00Z)
• Discretization and Statistical Consistency of Functional Flow Matching [0.0]
  有限ランク再構成の強い一貫した列に対して、有限条件速度目標の強い$L2$収束を証明した。 学習フローに対して、集団重ね合わせ経路に直接結合すると、終端ワッサーシュタイン境界が得られる。
  論文  参考訳（メタデータ） (2026-08-05T07:05:47Z)
• The Kikuchi Hierarchy is Sharp for $k$XOR [46.26532142699448]
  菊池階層の正規化された変種は、対数損失のない鋭い予想されたトレードオフを、全てのアーティ$kge3$で達成することを示す。 また、同じモデルで一致した下界を証明し、推論と難解な上界はより一般的な植林法や述語に遷移する。
  論文  参考訳（メタデータ） (2026-07-31T17:54:11Z)
• Maximal Classicalization of Finite-Group Quantum Reference-Frame Noise [0.0]
  グループ値のミスアライメントを持つ有限量子参照トークンは、ランダムなユニタリチャネルを誘導する。 以下の条件が有限群 G のユニタリ表現 U に等しいことを証明している。
  論文  参考訳（メタデータ） (2026-07-14T17:07:57Z)
• Optimization Geometrodynamics: Variational Reduction and Interaction Curvature [0.0]
  我々は、この隠れ行列式プッシュフォワードの変分理論として、測地力学を発展させる。 アフィン事前還元の場合、誘導的相互作用曲率(英語版)は負半有限作用素 $-G*H-1G$ である。 閉全測地線ファイバーを持つ大域的解析バンドルと、特異な解析的近接制御器部とを証明した。
  論文  参考訳（メタデータ） (2026-07-07T18:42:00Z)
• Sharper Guarantees for Misspecified Kernelized Bandit Optimization [34.863425530383545]
  大規模なカーネルでは、不特定値の増幅は対数的あるいは多対数的成長に還元できることを示す。 オフライン設定では、不特定項がスペクトルルベーグ定数によって支配される高確率単純回帰境界を最初に証明する。 オンライン設定では、ドメイン分割アルゴリズムを変更して、緩やかな局所化された固有デカイ仮定の下で、$widetildemathcal O(sqrt_n n+nvarepsilon)$の累積後悔境界を証明する。
  論文  参考訳（メタデータ） (2026-05-07T10:12:56Z)
• Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression [65.82017723631897]
  自己正規化マルティンガレのスケール不変上界が可能であることを示す。 通常の正規化ペナルティを含まない自己正規化濃度不等式を導出する。
  論文  参考訳（メタデータ） (2026-05-02T22:39:00Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry [0.0]
  我々は、非時間アルゴリズムが任意の定数でランダム割当比$r/q$を超えることを、Hstadの定理から直接還元することで証明する。 この閾値は、デコードされた量子干渉法を規定する半円法則の$ell/mから0$制限と一致する。
  論文  参考訳（メタデータ） (2026-03-04T19:26:26Z)
• Finite time path field theory and a new type of universal quantum spin chain quench behavior [0.0]
  急激なクエンチと急激なクエンチの差は,摂動の非定常スイッチングが時間とともに指数関数的に消えることを示す。 また、類似の普遍的行動は、障害のクエンチ、そして究極的には大域的行動に存在することを示す。
  論文  参考訳（メタデータ） (2025-06-20T18:08:30Z)
• The Cost of Consistency: Submodular Maximization with Constant Recourse [30.724711970113777]
  特に,アルゴリズムが1ステップあたりの更新回数を最大で一定にした場合に達成可能な,最も有望な近似比を求める。 我々は、一般的な部分モジュラ函数に対して$tfrac23$の厳密な情報理論境界と、カバレッジ関数に対して$tfrac34$の改良された(かつ厳密な)境界を示す。
  論文  参考訳（メタデータ） (2024-12-03T15:06:07Z)
• Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition [29.809415829907525]
  本稿では,逆制約を伴う分散オンライン凸最適化について考察する。 エージェントはネットワークの後悔と累積的制約違反を最小限にするために協力する。 我々の知る限り、この論文は、(分散)オンライン凸最適化における(ネットワーク)累積制約違反境界を敵制約付きで達成した最初のものである。
  論文  参考訳（メタデータ） (2023-05-31T19:39:15Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Asymptotics of Entropy-Regularized Optimal Transport via Chaos Decomposition [1.7188280334580195]
  この論文は、離散的なシュル「オーディンガー橋」の性質を、N$が無限大の傾向にあるとして論じる。 最初の2つのエラー項は、それぞれ$N-1/2$と$N-1$を導出する。 1階と2階のカオスに対応するカーネルは、シンクホーンアルゴリズムの自然な解釈を持つマルコフ作用素によって与えられる。
  論文  参考訳（メタデータ） (2020-11-17T21:55:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。