論文の概要: Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms

• arxiv url: http://arxiv.org/abs/2608.09870v1
• Date: Mon, 10 Aug 2026 17:25:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-11 19:16:37.396696
• Title: Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms
• Title（参考訳）: 一様安定アルゴリズムにおける対数自由モーメントと一般化境界
• Abstract要約: すべての$pge2$, $$ left| sum_i=1n g_i(Z)right|_p le 16+Msqrt2 に対して証明する。 これにより、前の境界から$log n$因子を取り除き、ブーケ、クロチコフ、ジヴォトフスキーの下限を、その構成によってカバーされる範囲の普遍定数に一致させる。
• 参考スコア（独自算出の注目度）: 2.8192865995731897
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional factor $\log n$, and they asked whether this factor can be removed. We answer this upper-bound question affirmatively. More specifically, let $Z=(Z_1,\ldots,Z_n)$ have independent coordinates and let $g_i(Z)$ satisfy $$ \mathbb E[g_i(Z)\mid Z_{-i}]=0, \qquad \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \qquad \forall i = \overline{1, n} $$ while changing any coordinate $Z_j$, $j\neq i$, changes $g_i$ by at most $β$ and $Z_{-i}$ denotes all coordinates except $Z_i$. We prove that, for every $p\ge2$, $$ \left\| \sum_{i=1}^n g_i(Z)\right\|_p \le 16pnβ+M\sqrt{2pn}. $$ This removes the $\log n$ factor from the previous bound and matches the lower bound of Bousquet, Klochkov, and Zhivotovskiy up to universal constants in the range covered by their construction. Our proof first establishes the required estimate on the Rademacher cube, then transfers it to arbitrary product distributions by a two-copy randomization argument.
• Abstract（参考訳）: 均一安定性は学習アルゴリズムの一般化誤差を制御する古典的なツールである。 Bousquet, Klochkov, Zhivotovskiy (2020) は、独立確率変数の弱い相互作用関数の和に対して、問題を瞬間不等式に還元できることを示した。 彼らの境界には追加の因子$\log n$が含まれており、彼らはこの因子を除去できるかどうかを尋ねた。 私たちはこの上界の質問に肯定的に答える。 具体的には、$Z=(Z_1,\ldots,Z_n)$ は独立座標を持ち、$g_i(Z)$ は$$$ \mathbb E[g_i(Z)\mid Z_{-i}]=0, \qquad \left| \mathbb E[g_i(Z)\mid Z_i]\right|\le M, \qquad \forall i = \overline{1, n} $ は$Z_j$, $j\neq i$, change $g_i$ は$β$, $Z_{-i}$ は$Z_i$ 以外のすべての座標を表す。 すべての$p\ge2$, $$ \left\| \sum_{i=1}^n g_i(Z)\right\|_p \le 16pnβ+M\sqrt{2pn} に対して証明する。 $$ これは、前の境界から$\log n$ factorを取り除き、ブーケ、クロチコフ、ジヴォトフスキーの下限を、その構成によってカバーされる範囲の普遍定数に一致させる。 我々の証明はまず、ラデマッハ立方体上で必要な見積もりを定め、それから2コピーのランダム化引数で任意の積分布に転送する。

関連論文リスト

• Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions [5.603202398374589]
  ポテンシャルは$$-strongly convexと$L$-smoothであり、原点に関する半径$-1/2$の球に未知のモードがある。 Nstar_textTV=!left(log(1+)+ frac2right), ] $:=frac L$は条件数である。
  論文  参考訳（メタデータ） (2026-09-11T08:44:06Z)
• Simultaneous Pointwise Majorization for Mixed Tail Processes with Applications in Gaussian Chaos and Ergodic Diffusions [15.386375612838371]
  古典的な連鎖は、単一の最悪のケースバウンドを通じてインデックス化されたプロセスを制御する。 バナッハ評価過程に対する最初の同時点分極理論を考案する。
  論文  参考訳（メタデータ） (2026-09-01T17:42:38Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Exact Coset Sampling for Quantum Lattice Algorithms [9.910562011343009]
  複雑なガウス窓を持つ最近のウィンドウ付きQFT格子アルゴリズムのステップ9において、競合する「ドメイン拡張」を簡易に置き換える。 我々の新しいサブルーチンは、未知のオフセットを正確にキャンセルするペアシフト差分によってドメイン拡張を置き換える。
  論文  参考訳（メタデータ） (2025-09-15T18:10:28Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。 A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。 A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
  論文  参考訳（メタデータ） (2025-09-15T14:26:11Z)
• Decomposition of RSA modulus applying even order elliptic curves [0.0]
  効率的な整数分解アルゴリズムはRSA暗号スキームのすべての変種をゼロにする。 滑らか性に対する一般化されたアプローチの自然な拡張と2ドル進点順序の分離が組み合わさって、ファクタリングアルゴリズムを提案することを実証する。
  論文  参考訳（メタデータ） (2025-03-02T16:09:07Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  我々は、$rho$が$mtext-d$集合の近くに集中しているとき、これをノイズのあるデータを持つ多様体学習問題と解釈できることを示した。 Monge-Kantorovich $p$-cost $mathbbW_pp(rho, nu)$を介して$rho$を近似する際の$nu$のパフォーマンスを定量化し、$mathrmsupp nu$を$f : mathbbRmでカバーできるようにすることで複雑さを制限します。
  論文  参考訳（メタデータ） (2024-09-25T01:30:16Z)
• Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms [0.4527270266697462]
  積として$Z$を表現する方法を示す: Z=Z(lambda)tilde Z(lambda)$ ここで乗法補正である$tilde Z(lambda)$はノードに依存しない確率分布に対する期待値である。 また,画像デノイズ化問題に対する本手法の適用性についても論じる。
  論文  参考訳（メタデータ） (2023-01-25T00:50:28Z)
• 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)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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