論文の概要: Sublinear Time Algorithms for Several Geometric Optimization (With
Outliers) Problems In Machine Learning
- arxiv url: http://arxiv.org/abs/2301.02870v1
- Date: Sat, 7 Jan 2023 15:03:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-10 18:46:55.964947
- Title: Sublinear Time Algorithms for Several Geometric Optimization (With
Outliers) Problems In Machine Learning
- Title（参考訳）: 機械学習における幾何最適化問題に対する部分線形時間アルゴリズム
- Authors: Hu Ding
- Abstract要約: ユークリッド空間$mathbbRd$における最小閉球(MEB)問題を再考する。
本稿では,MEBの安定性の概念を紹介する。
安定仮定の下では、半径近似MEBの2つのサンプリングアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 8.794896028549323
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study several important geometric optimization problems
arising in machine learning. First, we revisit the Minimum Enclosing Ball (MEB)
problem in Euclidean space $\mathbb{R}^d$. The problem has been extensively
studied before, but real-world machine learning tasks often need to handle
large-scale datasets so that we cannot even afford linear time algorithms.
Motivated by the recent studies on {\em beyond worst-case analysis}, we
introduce the notion of stability for MEB, which is natural and easy to
understand. Roughly speaking, an instance of MEB is stable, if the radius of
the resulting ball cannot be significantly reduced by removing a small fraction
of the input points. Under the stability assumption, we present two sampling
algorithms for computing radius-approximate MEB with sample complexities
independent of the number of input points $n$. In particular, the second
algorithm has the sample complexity even independent of the dimensionality $d$.
We also consider the general case without the stability assumption. We present
a hybrid algorithm that can output either a radius-approximate MEB or a
covering-approximate MEB. Our algorithm improves the running time and the
number of passes for the previous sublinear MEB algorithms. Our method relies
on two novel techniques, the Uniform-Adaptive Sampling method and Sandwich
Lemma. Furthermore, we observe that these two techniques can be generalized to
design sublinear time algorithms for a broader range of geometric optimization
problems with outliers in high dimensions, including MEB with outliers,
one-class and two-class linear SVMs with outliers, $k$-center clustering with
outliers, and flat fitting with outliers. Our proposed algorithms also work
fine for kernels.
- Abstract（参考訳）: 本稿では,機械学習における幾何最適化問題について検討する。
まず、ユークリッド空間 $\mathbb{R}^d$ における最小閉球(MEB)問題を再考する。
この問題はこれまで広く研究されてきたが、現実の機械学習タスクは大規模なデータセットを扱う必要があり、線形時間アルゴリズムの余裕さえない。
最悪のケース解析以外の最近の研究に動機づけられ、自然で理解しやすいmebの安定性の概念が紹介される。
おおまかに言えば、MEBのインスタンスは安定であり、入力ポイントのごく一部を取り除くことで、結果のボールの半径が著しく減少できない場合である。
安定条件下では,入力点数に依存しないサンプル複素数を持つ半径近似 meb を2つのサンプリングアルゴリズムで計算する。
特に、第2のアルゴリズムは、次元$d$にさえ依存しないサンプル複雑性を持つ。
また、安定性の仮定のない一般の場合についても検討する。
本稿では,半径近似MEBと被覆近似MEBのどちらかを出力できるハイブリッドアルゴリズムを提案する。
提案アルゴリズムは,従来のサブ線形MEBアルゴリズムの動作時間とパス数を改善する。
本手法は一様適応サンプリング法とサンドイッチ補題という2つの新しい手法に依存している。
さらに,これら2つの手法を一般化して,高次元の異常値を持つより広い幾何学的最適化問題に対して,meb と 1-class と 2-class の線形 svm を外れ値付きで,k$-center を外れ値でクラスタリングし,フラットに外れ値と適合する部分線形時間アルゴリズムを設計することができることを示した。
提案アルゴリズムはカーネルにも有効である。
関連論文リスト
- Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization [26.36906884097317]
我々は,リプシッツ,凸関数を次数次オラクルで最小化するための新しい並列アルゴリズムを開発した。
その結果,最もよく知られた問合せ深度と並列アルゴリズムの最もよく知られた計算深度とのギャップを埋めることができた。
論文 参考訳（メタデータ） (2024-06-11T15:41:48Z) - A GPU-Accelerated Bi-linear ADMM Algorithm for Distributed Sparse Machine Learning [4.258375398293221]
Bi-cADMMは、計算ノードのネットワーク上で定義された大規模正規化されたスパース機械学習問題を解決することを目的としている。
Bi-cADMMはParallel Sparse Fitting Toolboxと呼ばれるオープンソースのPythonパッケージで実装されている。
論文 参考訳（メタデータ） (2024-05-25T15:11:34Z) - Randomized Algorithms for Symmetric Nonnegative Matrix Factorization [2.1753766244387402]
対称非負行列因子化(SymNMF)は、データ解析と機械学習における技術である。
計算のためのランダム化アルゴリズムを2つ開発した。
提案手法は, 解法の品質を概ね維持し, 大規模疎水化問題と大規模疎水化問題の両方に対して, 大幅な高速化を実現する。
論文 参考訳（メタデータ） (2024-02-13T00:02:05Z) - Efficient Algorithms for Sparse Moment Problems without Separation [6.732901486505047]
ノイズモーメント情報から高次元空間における$k$-spike混合を学習するスパースモーメント問題を考える。
以前のアルゴリズムは、特定の分離仮定を仮定するか、より多くのリカバリモーメントを使用するか、または(超)指数時間で実行します。
高次元の場合のアルゴリズムは、混合の1次元射影をランダムなベクトルと混合の2次元射影のセットに整列させることにより、各スパイクの座標を決定する。
論文 参考訳（メタデータ） (2022-07-26T16:17:32Z) - On a class of geodesically convex optimization problems solved via
Euclidean MM methods [50.428784381385164]
ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。
最終的に、より広い範囲、より広い範囲の作業を支援するのです。
論文 参考訳（メタデータ） (2022-06-22T23:57:40Z) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
共分散行列の明示的な構成を避ける新しい推論手法を提案する。
本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。
いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
論文 参考訳（メタデータ） (2022-02-25T16:35:26Z) - Covariance-Free Sparse Bayesian Learning [62.24008859844098]
共分散行列の明示的な反転を回避する新しいSBL推論アルゴリズムを導入する。
私たちの手法は、既存のベースラインよりも数千倍も高速です。
我々は,SBLが高次元信号回復問題に難なく対処できる新しいアルゴリズムについて紹介する。
論文 参考訳（メタデータ） (2021-05-21T16:20:07Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。