論文の概要: Approximate Maximum Halfspace Discrepancy
- arxiv url: http://arxiv.org/abs/2106.13851v1
- Date: Fri, 25 Jun 2021 19:14:45 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-01 10:56:38.657776
- Title: Approximate Maximum Halfspace Discrepancy
- Title（参考訳）: 近似最大半空間差
- Authors: Michael Matheny and Jeff M. Phillips
- Abstract要約: 範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。
数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
- 参考スコア（独自算出の注目度）: 6.35821487778241
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Consider the geometric range space $(X, \mathcal{H}_d)$ where $X \subset
\mathbb{R}^d$ and $\mathcal{H}_d$ is the set of ranges defined by
$d$-dimensional halfspaces. In this setting we consider that $X$ is the
disjoint union of a red and blue set. For each halfspace $h \in \mathcal{H}_d$
define a function $\Phi(h)$ that measures the "difference" between the fraction
of red and fraction of blue points which fall in the range $h$. In this context
the maximum discrepancy problem is to find the $h^* = \arg \max_{h \in (X,
\mathcal{H}_d)} \Phi(h)$. We aim to instead find an $\hat{h}$ such that
$\Phi(h^*) - \Phi(\hat{h}) \le \varepsilon$. This is the central problem in
linear classification for machine learning, in spatial scan statistics for
spatial anomaly detection, and shows up in many other areas. We provide a
solution for this problem in $O(|X| + (1/\varepsilon^d) \log^4
(1/\varepsilon))$ time, which improves polynomially over the previous best
solutions. For $d=2$ we show that this is nearly tight through conditional
lower bounds. For different classes of $\Phi$ we can either provide a
$\Omega(|X|^{3/2 - o(1)})$ time lower bound for the exact solution with a
reduction to APSP, or an $\Omega(|X| + 1/\varepsilon^{2-o(1)})$ lower bound for
the approximate solution with a reduction to 3SUM.
A key technical result is a $\varepsilon$-approximate halfspace range
counting data structure of size $O(1/\varepsilon^d)$ with $O(\log
(1/\varepsilon))$ query time, which we can build in $O(|X| + (1/\varepsilon^d)
\log^4 (1/\varepsilon))$ time.
- Abstract（参考訳）: 幾何学的範囲空間 $(X, \mathcal{H}_d)$ を考えると、$X \subset \mathbb{R}^d$ と $\mathcal{H}_d$ は$d$次元半空間で定義される範囲の集合である。
この設定では、$x$ は赤と青の集合の合同和であると考える。
各半空間 $h \in \mathcal{H}_d$ に対して、赤の分数と青の点の分数の差を測る函数 $\Phi(h)$ を定義する。
この文脈における最大の相違問題は、$h^* = \arg \max_{h \in (X, \mathcal{H}_d)} \Phi(h)$ を見つけることである。
代わりに、$\phi(h^*) - \phi(\hat{h}) \le \varepsilon$ となる$\hat{h}$を求める。
これは、機械学習の線形分類、空間的異常検出のための空間スキャン統計における中心的な問題であり、他の多くの領域に見られる。
この問題に対する解は$o(|x| + (1/\varepsilon^d) \log^4 (1/\varepsilon))$ time で与えられる。
$d=2$ の場合、条件付き下界ではほぼ厳密であることを示す。
異なる$\Phi$のクラスに対して、APSP に還元された完全解に対して $\Omega(|X|^{3/2 - o(1)})$ 時下界を与えるか、3SUM に還元された近似解に対して $\Omega(|X| + 1/\varepsilon^{2-o(1)})$ 時下界を与えることができる。
主要な技術的結果は、$O(1/\varepsilon^d)$ with $O(\log (1/\varepsilon))$ query timeであり、$O(|X| + (1/\varepsilon^d) \log^4 (1/\varepsilon)$ timeである。
関連論文リスト
- Sparsifying Suprema of Gaussian Processes [6.638504164134713]
我々は、$O_varepsilon(1)$-size subset $S subseteq T$ と、S$ における実値 $c_s_s の集合が存在することを示す。
また、中心となるガウス過程の過度にスペーシフィケーション結果を用いて、有界な幾何学的幅の凸集合に対するスペーシフィケーション補題を与える。
論文 参考訳（メタデータ） (2024-11-22T01:43:58Z) - Fast, robust approximate message passing [2.668787455520979]
本稿では,AMPアルゴリズムを頑健に実装するための高速なスペクトル計算法を提案する。
提案アルゴリズムはスペクトル前処理のステップを実行し,$mathcal A$の摂動を緩やかに修正する。
論文 参考訳（メタデータ） (2024-11-05T03:20:14Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - For Kernel Range Spaces a Constant Number of Queries Are Sufficient [13.200502573462712]
カーネル範囲空間は、X の部分集合 mathbbRd$ の集合と、固定されたカーネルによる全てのクエリの空間に関する。
Anvarepsilon$-cover は点 $Q の部分集合 mathbbRd$ for any $p in mathbbRd$ that $frac1n |R_p - R_q|leq varepsilon$ for some $q in Q$ の部分集合である。
論文 参考訳（メタデータ） (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) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - 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) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。
低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文 参考訳（メタデータ） (2021-03-17T18:18:57Z) - Sets Clustering [25.358415142404752]
我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。
このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。
オープンソースコードと文書分類および施設位置の実験結果も提供される。
論文 参考訳（メタデータ） (2020-03-09T13:30:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。