論文の概要: Learning Weakly Convex Sets in Metric Spaces
- arxiv url: http://arxiv.org/abs/2105.06251v1
- Date: Mon, 10 May 2021 23:00:02 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-14 14:12:50.169599
- Title: Learning Weakly Convex Sets in Metric Spaces
- Title(参考訳): 計量空間における弱凸集合の学習
- Authors: Eike Stadtl\"ander, Tam\'as Horv\'ath, Stefan Wrobel
- Abstract要約: 弱凸集合は閉作用素によって特徴づけられ、一対の不連結な連結ブロックの集合に一意に分解されることを示す。
我々は、例のセットと一致し、最小数の超矩形を含む弱凸集合が時間内に見つかることを示す。
- 参考スコア(独自算出の注目度): 1.456699007803424
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the notion of weak convexity in metric spaces, a generalization
of ordinary convexity commonly used in machine learning. It is shown that
weakly convex sets can be characterized by a closure operator and have a unique
decomposition into a set of pairwise disjoint connected blocks. We give two
generic efficient algorithms, an extensional and an intensional one for
learning weakly convex concepts and study their formal properties. Our
experimental results concerning vertex classification clearly demonstrate the
excellent predictive performance of the extensional algorithm. Two non-trivial
applications of the intensional algorithm to polynomial PAC-learnability are
presented. The first one deals with learning $k$-convex Boolean functions,
which are already known to be efficiently PAC-learnable. It is shown how to
derive this positive result in a fairly easy way by the generic intensional
algorithm. The second one is concerned with the Euclidean space equipped with
the Manhattan distance. For this metric space, weakly convex sets are a union
of pairwise disjoint axis-aligned hyperrectangles. We show that a weakly convex
set that is consistent with a set of examples and contains a minimum number of
hyperrectangles can be found in polynomial time. In contrast, this problem is
known to be NP-complete if the hyperrectangles may be overlapping.
- Abstract(参考訳): 本稿では,機械学習においてよく用いられる一般凸性の一般化である距離空間における弱凸の概念を紹介する。
弱凸集合は閉作用素によって特徴づけられ、一意な分解をペアワイズ不連結ブロックの集合に持つことが示されている。
弱凸概念を学習し、それらの形式的性質を研究するために、拡張型とインテンション型という2つの汎用的効率的なアルゴリズムを与える。
頂点分類に関する実験結果から,拡張アルゴリズムの優れた予測性能が明らかとなった。
インテンショナルアルゴリズムの多項式PAC学習性に対する2つの非自明な応用を示す。
最初の1つは$k$-convex boolean関数の学習を扱っており、これは既にpac-learnableとして知られている。
汎用インテンションアルゴリズムを用いて, この正の結果を比較的容易に導出する方法を示す。
2つ目は、マンハッタン距離を備えたユークリッド空間に関するものである。
この距離空間に対して、弱凸集合は対に非随伴な軸方向の超矩形からなる和である。
弱凸集合が一組の例と一致し、多項式時間内に最小数の超矩形を含むことを示す。
対照的に、超矩形が重なり合う場合、この問題はNP完全であることが知られている。
関連論文リスト
- Convergence of Some Convex Message Passing Algorithms to a Fixed Point [0.0]
グラフィカルモデルにおけるMAP推論問題に対する一般的なアプローチは、双対線型計画法や(ブロック座標)降下によるラグランジュ緩和から得られる上限を最小化することである。
より強い結果(これは以前予想されたが、決して証明されなかった)を証明します。
本研究の主な結果とは対照的に,制約付き最適化問題に適用された座標降下の類似バージョンは収束しないことを示す。
論文 参考訳(メタデータ) (2024-03-07T13:14:21Z) - Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
2つの凸関数の和を最小化する自己協和スムージングの概念を導入し、そのうちの1つは滑らかであり、もう1つは非滑らかである。
本稿では, 近位ニュートンアルゴリズムであるProx-N-SCOREと近位一般化したガウスニュートンアルゴリズムであるProx-GGN-SCOREの2つのアルゴリズムの収束性を証明する。
論文 参考訳(メタデータ) (2023-09-04T19:47:04Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳(メタデータ) (2023-06-21T17:03:22Z) - Complexity of Block Coordinate Descent with Proximal Regularization and
Applications to Wasserstein CP-dictionary Learning [1.4010916616909743]
正規化(BCD-PR)によるGauss-Sdel型ブロック座標の導出について検討する。
W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W) W(W) W(W) W) W(W) W(W) W) W(W) W(W) W(W)
論文 参考訳(メタデータ) (2023-06-04T17:52:49Z) - Convex optimization over a probability simplex [0.0]
そこで我々は,確率的単純度よりも凸問題を最適化するために,新しい反復スキームCauchy-Simplexを提案する。
Cauchy-Simplex の各イテレーションは単純な操作で構成されており、高次元問題に適している。
論文 参考訳(メタデータ) (2023-05-15T22:14:22Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。
6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2022-05-21T01:47:17Z) - On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。
バイマックス性能問題を解くための優れた外挿が得られることが示されている。
論文 参考訳(メタデータ) (2022-01-19T16:14:27Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-01-19T04:24:23Z) - A Unified Single-loop Alternating Gradient Projection Algorithm for
Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。
提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
論文 参考訳(メタデータ) (2020-06-03T04:00:52Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。