論文の概要: Polynomial-Time Minimax Prediction for Stationary Renewal Processes
- arxiv url: http://arxiv.org/abs/2611.01430v1
- Date: Sun, 01 Nov 2026 02:12:39 GMT
- ステータス: 情報取得中
- システム内更新日: 2026-11-03 19:32:32.665116
- Title: Polynomial-Time Minimax Prediction for Stationary Renewal Processes
- Title（参考訳）: 定常更新プロセスにおける多項式時間最小値予測
- Abstract要約: 定常二元更新過程におけるミニマックス次シンボルKullback-Leiblerリスクは位数n(-1/2)を持つことが知られている
我々は、任意の未知の有限平均交叉法則に対して、この順序を達成する予測子時間予測器を与える。
- 参考スコア（独自算出の注目度）: 5.407677397417658
- License:
- Abstract: The minimax next-symbol Kullback-Leibler risk for stationary binary renewal processes is known to have order n^(-1/2). We give a polynomial-time predictor attaining this order for an arbitrary unknown finite-mean interarrival law. The construction uses a classical type-uniform renewal code. Its contribution is an exact dynamic program for censored prefix marginals, avoiding enumeration of gap histograms or binary completions. Combined with an established prediction reduction, it gives risk at most [log M_(n+1)+log(n+2)]/n, where M_N counts renewal types. Shared suffix updates reduce the total computation to O(n^3) arithmetic work and polynomial bit complexity, without tail, mixing, known-mean, or bounded-support assumptions. The statistical rate and its lower bound are prior results; the proposed advance concerns computation.
- Abstract（参考訳）: 定常二元更新過程のミニマックス次シンボルKullback-Leiblerリスクは位数n^(-1/2)を持つことが知られている。
この順序を満たす多項式時間予測器を任意の未知の有限平均交叉法則に対して与える。
この構造は古典的な一様更新コードを使用する。
その貢献は検閲された接頭辞境界の正確な動的プログラムであり、ギャップヒストグラムやバイナリ補完の列挙を避けている。
確立された予測の削減と組み合わせることで、M_N が更新型をカウントしている場合、最大 [log M_(n+1)+log(n+2)]/n のリスクが生じる。
共有接尾辞の更新により、計算総量は O(n^3) 算術的な作業と多項式ビットの複雑さに還元される。
統計的レートとその下限は事前の結果であり、提案手法は計算に関するものである。
関連論文リスト
- Pinpointing Super-Quadratic Quantum Enumeration Speedups: Exact and Certified Evaluation of the Guessing-Moment Exponent under Product-Distribution Advice [1.8224992311090216]
与えられたアドバイス分布によって誘導される量子古典的推測モーメント分離を評価するための有限サイズ手法を提案する。
本フレームワークは,シードおよびブロック暗号キー上のコールドブートリーク,テンプレートアタック後部,および合成ベルヌーイ後部に適用する。
論文 参考訳（メタデータ） (2026-09-23T14:53:56Z) - Statistical Gains from Looped Estimation under Parameter Budgets [11.857867207010981]
人工知能におけるメモリ制約は、より少ないパラメータで正確な関数近似を動機付ける。
共有パラメータを持つ1つの更新関数を繰り返し構成するループについて検討する。
我々は,そのパラメータ要求を,与えられた最悪の場合の近似精度,あるいは同等に,共通の予算下での近似精度と比較する。
論文 参考訳（メタデータ） (2026-09-22T07:14:18Z) - A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions [75.69959433669244]
オンラインスパース線形回帰(OSLR)では,予測のために1インスタンスあたり$d$あたり$k$しかアクセスできない。
提案手法では, 過去の後悔点を大幅に改善する拡張時間アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-10-31T05:02:33Z) - Time-series Random Process Complexity Ranking Using a Bound on Conditional Differential Entropy [0.8666096694354596]
Fangらによって確立された情報理論予測誤差境界に基づいて構築する。
条件付き微分エントロピー textbf$h(X_k mid X_k-1,...,X_k-m)$ は次ステップ予測誤差の行列式の関数によって上界となることを示す。
論文 参考訳（メタデータ） (2025-10-23T13:36:04Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳（メタデータ） (2022-04-20T07:14:21Z) - DASHA: Distributed Nonconvex Optimization with Communication
Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。
MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
論文 参考訳（メタデータ） (2022-02-02T20:10:40Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳（メタデータ） (2022-01-05T15:17:35Z) - Efficient improper learning for online logistic regression [68.8204255655161]
サンプル数 n の対数的後悔を持つ任意の正則アルゴリズムは、必然的に B の指数乗法定数を損なうことが知られている。
本研究では、対数的後悔を保ちながら、この指数定数を回避する効率的な不適切なアルゴリズムを設計する。
シュロゲート損失を伴う正規化経験的リスク最小化に基づく新しいアルゴリズムは、O(B log(Bn))として、オーダーO(d2)の1回あたりの時間複雑度で、後悔のスケーリングを満足させる。
論文 参考訳（メタデータ） (2020-03-18T09:16:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。