論文の概要: New Bounds for Kernel Sums via Fast Spherical Embeddings

• arxiv url: http://arxiv.org/abs/2605.01263v1
• Date: Sat, 02 May 2026 05:42:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-05 20:33:49.673932
• Title: New Bounds for Kernel Sums via Fast Spherical Embeddings
• Title（参考訳）: 高速球面埋め込みによるカーネルサムの新たな境界
• Authors: Tal Wagner,
• Abstract要約: 新たに$tilde O(d+varepsilon2+1/varepsilon3)$を証明した。 証明の中心には、Bartal, Recht and Schulman (2011) によって導入された意味での新しい高速球面埋め込み定理があり、埋め込みデータ直径を制限している。
• 参考スコア（独自算出の注目度）: 12.14121214083427
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study query time bounds for the fundamental problem of estimating the kernel mean $\frac1{|X|}\sum_{x\in X}\mathbf{k}(x,y)$ of a query $y$ in a finite dataset $X\subset\mathbb{R}^d$ up to a prescribed additive error $\varepsilon$. The best known bounds for the Gaussian kernel are $O(d/\varepsilon^2)$, $\widetilde O(d+1/\varepsilon^4)$, and $\widetilde O(d+Δ^2/\varepsilon^2)$, where $Δ$ is the diameter of a region containing the points. We prove the new bound $\tilde O(d+\varepsilonΔ^2+1/\varepsilon^3)$, which improves over the previous ones in regimes with small error $\varepsilon$ and intermediate diameter $Δ$. At the center of our proof is a new fast spherical embedding theorem in the sense introduced by Bartal, Recht and Schulman (2011), which limits the embedded data diameter while preserving local Euclidean distances and avoiding ``distance collapse'' at larger scales. This fast embedding theorem may be of independent interest.
• Abstract（参考訳）: 我々は、カーネルの平均を推定する基本的な問題のクエリ時間境界について研究する: $\frac1{|X|}\sum_{x\in X}\mathbf{k}(x,y)$ of a query $y$ in a finite dataset $X\subset\mathbb{R}^d$ to a prescribed additive error $\varepsilon$。 ガウス核の最もよく知られた境界は、$O(d/\varepsilon^2)$, $\widetilde O(d+1/\varepsilon^4)$, $\widetilde O(d+Δ^2/\varepsilon^2)$である。 我々は、新しい有界な$\tilde O(d+\varepsilonΔ^2+1/\varepsilon^3)$を証明し、小さな誤差が$\varepsilon$と中間径が$Δ$で以前のものよりも改善する。 証明の中心には、Bartal, Recht and Schulman (2011) によって導入された意味での新しい高速球面埋め込み定理があり、これは、局所ユークリッド距離を保ちながら埋め込みデータ直径を制限し、より大規模な「距離崩壊」を避けるものである。 この高速埋め込み定理は独立した興味を持つかもしれない。

関連論文リスト

• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Dimension-Independent Kernel ε-Covers [8.234735564035567]
  カーネル範囲空間は、X の部分集合 mathbbRd$ の集合と、固定されたカーネルによる全てのクエリの空間に関する。 カーネルレンジ空間に対して$varepsilon$-coverという概念を導入する。
  論文  参考訳（メタデータ） (2023-06-28T19:19:33Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Improved Coresets for Euclidean $k$-Means [24.850829728643923]
  1組の$d$次元の$n$ポイントが与えられたとき、ユークリッド$k$平均問題(ユークリッド$k$中間問題を参照)は、$k$センターを見つけることからなる。 本稿では,$tilde O(min(k2 cdot varepsilon-2,kcdot varepsilon-4)$ for $k$-means and $tilde O(min(k4/3 cdot varepsilon)を改善する。
  論文  参考訳（メタデータ） (2022-11-15T14:47:24Z)
• Non-asymptotic spectral bounds on the $\varepsilon$-entropy of kernel classes [4.178980693837599]
  この話題は、カーネルベースの手法の現代的な統計理論において重要な方向である。 我々は、我々の境界の多くの結果について議論し、それらが一般のカーネルのバウンドよりもかなり厳密であることを示す。
  論文  参考訳（メタデータ） (2022-04-09T16:45:22Z)
• 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)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)

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

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