論文の概要: A Strongly Polynomial Algorithm for Approximate Forster Transforms and
its Application to Halfspace Learning
- arxiv url: http://arxiv.org/abs/2212.03008v1
- Date: Tue, 6 Dec 2022 14:32:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-07 16:13:15.371219
- Title: A Strongly Polynomial Algorithm for Approximate Forster Transforms and
its Application to Halfspace Learning
- Title（参考訳）: 近似フォルスター変換に対する強多項式アルゴリズムとその半空間学習への応用
- Authors: Ilias Diakonikolas and Christos Tzamos and Daniel M. Kane
- Abstract要約: フォースター変換(フォースターりゅう、英: Forster transform)は、データセットを放射等方性位置に配置し、その性質のいくつかを維持しながら、データセットを正規化する方法である。
- 参考スコア（独自算出の注目度）: 56.86097988183311
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Forster transform is a method of regularizing a dataset by placing it in
{\em radial isotropic position} while maintaining some of its essential
properties. Forster transforms have played a key role in a diverse range of
settings spanning computer science and functional analysis. Prior work had
given {\em weakly} polynomial time algorithms for computing Forster transforms,
when they exist. Our main result is the first {\em strongly polynomial time}
algorithm to compute an approximate Forster transform of a given dataset or
certify that no such transformation exists. By leveraging our strongly
polynomial Forster algorithm, we obtain the first strongly polynomial time
algorithm for {\em distribution-free} PAC learning of halfspaces. This learning
result is surprising because {\em proper} PAC learning of halfspaces is {\em
equivalent} to linear programming. Our learning approach extends to give a
strongly polynomial halfspace learner in the presence of random classification
noise and, more generally, Massart noise.
- Abstract（参考訳）: forster変換はデータセットを"em radial isotropic position}"に置きながら、その本質的な性質を保ちながら正規化する手法である。
forster変換は、コンピュータ科学と機能分析にまたがる様々な設定において重要な役割を果たしてきた。
以前の研究は、フォルスター変換を計算するための多項式時間アルゴリズムを弱に与えていた。
我々の主な結果は、与えられたデータセットの近似 forster 変換を計算する最初の {\em strong polynomial time} アルゴリズムであり、そのような変換は存在しないことを証明します。
強い多項式フォースターアルゴリズムを利用して、ハーフスペースの分布自由なPAC学習のための最初の強多項式時間アルゴリズムを得る。
この学習結果は、ハーフスペースのPAC学習が線形プログラミングと同等であるため、驚くべきものである。
学習アプローチは,ランダム分類雑音とマスアート雑音の存在下で,強多項式半空間学習者を与えるように拡張する。
関連論文リスト
- Learning Polynomial Transformations [41.30404402331856]
ガウスの高次元二次変換を学習する問題を考察する。
我々の結果はガウス分布だけでなく、任意の不変な入力分布にまで拡張される。
また、テンソル環分解の証明可能な保証を持つ最初の分解時間アルゴリズムを与える。
論文 参考訳（メタデータ） (2022-04-08T17:59:31Z) - Forster Decomposition and Learning Halfspaces with Noise [60.691817861402676]
フォースター変換 (Forster transform) は、分布を優れた反集中特性を持つものに変換する演算である。
本稿では,Forster変換が存在し,効率よく計算できる少数の分布の解離混合として,任意の分布を効率的に分解可能であることを示す。
論文 参考訳（メタデータ） (2021-07-12T17:00:59Z) - A Reinforcement Learning Environment for Polyhedral Optimizations [68.8204255655161]
マルコフ決定過程(MDP)として多面体モデルにおける法的変換空間の形状に依存しない定式化を提案する。
変換を使う代わりに、定式化は可能なスケジュールの抽象空間に基づいている。
我々の総合的MDP定式化は、強化学習を用いて幅広いループで最適化ポリシーを学習することを可能にする。
論文 参考訳（メタデータ） (2021-04-28T12:41:52Z) - Metric Transforms and Low Rank Matrices via Representation Theory of the
Real Hyperrectangle [17.808087068037985]
ハイパー矩形から生じる行列の固有ベクトルと固有値の計算方法を示す。
次に、これらの接続と共に新しい手法を使用して、いくつかの新しい構造結果を示す。
論文 参考訳（メタデータ） (2020-11-23T16:03:12Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Quantum Gradient Algorithm for General Polynomials [5.008814514502094]
問題を最適化するための一般的な戦略であるグラディエントベースのアルゴリズムは、多くの現代の機械学習技術にとって不可欠である。
着飾った振幅で数値を最適化する量子勾配アルゴリズムを提案する。
高次元最適化におけるポテンシャル値について、この量子アルゴリズムは勾配最適化を容易にする。
論文 参考訳（メタデータ） (2020-04-23T11:28:45Z) - Sketching Transformed Matrices with Applications to Natural Language
Processing [76.6222695417524]
本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。
提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
論文 参考訳（メタデータ） (2020-02-23T03:07:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。