論文の概要: Agnostic Learnability of Halfspaces via Logistic Loss
- arxiv url: http://arxiv.org/abs/2201.13419v1
- Date: Mon, 31 Jan 2022 18:24:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-01 16:14:31.659311
- Title: Agnostic Learnability of Halfspaces via Logistic Loss
- Title（参考訳）: ロジスティック損失によるハーフスペースの学習性
- Authors: Ziwei Ji, Kwangjun Ahn, Pranjal Awasthi, Satyen Kale, and Stefani Karp
- Abstract要約: 等質半空間の学習の基本問題に対するロジスティック回帰による近似保証について検討する。
我々の手法は、放射状リプシッツ性に関係なく、ロジスティック損失に対する$Omega(sqrttextrmOPT)$ローバウンドを克服できる。
- 参考スコア（独自算出の注目度）: 35.29651441967513
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate approximation guarantees provided by logistic regression for
the fundamental problem of agnostic learning of homogeneous halfspaces.
Previously, for a certain broad class of "well-behaved" distributions on the
examples, Diakonikolas et al. (2020) proved an $\tilde{\Omega}(\textrm{OPT})$
lower bound, while Frei et al. (2021) proved an
$\tilde{O}(\sqrt{\textrm{OPT}})$ upper bound, where $\textrm{OPT}$ denotes the
best zero-one/misclassification risk of a homogeneous halfspace. In this paper,
we close this gap by constructing a well-behaved distribution such that the
global minimizer of the logistic risk over this distribution only achieves
$\Omega(\sqrt{\textrm{OPT}})$ misclassification risk, matching the upper bound
in (Frei et al., 2021). On the other hand, we also show that if we impose a
radial-Lipschitzness condition in addition to well-behaved-ness on the
distribution, logistic regression on a ball of bounded radius reaches
$\tilde{O}(\textrm{OPT})$ misclassification risk. Our techniques also show for
any well-behaved distribution, regardless of radial Lipschitzness, we can
overcome the $\Omega(\sqrt{\textrm{OPT}})$ lower bound for logistic loss simply
at the cost of one additional convex optimization step involving the hinge loss
and attain $\tilde{O}(\textrm{OPT})$ misclassification risk. This two-step
convex optimization algorithm is simpler than previous methods obtaining this
guarantee, all of which require solving $O(\log(1/\textrm{OPT}))$ minimization
problems.
- Abstract（参考訳）: 等質半空間の非依存学習の基本問題に対するロジスティック回帰による近似保証について検討する。
以前は、例の「良い振る舞い」分布のあるクラスに対して、 Diakonikolas et al. (2020) は$\tilde{\Omega}(\textrm{OPT})$ lower bound を証明し、 Frei et al. (2021) は$\tilde{O}(\sqrt{\textrm{OPT}})$ upper bound を証明した。
本稿では,この分布上のロジスティックリスクの大域的最小化が,上限値に一致する$\omega(\sqrt{\textrm{opt}})$ミスクラス化リスクのみを達成するような,十分に整備された分布を構築することにより,このギャップを解消する(frei et al., 2021)。
他方, 分布の健全性に加えてラジアルリプシッツ性条件を課した場合, 有界半径球上のロジスティック回帰は$\tilde{o}(\textrm{opt})$ の誤分類リスクに達することを示した。
また,ラジアルリプシッツ性に拘わらず,ロジスティック損失に対する$\omega(\sqrt{\textrm{opt}})$の上限を,ヒンジ損失を伴って$\tilde{o}(\textrm{opt})$の誤分類リスクを得るための1つの追加の凸最適化ステップのコストだけで克服できることを示した。
この二段階凸最適化アルゴリズムはこの保証を得る以前の方法よりも単純であり、いずれも$o(\log(1/\textrm{opt}))$最小化問題を解く必要がある。
関連論文リスト
- Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。
我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文 参考訳（メタデータ） (2024-06-10T17:48:36Z) - LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
本研究では、独立かつ同一に分散したコンテキストを持つ線形文脈帯域問題について考察する。
提案アルゴリズムは、Tsallisエントロピーを持つFollow-The-Regularized-Leaderに基づいており、$alpha$-textual-Con (LC)-Tsallis-INFと呼ばれている。
論文 参考訳（メタデータ） (2024-03-05T18:59:47Z) - Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions [11.222970035173372]
カーネルベースのスコア推定器は$widetildeOleft(n-1 t-fracd+22(tfracd2 vee 1)rightの最適平均二乗誤差を達成する
核を用いたスコア推定器は,拡散モデルで生成した試料の分布の総変動誤差に対して,極小ガウスの下での最大平均2乗誤差を$widetildeOleft(n-1/2 t-fracd4right)$上界で達成することを示す。
論文 参考訳（メタデータ） (2024-02-23T20:51:31Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces
and ReLU Regression under Gaussian Marginals [43.0867217287089]
ガウス分布の下で半空間を不可知的に学習する作業について検討する。
この課題に対して,ほぼ最適計算硬度を証明した。
論文 参考訳（メタデータ） (2023-02-13T16:46:23Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。