論文の概要: The Effectiveness of Johnson-Lindenstrauss Transform for High Dimensional Optimization With Adversarial Outliers, and the Recovery

• arxiv url: http://arxiv.org/abs/2002.11923v5
• Date: Sun, 21 Feb 2021 13:18:12 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-28 09:25:21.115523
• Title: The Effectiveness of Johnson-Lindenstrauss Transform for High Dimensional Optimization With Adversarial Outliers, and the Recovery
• Title（参考訳）: Johnson-Lindenstrauss変換の逆数外乱を用いた高次元最適化の有効性と回復
• Authors: Hu Ding, Ruizhe Qin, Jiawei Huang
• Abstract要約: 我々は2つの基本的な最適化問題に焦点をあてる: アウトリーチ付きSVMと、アウトリーチ付き$k$-centerクラスタリング。 これらの2つの問題の複雑さは、JL変換によって著しく低減できることを示す。 また、次元レデュース空間の解が元の$mathbbRd$で効率よく回収できることも証明する。
• 参考スコア（独自算出の注目度）: 23.700490046344264
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider robust optimization problems in high dimensions. Because a real-world dataset may contain significant noise or even specially crafted samples from some attacker, we are particularly interested in the optimization problems with arbitrary (and potentially adversarial) outliers. We focus on two fundamental optimization problems: {\em SVM with outliers} and {\em $k$-center clustering with outliers}. They are in fact extremely challenging combinatorial optimization problems, since we cannot impose any restriction on the adversarial outliers. Therefore, their computational complexities are quite high especially when we consider the instances in high dimensional spaces. The {\em Johnson-Lindenstrauss (JL) Transform} is one of the most popular methods for dimension reduction. Though the JL transform has been widely studied in the past decades, its effectiveness for dealing with adversarial outliers has never been investigated before (to the best of our knowledge). Based on some novel insights from the geometry, we prove that the complexities of these two problems can be significantly reduced through the JL transform. Moreover, we prove that the solution in the dimensionality-reduced space can be efficiently recovered in the original $\mathbb{R}^d$ while the quality is still preserved. In the experiments, we compare JL transform with several other well known dimension reduction methods, and study their performances on synthetic and real datasets.
• Abstract（参考訳）: 本稿では,高次元におけるロバスト最適化問題を考える。 実世界のデータセットには大きなノイズや攻撃者からの特別なサンプルが含まれている可能性があるため、我々は特に任意の(そして潜在的に敵対的な)アウトリーチによる最適化問題に興味を持っている。 我々は2つの基本的な最適化問題に焦点を絞った: "em svm with outliers} と "em $k$-center clustering with outliers} である。 実際、それらは相反する外れ値にいかなる制限も課せないため、組合せ最適化問題は非常に困難である。 したがって、高次元空間の例を考えると、それらの計算複雑性は非常に高い。 ジョンソン・リンデンシュトラウス変換 (JL) は次元減少の最も一般的な方法の1つである。 JL変換は、過去数十年にわたって広く研究されてきたが、敵の外れ値を扱う効果は、これまで(我々の知る限り)研究されていない。 幾何学からの新しい知見に基づき、これらの2つの問題の複雑さがJL変換によって著しく低減できることを証明した。 さらに,次元が縮小された空間の解は,元の$\mathbb{r}^d$ で効率的に回収できることを示した。 実験では、JL変換と、他のよく知られた次元還元法を比較し、それらの性能を合成および実データ上で研究する。

関連論文リスト

• Riemannian Projection-free Online Learning [5.918057694291832]
  プロジェクション操作は、オンライン勾配降下(OGD)のような最適化アルゴリズムにおける重要な要素である。 これは高次元の設定における計算上の制限や、不条件の制約セットを扱う際に悩まされる。 本稿では,曲面空間上でのオンライン測地線凸最適化において,線形後悔の保証を得る手法を提案する。
  論文  参考訳（メタデータ） (2023-05-30T18:22:09Z)
• Symmetrized Robust Procrustes: Constant-Factor Approximation and Exact Recovery [6.157087562708549]
  本稿では,ロバスト・プロクリストス問題に対する新しい凸緩和法を提案する。 提案手法は,標準の反復重み付き最小広場と同様の動作を示す。
  論文  参考訳（メタデータ） (2022-07-18T13:32:20Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。 最終的に、より広い範囲、より広い範囲の作業を支援するのです。
  論文  参考訳（メタデータ） (2022-06-22T23:57:40Z)
• Robust and Accurate Superquadric Recovery: a Probabilistic Approach [29.7543198254021]
  点雲から超四分儀を回収する最初の確率的手法を提案する。 提案手法は, 合成データセットと実世界のデータセットの精度, 効率, 堅牢性の観点から, 最先端の手法より優れている。
  論文  参考訳（メタデータ） (2021-11-29T13:17:17Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Learning to Guide Random Search [111.71167792453473]
  我々は、潜在低次元多様体上の高次元関数の微分自由最適化を考える。 最適化を行いながらこの多様体を学習するオンライン学習手法を開発した。 本研究では,連続最適化ベンチマークと高次元連続制御問題について実験的に評価する。
  論文  参考訳（メタデータ） (2020-04-25T19:21:14Z)
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives [50.12802772165797]
  平均化手法は、全ての反復解を一つの解に結合する。 実験は、他の平均化方式と比較して、トレードオフと平均化の有効性を示した。
  論文  参考訳（メタデータ） (2020-03-09T18:14:00Z)

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

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