論文の概要: Learning Weakly Convex Sets in Metric Spaces

• arxiv url: http://arxiv.org/abs/2105.06251v2
• Date: Tue, 19 Mar 2024 18:02:11 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-21 23:26:53.524506
• Title: Learning Weakly Convex Sets in Metric Spaces
• Title（参考訳）: 計量空間における弱凸集合の学習
• Authors: Eike Stadtländer, Tamás Horváth, Stefan Wrobel,
• Abstract要約: 機械学習理論における中心的な問題は、ゼロエラーを持つ一貫した仮説を効率的に見つけることができるかどうかである。 このアルゴリズムの一般的な考え方は、弱凸仮説の場合にまで拡張可能であることを示す。
• 参考スコア（独自算出の注目度）: 2.0618817976970103
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One of the central problems studied in the theory of machine learning is the question of whether, for a given class of hypotheses, it is possible to efficiently find a {consistent} hypothesis, i.e., which has zero training error. While problems involving {\em convex} hypotheses have been extensively studied, the question of whether efficient learning is possible for non-convex hypotheses composed of possibly several disconnected regions is still less understood. Although it has been shown quite a while ago that efficient learning of weakly convex hypotheses, a parameterized relaxation of convex hypotheses, is possible for the special case of Boolean functions, the question of whether this idea can be developed into a generic paradigm has not been studied yet. In this paper, we provide a positive answer and show that the consistent hypothesis finding problem can indeed be solved in polynomial time for a broad class of weakly convex hypotheses over metric spaces. To this end, we propose a general domain-independent algorithm for finding consistent weakly convex hypotheses and prove sufficient conditions for its efficiency that characterize the corresponding hypothesis classes. To illustrate our general algorithm and its properties, we discuss several non-trivial learning examples to demonstrate how it can be used to efficiently solve the corresponding consistent hypothesis finding problem. Without the weak convexity constraint, these problems are known to be computationally intractable. We then proceed to show that the general idea of our algorithm can even be extended to the case of extensional weakly convex hypotheses, as it naturally arise, e.g., when performing vertex classification in graphs. We prove that using our extended algorithm, the problem can be solved in polynomial time provided the distances in the domain can be computed efficiently.
• Abstract（参考訳）: 機械学習理論で研究される中心的な問題の1つは、与えられた仮説のクラスに対して、効率よく {consistent} 仮説を見つけることができるかどうか、すなわち、訓練誤差がゼロであるかどうかである。 エム凸仮説に関する問題は広く研究されているが、いくつかの非連結領域からなる非凸仮説に対して効率的な学習が可能かどうかという問題は、いまだに理解されていない。 弱凸仮説の効率的な学習(凸仮説のパラメータ化緩和)がブール関数の特別な場合において可能であることが、かなり以前から示されてきたが、このアイデアが一般的なパラダイムへと発展できるかどうかという問題は、まだ研究されていない。 本稿では,測度空間上の弱凸仮説の広いクラスに対して,一貫した仮説探索問題を多項式時間で解くことができることを示す。 そこで本研究では,一貫した弱凸仮説を導出する一般領域非依存アルゴリズムを提案し,その効率性を証明し,対応する仮説クラスを特徴づける。 一般のアルゴリズムとその特性を説明するために,いくつかの非自明な学習例について論じ,それに対応する一貫した仮説探索問題を効率的に解く方法を示す。 弱凸性制約がなければ、これらの問題は計算的に難解であることが知られている。 そして、グラフで頂点分類を行う際に自然に発生するような、我々のアルゴリズムの一般的な考え方は、拡張性の弱い凸仮説にまで拡張可能であることを示す。 拡張アルゴリズムを用いることで、領域内の距離を効率的に計算できるような多項式時間で問題を解くことができることを示す。

関連論文リスト

• Non-Convex Robust Hypothesis Testing using Sinkhorn Uncertainty Sets [18.46110328123008]
  非破壊仮説テスト問題に対処する新しい枠組みを提案する。 目標は、最大数値リスクを最小限に抑える最適な検出器を探すことである。
  論文  参考訳（メタデータ） (2024-03-21T20:29:43Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• On Continuity of Robust and Accurate Classifiers [3.8673630752805437]
  敵の訓練が仮説の堅牢性を向上させることが示されている。 仮説の頑健性と正確性は互いに相反していることが示唆されている。 本稿では,その頑健さと精度に相容れない仮説の連続性について,その代替案を提示する。
  論文  参考訳（メタデータ） (2023-09-29T08:14:25Z)
• Learnability, Sample Complexity, and Hypothesis Class Complexity for Regression Models [10.66048003460524]
  この研究はPACの基礎に触発され、既存の回帰学習問題に動機付けられている。 提案手法はEpsilon-Confidence Aough Correct (epsilon CoAC)で示され、Kullback Leibler divergence(相対エントロピー)を利用する。 これにより、学習者は異なる複雑性順序の仮説クラスを比較でき、それらの中から最小のエプシロンを最適に選択できる。
  論文  参考訳（メタデータ） (2023-03-28T15:59:12Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  本稿では,カーネル手法のコンテキストにおいて,現象を正確に特徴付けることができることを示す。 分離可能なヒルベルト空間における2次対象の最小化を考慮し、早期停止の場合、学習速度の選択が得られた解のスペクトル分解に影響を及ぼすことを示す。
  論文  参考訳（メタデータ） (2022-02-28T13:01:04Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。 我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
  論文  参考訳（メタデータ） (2021-10-12T02:21:30Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Learning from Non-Random Data in Hilbert Spaces: An Optimal Recovery Perspective [12.674428374982547]
  最適回復の観点から回帰問題を考察する。 まず、有限次元ヒルベルト空間における任意の回復写像の最悪のケース誤差を計算する半定値プログラムを開発する。 最適回復法は,アルゴリズム的な視点からユーザフレンドリな式を提供する。
  論文  参考訳（メタデータ） (2020-06-05T21:49:07Z)
• Counterexamples to the Low-Degree Conjecture [80.3668228845075]
  ホプキンスの予想は、ある高次元仮説テスト問題に対して、非時間アルゴリズムはいわゆる「単純な統計」よりも優れていると仮定する。 この予想は、統計対計算のトレードオフを理解しようとする最近の研究のラインを囲む信念を定式化する。
  論文  参考訳（メタデータ） (2020-04-17T21:08:11Z)

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

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