論文の概要: Stronger Coreset Bounds for Kernel Density Estimators via Chaining

• arxiv url: http://arxiv.org/abs/2310.08548v1
• Date: Thu, 12 Oct 2023 17:44:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2023-10-15 10:30:20.923879
• Title: Stronger Coreset Bounds for Kernel Density Estimators via Chaining
• Title（参考訳）: 連鎖によるカーネル密度推定器のより強いコアセット境界
• Authors: Rainie Bozzai and Thomas Rothvoss
• Abstract要約: 本稿では,カーネル関数のコアセットの複雑性を改善するために,差分法と連鎖法を適用した。 我々の結果は、ガウスカーネルとラプラシアカーネルのコアセットとして$Obig(fracsqrtdvarepsilonsqrtloglog frac1varepsilonbig)をランダムに生成する時間アルゴリズムを与える。 また、最もよく知られた$Obig(fracsqrtdvarepsilonsqrtlog (2max1,
• 参考スコア（独自算出の注目度）: 0.5454560484178483
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We apply the discrepancy method and a chaining approach to give improved bounds on the coreset complexity of a wide class of kernel functions. Our results give randomized polynomial time algorithms to produce coresets of size $O\big(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log\log \frac{1}{\varepsilon}}\big)$ for the Gaussian and Laplacian kernels in the case that the data set is uniformly bounded, an improvement that was not possible with previous techniques. We also obtain coresets of size $O\big(\frac{1}{\varepsilon}\sqrt{\log\log \frac{1}{\varepsilon}}\big)$ for the Laplacian kernel for $d$ constant. Finally, we give the best known bounds of $O\big(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log(2\max\{1,\alpha\})}\big)$ on the coreset complexity of the exponential, Hellinger, and JS Kernels, where $1/\alpha$ is the bandwidth parameter of the kernel.
• Abstract（参考訳）: 我々は,幅広いカーネル関数のコアセットの複雑性を改良するために,分離法と連鎖法を適用した。 この結果から,ランダム化多項式時間アルゴリズムは,データセットが一様有界である場合にはガウスおよびラプラキアのカーネルに対して,サイズ$o\big(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log\log \frac{1}{\varepsilon}}\big)$のコア集合を生成する。 また、サイズ $O\big(\frac{1}{\varepsilon}\sqrt{\log\log \frac{1}{\varepsilon}}\big)$d$ constant のラプラシア核に対してコアセットを得る。 最後に、最もよく知られた境界である$o\big(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log(2\max\{1,\alpha\})}\big)$ を指数関数、ヘリンガー、jsカーネルのコアセットの複雑さに基づいて与える。

関連論文リスト

• On the $O(\rac{\sqrt{d}}{K^{1/4}})$ Convergence Rate of AdamW Measured by $\ell_1$ Norm [54.28350823319057]
  本稿では、$ell_$ノルムで測定されたAdamWの収束率$frac1Ksum_k=1KEleft[|nabla f(xk)|_1right]leq O(fracsqrtdCK1/4)を確立する。
  論文  参考訳（メタデータ） (2025-05-17T05:02:52Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• On the $O(\rac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
  本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。 我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。 収束率は$frac1Tsum_k=1Tと類似していると考えられる。
  論文  参考訳（メタデータ） (2024-02-01T07:21:32Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Improved Kernel Alignment Regret Bound for Online Kernel Learning [11.201662566974232]
  提案手法は, 既往の結果よりも, 計算量や計算量が多くなるアルゴリズムを提案する。 核行列の固有値が指数関数的に減衰すると、我々のアルゴリズムは$O(sqrtmathcalA_T)$の後悔を、$O(ln2T)$の計算複雑性で楽しむ。 我々はアルゴリズムをバッチ学習に拡張し、以前の$Oを改善した$O(frac1TsqrtmathbbE[mathcalA_T])$over risk boundを得る。
  論文  参考訳（メタデータ） (2022-12-26T02:32:20Z)
• Lower Bounds on the Worst-Case Complexity of Efficient Global Optimization [11.523746174066702]
  我々は、その対応する再生核ヒルベルト空間(RKHS)における球の計量エントロピーの観点から、効率的な大域最適化の複雑さに対する統一された下界を導出する。 この下界は、一般に使用される2乗指数核とマタン核の非適応探索アルゴリズムによって達成された上界にほぼ一致することを示す。
  論文  参考訳（メタデータ） (2022-09-20T11:57:13Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Faster Rates of Convergence to Stationary Points in Differentially Private Optimization [31.46358820048179]
  リプシッツの定常点と滑らかな関数を$(varepsilon,delta)$-differential privacy(DP)で近似する問題について検討する。 点 $widehatw$ は関数 $mathbbRdrightarrowmathbbR$ if $|nabla F(widehatw)|leq alpha$ の $alpha$-stationary point と呼ばれる。 我々は$tildeObig(big[)を見つける新しい効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-06-02T02:43:44Z)
• On the speed of uniform convergence in Mercer's theorem [6.028247638616059]
  コンパクト集合上の連続正定核 $K(mathbf x, mathbf y)$ は $sum_i=1infty lambda_iphi_i(mathbf x)phi_i(mathbf y)$ と表すことができ、$(lambda_i,phi_i)$ は対応する積分作用素の固有値-固有ベクトル対である。 固有値の減衰速度からこの収束速度を推定し、300万ドルで証明する。
  論文  参考訳（メタデータ） (2022-05-01T15:07:57Z)
• Non-asymptotic spectral bounds on the $\varepsilon$-entropy of kernel classes [4.178980693837599]
  この話題は、カーネルベースの手法の現代的な統計理論において重要な方向である。 我々は、我々の境界の多くの結果について議論し、それらが一般のカーネルのバウンドよりもかなり厳密であることを示す。
  論文  参考訳（メタデータ） (2022-04-09T16:45:22Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  カーネル群に基づく暗黙の空間性誘導機構について述べる。 アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
  論文  参考訳（メタデータ） (2021-10-12T09:36:41Z)
• Kernel Thinning [26.25415159542831]
  カーネルの薄型化は、サンプリングや標準的な薄型化よりも効率的に$mathbbP$を圧縮するための新しい手順である。 我々は、ガウス、マタン、およびB-スプライン核に対する明示的な非漸近的な最大誤差境界を導出する。
  論文  参考訳（メタデータ） (2021-05-12T17:56:42Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• Convergence of Graph Laplacian with kNN Self-tuned Kernels [14.645468999921961]
  自己チューニングされたカーネルは、各点に$sigma_i$ を $k$-nearest neighbor (kNN) 距離で適応的に設定する。 本稿では、グラフラプラシアン作用素$L_N$を、kNN自己チューニングカーネルの新しい族に対する多様体(重み付き)ラプラシアンに収束することを証明する。
  論文  参考訳（メタデータ） (2020-11-03T04:55:33Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• 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)
• Optimal Coreset for Gaussian Kernel Density Estimation [0.8376091455761259]
  点集合 $Psubset mathbbRd$ が与えられたとき、$P$ の核密度推定は [ overlinemathcalG_P(x) = frac1left|Pright|sum_pin Pe-leftlVert x-p rightrVert2 ] for any $xinmathbbRd$ と定義される。 我々は、小さなサブセット$Q$ of $P を構築する方法を研究する。
  論文  参考訳（メタデータ） (2020-07-15T22:58:50Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。 代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
  論文  参考訳（メタデータ） (2020-06-12T10:21:40Z)

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

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