論文の概要: The Sharp Tail of Uniform Stability

• arxiv url: http://arxiv.org/abs/2608.24098v1
• Date: Tue, 25 Aug 2026 05:53:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-26 14:09:34.824355
• Title: The Sharp Tail of Uniform Stability
• Title（参考訳）: 一様安定性のシャープテール
• Abstract要約: 均一な安定性は、あるトレーニング例がテストポイントでの損失をどの程度変えられるかを制御する。 新しい対数自由な上界は、$[0,L]$の損失を持つ$$一様安定なアルゴリズムが、最大$O left(log(1/) +Lsqrtfraclog (1/)nright)$の一般化ギャップを持つことを示している。
• 参考スコア（独自算出の注目度）: 1.14219428942199
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Uniform stability controls how much one training example can change the loss at any test point. A new logarithmic-free upper bound shows that a $γ$-uniformly stable algorithm with loss in $[0,L]$ has generalization gap at most $O \left(γ\log(1/δ) +L\sqrt{\frac{\log(1/δ)}{n}}\right)$ with probability $1-δ$. Whether an actual bounded-loss learning algorithm can realize the linear dependence on $\log(1/δ)$ has remained open. The known construction realizes it only for auxiliary weakly dependent random variables whose pointwise range grows with $n$. The known learning lower bound holds only at constant probability. We close this gap. For every $n$, stability level $γ$, and loss bound $L$, we construct one deterministic $γ$-uniformly stable learning problem whose tail satisfies, simultaneously for $1\le p\le c n$, $\mathbb P \left( R(A_S)-R_S(A_S) \ge c'\min \left\{L,γp+L\sqrt{p/n}\right\} \right)\ge e^{-p}.$ The construction is ordinary bounded absolute-loss regression with constant labels. Its key is a multiscale collection of rare Rademacher features. A coordinatewise ramp is stable in sup norm, while an odd symmetrized maximum converts a unique extreme feature into a gap of order $γp$ without violating the loss bound. Geometrically spaced ramps put all confidence levels into the same problem. Together with the logarithmic-free upper bound, this determines the optimal high-probability and moment dependence of uniform stability up to universal constants.
• Abstract（参考訳）: 均一な安定性は、あるトレーニング例がテストポイントでの損失をどの程度変えられるかを制御する。 新しい対数自由上界は、$[0,L]$の損失を持つ$γ$-一様安定なアルゴリズムが、最大$O \left(γ\log(1/δ) +L\sqrt{\frac{\log(1/δ)}{n}}\right)$の一般化ギャップを持つことを示している。 実有界学習アルゴリズムが$\log(1/δ)$に対する線形依存を実現できるかどうかは未定である。 既知の構成は、点幅が$n$で成長する部分弱依存確率変数に対してのみ実現している。 既知の学習の下界は一定の確率でしか持たない。 私たちはこのギャップを埋めます。 すべての$n$, 安定性レベル$γ$, 損失バウンド$L$に対して、1つの決定論的$γ$-一様安定学習問題を構築し、そのテールが1\le p\le c n$, $\mathbb P \left(R(A_S)-R_S(A_S) \ge c'\min \left\{L,γp+L\sqrt{p/n}\right\} \right)\ge e^{-p} に対して同時に満足する。 構造は、定値ラベルを持つ通常の有界絶対剰余回帰である。 キーとなるのは、レアなRademacher機能のマルチスケールコレクションである。 座標的ランプはsupノルムにおいて安定であり、一方奇対称化された最大値は、一意の極端な特徴を損失境界に違反することなく、次数$γp$のギャップに変換する。 幾何学的に空間化されたランプは、すべての信頼レベルを同じ問題にしました。 対数自由な上界と共に、これは一様安定性の最適高確率とモーメント依存を普遍定数まで決定する。

関連論文リスト

• Sample-optimal learning of stabilizer states [0.20999222360659608]
  純粋な$n$-qubit 安定化子状態 $|rangle$ を学ぶにはどちらも必要であり、$|rangle$ のコピーを $n$ で数部アクセスすることが知られている。 ここでは、量子プロシージャが任意の安定化状態を特定することができる最小のコピー数である$L_(n)$を、少なくとも01/8$の確率で証明する。
  論文  参考訳（メタデータ） (2026-09-10T01:48:29Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Quantum Query Complexity of Persistence Statistics in Graph Zigzags [2.895030292351388]
  本研究では、スナップショット・アジャシエンスビットからジグザグバー寿命のスカラーサマリーを推定するクエリ複雑性について検討した。 ランクがグラフの回路ランクであるグラフの場合、非線形バーコード関数はエッジと成分数の平均となる。 すべての固定パワーウェイトに対して$xr$,$rge2$、均一ウィンドウ平均では、最悪のケースの複雑さは$widetilde(nsqrt m/varepsilon)$ Quantumと$(n2m)$ classicalである。
  論文  参考訳（メタデータ） (2026-09-05T02:16:28Z)
• 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)
• Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits [13.075031222564535]
  マルチアームのバンディットアルゴリズムは、後悔によって評価されるが、同等の後悔は、独立ラン毎に異なるアロケーションと共存することができる。 我々は、最低ケースの後悔$mathcalR_K,T$と不安定$mathcalS_K,T$のトレードオフを、端末プルカウントの最大の標準偏差として定義し、$K$アームと$T$ラウンドについて検討する。
  論文  参考訳（メタデータ） (2026-08-18T14:38:47Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• Solving Stochastic Fixed-Point Equations with High Probability [22.376855234542813]
  オラクルの不動点方程式 $mathbfT(mathbfx) = mathbfx$ をノルム空間上で研究する。 本稿では,2次スムーズなバナッハ空間に対する分散還元段階Halpern法であるVR-GHALを紹介する。
  論文  参考訳（メタデータ） (2026-07-10T04:59:20Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias [15.113649527486276]
  良性オーバーフィッティングが線形レートで失敗することを示します。 この局所化機構は信号の存在下で持続するべきであるが、正確な信号-雑音分解は未解決の問題である。
  論文  参考訳（メタデータ） (2026-05-07T14:14:09Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。 スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。 また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
  論文  参考訳（メタデータ） (2023-04-05T07:24:19Z)
• Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap [12.446156563700482]
  凸凹型リプシッツサドル点問題は、$(epsilon,delta)$differential privacyの制約の下で解決可能であることを示す。 また、安定性と精度の間には根本的なトレードオフがあることも示している。
  論文  参考訳（メタデータ） (2023-02-24T21:50:02Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Generalized moduli of continuity under irregular or random deformations via multiscale analysis [0.0]
  多分解近似空間の信号に対して、$U_s$ at scale $s$, $L2$ in the regime $|tau|_Linfty/sll 1$。 不安定性は、|tau|_Linfty/sgg 1$ のときに起こり、成長速度に対して鋭い上限を与える。
  論文  参考訳（メタデータ） (2021-04-24T16:16:30Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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