論文の概要: Sharp Minimax Regret for Infinite-Memory Logistic Prediction
- arxiv url: http://arxiv.org/abs/2608.26515v1
- Date: Thu, 27 Aug 2026 01:31:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-28 16:30:58.211831
- Title: Sharp Minimax Regret for Infinite-Memory Logistic Prediction
- Title（参考訳）: Infinite-Memory Logistic PredictionのためのSharp Minimax Regret
- Abstract要約: Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。
すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。
指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
- 参考スコア（独自算出の注目度）: 55.29259818039367
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online prediction for a specific finite-alphabet, exogenously driven source with infinite input memory. Independent Rademacher inputs $(U_t)$ are observed sequentially, and the next binary mark has logit $\sum_{j=1}^{t}θ_jU_{t+1-j}$, where $\abs{θ_j}\leq r_j$ and $\sum_jr_j\leq B$. Regret is expected cumulative excess log loss. Lag $j$ can affect prediction by scale $r_j$ and enters only $n_{T,j}=T-j+1$ prediction rounds, leading to the lag-resolved spectrum $Γ_T(r)=\sum_{j=1}^{T}\log\!\left(1+n_{T,j}r_j^2\right)$. For every summable envelope, a localized Bayesian mixture proves $\cR_T(r)\leq CΓ_T(r)$. For exponential and polynomial envelopes, under the stated finite-sample dimension condition, a Toeplitz-design converse proves $\cR_T(r)\geq cΓ_T(r)$, with constants allowed to depend on the fixed decay parameters and the logit bound. Thus $Γ_T(r)$ is the minimax cumulative-regret scale for this source class in these canonical regimes, giving $Θ(α^{-1}\log^2T)$ for $r_j=Ae^{-αj}$ and $Θ(T^{1/(2s)})$ for $r_j=Aj^{-s}$, $s>1$. The converse is specific to the exogenous lagged model and is not a profile-only theorem for arbitrary stationary infinite-memory sources. Retaining only the most recent $h$ inputs costs order $\sum_{j>h}n_{T,j}θ_j^2$, yet the same worst-case truncation profile can correspond to polynomially different regret. A scaled online Newton predictor attains the spectrum upper bound.
- Abstract（参考訳）: 本研究では,入力メモリが無限となる特定の有限アルファベット,異種駆動音源のオンライン予測について検討する。
独立な Rademacher 入力 $(U_t)$ は順次観測され、次のバイナリマークは logit $\sum_{j=1}^{t}θ_jU_{t+1-j}$ であり、$\abs{θ_j}\leq r_j$ および $\sum_jr_j\leq B$ である。
Regretは累積過剰なログ損失を期待する。
Lag $j$はスケール$r_j$の予測に影響を与え、$n_{T,j}=T-j+1$の予測ラウンドしか入らないため、ラグ分解スペクトルである$n_T(r)=\sum_{j=1}^{T}\log\!
\left(1+n_{T,j}r_j^2\right)$
任意の要約エンベロープに対して、局所化されたベイズ混合は$\cR_T(r)\leq C\_T(r)$を証明している。
指数的および多項式的エンベロープに対して、有限サンプル次元条件の下では、トエプリッツ・デサインの逆は$\cR_T(r)\geq cn_T(r)$であり、定数は固定された減衰パラメータとロジット境界に依存することが許される。
したがって、99(α^{-1}\log^2T)$ for $r_j=Ae^{-αj}$ and $(T^{1/(2s)})$ for $r_j=Aj^{-s}$, $s>1$である。
逆は外生ラッジモデルに特有であり、任意の静止無限メモリ源に対するプロファイルのみの定理ではない。
最新の$h$入力だけを保持すると、$\sum_{j>h}n_{T,j}θ_j^2$となるが、同じ最悪ケースのトランケーションプロファイルは多項式的に異なる後悔に対応することができる。
スケールしたオンラインニュートン予測器は、スペクトル上界を得る。
関連論文リスト
- Sparse Quantum State Preparation with Sublinear T-Count [5.929956715430168]
$$n$-qubit $s$-sparse状態は、$widetildeO(mins, n3/4sqrts+sqrtslog (1/)+log (1/)$ $T$ gatesを使ってエラーを発生させることができる。
0le$と2le sle 2n/2$に対して、スパース状態の準備には$(mins,sqrtns)$$Tが必要である。
論文 参考訳（メタデータ） (2026-08-01T03:33:19Z) - Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling: Tight Upper and Lower Bounds [7.787109481104569]
ランダムシャッフルに基づくサブサンプリングによるDP-SGDのトレードオフ関数の厳密な解析を導出する。
Berry-Esseenの定理によって導かれる我々の具体的な境界は、証明フレームワーク内の定数要素に密着している。
論文 参考訳（メタデータ） (2026-05-07T13:35:43Z) - Sparse Linear Regression is Easy on Random Supports [20.128442161507582]
我々は mathbbRN times d$ で設計行列 $X を入力し、 mathbbRN times d$ で測定やラベル $y を入力します。
w*$がランダムに選択されると、およそ$N = O(klog d/epsilon)$サンプルで予測エラー$epsilon$が得られる。
論文 参考訳（メタデータ） (2025-11-09T03:48:21Z) - Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳（メタデータ） (2023-09-20T21:41:59Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。
任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
論文 参考訳（メタデータ） (2022-01-24T17:33:19Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。
疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文 参考訳（メタデータ） (2020-06-17T09:21:00Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。