論文の概要: Point Location and Active Learning: Learning Halfspaces Almost Optimally
- arxiv url: http://arxiv.org/abs/2004.11380v1
- Date: Thu, 23 Apr 2020 18:00:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-10 09:30:31.286783
- Title: Point Location and Active Learning: Learning Halfspaces Almost Optimally
- Title（参考訳）: ポイントロケーションとアクティブラーニング:ハーフスペースをほぼ最適に学習する
- Authors: Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
- Abstract要約: 有限集合 $X の部分集合 mathbbRd$ とバイナリ線型 $c: mathbbRd to 0,1$ が与えられたとき、$c(x)$ という形のクエリは、$X$ のすべての点のラベルを学ぶために何回必要か?
最初のほぼ最適解、深さ$tildeO(dlog(|X|))$のランダム化線形決定木を提供し、以前の$tildeO(dlog(|X))の最高値を改善する。
- 参考スコア（独自算出の注目度）: 24.80812483480747
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a finite set $X \subset \mathbb{R}^d$ and a binary linear classifier
$c: \mathbb{R}^d \to \{0,1\}$, how many queries of the form $c(x)$ are required
to learn the label of every point in $X$? Known as \textit{point location},
this problem has inspired over 35 years of research in the pursuit of an
optimal algorithm. Building on the prior work of Kane, Lovett, and Moran (ICALP
2018), we provide the first nearly optimal solution, a randomized linear
decision tree of depth $\tilde{O}(d\log(|X|))$, improving on the previous best
of $\tilde{O}(d^2\log(|X|))$ from Ezra and Sharir (Discrete and Computational
Geometry, 2019). As a corollary, we also provide the first nearly optimal
algorithm for actively learning halfspaces in the membership query model. En
route to these results, we prove a novel characterization of Barthe's Theorem
(Inventiones Mathematicae, 1998) of independent interest. In particular, we
show that $X$ may be transformed into approximate isotropic position if and
only if there exists no $k$-dimensional subspace with more than a
$k/d$-fraction of $X$, and provide a similar characterization for exact
isotropic position.
- Abstract（参考訳）: 有限集合 $X \subset \mathbb{R}^d$ とバイナリ線型分類器 $c: \mathbb{R}^d \to \{0,1\}$ が与えられたとき、$c(x)$ という形のクエリは、$X$ のすべての点のラベルを学ぶために必要となる。
textit{point location} として知られるこの問題は、最適なアルゴリズムを追求する35年以上の研究に影響を与えた。
Kane, Lovett, and Moran (ICALP 2018) の以前の研究に基づいて、我々は、Ezra と Sharir (Discrete and Computational Geometry, 2019) の以前のベストである $\tilde{O}(d\log(|X|))$ のランダム化線形決定木である、深さ$\tilde{O}(d^2\log(|X|))$ の最初のほぼ最適解を提供する。
また,メンバシップクエリモデルのハーフスペースを積極的に学習するための,最初の最適化アルゴリズムも提供する。
これらの結果に対し,バーテの定理(inventiones mathematicae,1998)の独立興味の新たな特徴付けを証明した。
特に、$x$ が近似等方的位置へ変換できることと、$k/d$-フラクションが $x$ 以上の $k$-次元部分空間が存在しない場合に限り、正確な等方的位置に対する類似のキャラクタリゼーションを提供する。
関連論文リスト
- Combinatorial optimization of the coefficient of determination [0.0]
決定係数が最も高い平面上の$n$点の$k$-部分集合を選択するための効率的なアルゴリズムを開発する。
誤差のない$n=30$までの試行で,提案手法の最適性を実験的に実証した。
論文 参考訳（メタデータ） (2024-10-12T00:53:25Z) - Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Sharper Model-free Reinforcement Learning for Average-reward Markov
Decision Processes [21.77276136591518]
我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。
シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
論文 参考訳（メタデータ） (2023-06-28T17:43:19Z) - Nearly Minimax Optimal Reinforcement Learning with Linear Function
Approximation [25.60689712525918]
本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。
本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
論文 参考訳（メタデータ） (2022-06-23T06:04:21Z) - 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) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Model Selection with Near Optimal Rates for Reinforcement Learning with
General Model Classes [27.361399036211694]
有限地平線エピソディック強化学習(RL)問題に対するモデル選択の問題に対処する。
モデル選択フレームワークでは、$mathcalP*$の代わりに、遷移カーネルのネストされたファミリーが$M$を与えられる。
textttARL-GENが$TildemathcalO(d_mathcalE* H2+sqrtd_mathcalE* mathbbM* H2T)$の後悔を得ることを示す。
論文 参考訳（メタデータ） (2021-07-13T05:00:38Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。