論文の概要: The Extremum Stack is a Minimal Sufficient Statistic for Rate-Independent Functionals: A Kolmogorov Complexity Characterisation

• arxiv url: http://arxiv.org/abs/2605.18885v1
• Date: Sat, 16 May 2026 19:21:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-20 15:03:08.846642
• Title: The Extremum Stack is a Minimal Sufficient Statistic for Rate-Independent Functionals: A Kolmogorov Complexity Characterisation
• Title（参考訳）: 極値スタックは速度非依存関数の最小統計量である:コルモゴロフ複素性特徴化
• Authors: Piotr Frydrych,
• Abstract要約: 離散列の極限スタックは、計算可能で因果的、レート非依存な函数のクラスに対する最小統計量であることを示す。 結果から示唆されるスタックベースの圧縮アルゴリズムは、コルモゴロフの最適性を保証する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that the extremum stack of a discrete sequence is a minimal sufficient statistic for the class of all computable, causal, rate-independent functionals, in the sense of Kolmogorov complexity. Specifically, we establish K(Pi_n) - O(1) <= K_R(u_{0:n}) <= K(Pi_n) + O(1), where K_R(u_{0:n}) is the length of the shortest program answering every query in the class R, and the O(1) overhead is independent of both the sequence length n and the stack depth k. Sufficiency follows from the classical wiping property of the Preisach hysteresis operator. Minimality is established via a finite indicator family whose rate-independence is verified explicitly. Any compression of a hysteresis-driven stream that preserves the full class R must therefore retain at least K(Pi_n) - O(1) bits; the stack-based compression algorithm implied by the result carries a Kolmogorov optimality guarantee that none of the standard time-series compression methods provide.
• Abstract（参考訳）: 離散列の極大スタックは、コルモゴロフ複雑性という意味で、計算可能で因果的、レート非依存な函数のクラスに対して、最小の統計量であることを示す。 具体的には、K(Pi_n) - O(1) <= K_R(u_{0:n}) <= K(Pi_n) + O(1) を確立する。 プレサッハ・ヒステレシス作用素の古典的なワイピング特性から十分従う。 最小性は、速度依存性が明示的に証明された有限指標族によって確立される。 したがって、全クラス R を保持するヒステリシス駆動ストリームの圧縮は、少なくとも K(Pi_n) - O(1) ビットを保持する必要がある。

関連論文リスト

• Layer-wise Lipschitz-Product Control for Deep Kolmogorov--Arnold Network Representations of Compositionally Structured Functions [51.56484100374058]
  リプシッツ積は入力次元 n の独立な一次領域感受性境界を満たす。 実験では、いくつかの構成的構造化関数に対して P(KAN)=1.0 を確認する。
  論文  参考訳（メタデータ） (2026-04-29T08:55:49Z)
• Pack only the essentials: Adaptive dictionary learning for kernel ridge regression [69.32538992633842]
  カーネルリッジ回帰 (KRR) の大きな限界の1つは、n 個のサンプルに対するカーネル行列 K_n の保存と操作が O(n2) 空間を必要とすることである。 INK-Estimateはデータセットを漸進的に処理し、RSS、有効次元、Nystrom近似をオンザフライで更新するアルゴリズムである。 本稿では,INK-Estimateをベースとした非正規化RSSを用いた新しいアルゴリズムであるSQUEAKを紹介する。
  論文  参考訳（メタデータ） (2026-04-24T09:22:09Z)
• Dynamic Algorithm for Explainable k-medians Clustering under lp Norm [11.05906005268085]
  各有限 p >= 1 に対して lp ノルムの下で説明可能な k-メディアンに対する最初のアルゴリズムを示す。 我々のアルゴリズムは任意の p >= 1 に対して最適な k-メディアンに対する O(p(log k)1 + 1/p - 1/p2) 近似を達成する。 このアルゴリズムは、挿入と削除のシーケンスの下で説明可能なクラスタリングを維持しており、償却更新時間 O(d log3 k) と O(log k) のリコースがある。
  論文  参考訳（メタデータ） (2025-12-01T00:01:47Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates [0.0]
  提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。 非テンション依存データ設定の下で, 各種手法の収束点を求める。
  論文  参考訳（メタデータ） (2022-01-05T15:17:35Z)
• A PAC-Bayesian Analysis of Distance-Based Classifiers: Why Nearest-Neighbour works! [12.317405551932195]
  K-nearest-neighbour分類器(K-NN)の一般化誤差に対するPAC-Bayesian境界 我々は、カーネル展開における係数に関する事前測度と、カーネル空間における重みベクトルに関する誘導測度との関係を確立する。
  論文  参考訳（メタデータ） (2021-09-28T17:35:57Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Subgroup-based Rank-1 Lattice Quasi-Monte Carlo [51.877197074344586]
  グループ理論に基づく単純な閉形式ランク1格子構築法を提案する。 本手法は,ベンチマーク統合テスト問題とカーネル近似問題において,優れた近似性能を実現する。
  論文  参考訳（メタデータ） (2020-10-29T03:42:30Z)
• Robust Linear Regression: Optimal Rates in Polynomial Time [11.646151402884215]
  複数の線形モデルを学習するための頑健で計算効率の良い推定器を得る。 確率変数の独立性の緩和に役立つ解析条件を同定する。 我々の中心となる技術的貢献は、"sum-of-squares"フレームワークにおけるランダム変数の独立性をアルゴリズム的に活用することである。
  論文  参考訳（メタデータ） (2020-06-29T17:22:16Z)

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

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