論文の概要: Reverse Euclidean and Gaussian isoperimetric inequalities for parallel sets with applications

• arxiv url: http://arxiv.org/abs/2006.09568v2
• Date: Fri, 21 Aug 2020 02:47:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-20 21:54:51.916776
• Title: Reverse Euclidean and Gaussian isoperimetric inequalities for parallel sets with applications
• Title（参考訳）: 平行集合に対する逆ユークリッドおよびガウス等距離不等式と応用
• Authors: Varun Jog
• Abstract要約: 例えば、$r$-parallel set in $mathbb Rd$ with volume at most $V$ is upper-bounded by $eTheta(d)V/r$, and its Gaussian surface area are upper-bounded by $max(eTheta(d), eTheta(d)/r)$。 また、$r$-パラレル集合に対するブラン・ミンコフスキーの不等式(英語版)の逆形式を導出し、ガウスの滑らかな確率変数に対する逆エントロピーパワー不等式(英語版)(verse entropy power inequality)を導出する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The $r$-parallel set of a measurable set $A \subseteq \mathbb R^d$ is the set of all points whose distance from $A$ is at most $r$. In this paper, we show that the surface area of an $r$-parallel set in $\mathbb R^d$ with volume at most $V$ is upper-bounded by $e^{\Theta(d)}V/r$, whereas its Gaussian surface area is upper-bounded by $\max(e^{\Theta(d)}, e^{\Theta(d)}/r)$. We also derive a reverse form of the Brunn-Minkowski inequality for $r$-parallel sets, and as an aside a reverse entropy power inequality for Gaussian-smoothed random variables. We apply our results to two problems in theoretical machine learning: (1) bounding the computational complexity of learning $r$-parallel sets under a Gaussian distribution; and (2) bounding the sample complexity of estimating robust risk, which is a notion of risk in the adversarial machine learning literature that is analogous to the Bayes risk in hypothesis testing.
• Abstract（参考訳）: 可測集合 $A \subseteq \mathbb R^d$ の $r$-パラレル集合は、$A$ からの距離が少なくとも $r$ であるすべての点の集合である。 本稿では、最大$V$の体積を持つ$\mathbb R^d$の$r$パラレル集合の表面積が、$e^{\Theta(d)}V/r$で上界であるのに対し、そのガウス曲面面積は$\max(e^{\Theta(d)},e^{\Theta(d)}/r$で上界であることを示す。 また、brunn-minkowski不等式をr$-parallel 集合に対して逆形式として導出し、gaussian-smoothed 確率変数の逆エントロピーパワー不等式を別にして導出する。 理論機械学習の2つの問題に対して,(1) ガウス分布下での学習の計算複雑性をr$-parallel 集合に限定する,(2) 仮説テストにおけるベイズリスクに類似した,敵対的機械学習文献におけるリスクの概念であるロバストリスクを推定するサンプル複雑性を限定する,という2つの問題を適用する。

関連論文リスト

• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Toward $L_\infty$-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields [35.76184529520015]
  多くの機械学習アプリケーションは、入力ドメイン全体、すなわち$L_infty$-errorで最小ケースエラーの関数を学習する必要がある。 既存の理論的研究の多くは、$L$-errorのような平均エラーの回復を保証するだけである。 本稿では, 地絡関数のランダム性を生かして, 不合理性以外のいくつかの初期ステップについて述べる。
  論文  参考訳（メタデータ） (2023-04-29T18:33:39Z)
• Overparametrized linear dimensionality reductions: From projection pursuit to two-layer neural networks [10.368585938419619]
  $mathbbRd$に$n$のデータポイントのクラウドが与えられると、$mathbbRd$の$m$次元部分空間へのすべての射影を考える。 この確率分布の集まりは、$n,d$が大きくなるとどのように見えるか? この極限の低次元射影として生じる $mathbbRm$ の確率分布の集合の α$ を $mathscrF_m で表すと、$mathscrF_ に新たな内界と外界を確立する。
  論文  参考訳（メタデータ） (2022-06-14T00:07:33Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。 規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
  論文  参考訳（メタデータ） (2021-05-31T16:10:49Z)
• SDP Achieves Exact Minimax Optimality in Phase Synchronization [19.909352968029584]
  我々は、ノイズ測定$Y=z*z*+sigma WinmathbbCntimes ntimes nで位相同期問題を研究する。 SDPが誤差境界$ (1+o)fracnp22np$を2乗の$ell$損失で達成することを証明する。
  論文  参考訳（メタデータ） (2021-01-07T03:14:05Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Multivariate mean estimation with direction-dependent accuracy [8.147652597876862]
  独立な同一分布観測に基づくランダムベクトルの平均を推定する問題を考察する。 確率ベクトルの1次元辺の分散があまり小さくない全ての方向において、ほぼ最適誤差を持つ推定器を証明した。
  論文  参考訳（メタデータ） (2020-10-22T17:52:45Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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