論文の概要: Approximate Vanishing Ideal Computations at Scale

• arxiv url: http://arxiv.org/abs/2207.01236v1
• Date: Mon, 4 Jul 2022 07:17:28 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-05 16:53:21.299614
• Title: Approximate Vanishing Ideal Computations at Scale
• Title（参考訳）: スケールで理想的な計算を行う近似
• Authors: Elias Wirth, Hiroshi Kera, Sebastian Pokutta
• Abstract要約: 私たちはOracle Approximate Vanishing Idealアルゴリズム(OAVI)のスケールアップに注力しています。 OAVIは大規模機械学習のための魅力的な前処理技術である。
• 参考スコア（独自算出の注目度）: 21.01267270902429
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The approximate vanishing ideal of a set of points $X = \{\mathbf{x}_1, \ldots, \mathbf{x}_m\}\subseteq [0,1]^n$ is the set of polynomials that approximately evaluate to $0$ over all points $\mathbf{x} \in X$ and admits an efficient representation by a finite set of polynomials called generators. Algorithms that construct this set of generators are extensively studied but ultimately find little practical application because their computational complexities are thought to be superlinear in the number of samples $m$. In this paper, we focus on scaling up the Oracle Approximate Vanishing Ideal algorithm (OAVI), one of the most powerful of these methods. We prove that the computational complexity of OAVI is not superlinear but linear in the number of samples $m$ and polynomial in the number of features $n$, making OAVI an attractive preprocessing technique for large-scale machine learning. To further accelerate OAVI's training time, we propose two changes: First, as the name suggests, OAVI makes repeated oracle calls to convex solvers throughout its execution. By replacing the Pairwise Conditional Gradients algorithm, one of the standard solvers used in OAVI, with the faster Blended Pairwise Conditional Gradients algorithm, we illustrate how OAVI directly benefits from advancements in the study of convex solvers. Second, we propose Inverse Hessian Boosting (IHB): IHB exploits the fact that OAVI repeatedly solves quadratic convex optimization problems that differ only by very little and whose solutions can be written in closed form using inverse Hessian information. By efficiently updating the inverse of the Hessian matrix, the convex optimization problems can be solved almost instantly, accelerating OAVI's training time by up to multiple orders of magnitude. We complement our theoretical analysis with extensive numerical experiments on data sets whose sample numbers are in the millions.
• Abstract（参考訳）: 点の集合 $X = \{\mathbf{x}_1, \ldots, \mathbf{x}_m\}\subseteq [0,1]^n$ の近似消滅イデアルは、すべての点$\mathbf{x} \in X$ に対しておよそ 0$ と評価され、生成元と呼ばれる多項式の有限集合による効率的な表現を認める多項式の集合である。 この生成器の集合を構成するアルゴリズムは広範囲に研究されているが、計算の複雑さはサンプル数$m$で超線形であると考えられるため、結局は実用的でない。 本稿では,Oracle Approximate Vanishing Idealアルゴリズム(OAVI)のスケールアップに注力する。 oaviの計算複雑性は超線形ではなく、サンプル数 m$ と多項式数 n$ で線形であることが証明され、大規模機械学習のための魅力的な前処理技術となる。 OAVIのトレーニング時間をさらに加速するために、私たちは2つの変更を提案する。 OAVIの標準解法の一つであるPairwise Conditional Gradientsアルゴリズムを、より高速なBlended Pairwise Conditional Gradientsアルゴリズムに置き換えることで、OAVIが凸解法の研究の進歩から直接恩恵を受けるかを説明する。 Inverse Hessian Boosting (IHB): IHB は OAVI が2次凸最適化の問題を繰り返し解決し,その解が逆 Hessian 情報を用いて閉じた形で書けることを活用する。 ヘッセン行列の逆数を効率的に更新することにより、凸最適化問題をほぼ瞬時に解き、OAVIのトレーニング時間を最大で複数の桁に短縮することができる。 我々は、サンプル数が数百万であるデータセットに関する広範な数値実験で理論解析を補完する。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization [25.438298531555468]
  双レベル最適化は、ハイパーラーニング、メタラーニング、強化ラーニングなど、多くの機械学習タスクに広く適用されている。 最適収束$frac1TT(Hessian/BiO法)を軽度条件下で提案する。 バイレベルゲーム超定常数値収束に関するいくつかの実験を行う。
  論文  参考訳（メタデータ） (2024-07-25T07:25:06Z)
• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。 結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
  論文  参考訳（メタデータ） (2024-05-09T14:56:49Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• The Hypervolume Indicator Hessian Matrix: Analytical Expression, Computational Time Complexity, and Sparsity [4.523133864190258]
  本稿では,$d$次元決定空間における$n$点の(固定サイズ)集合からスカラー超体積指標値への写像のヘッセン行列の解析式を確立する。 ヘッセン行列はニュートン・ラフソン最適化法のような二階法において重要な役割を担い、局所最適集合の検証に使用できる。
  論文  参考訳（メタデータ） (2022-11-08T11:24:18Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning [12.069630105460766]
  AltGDA(Alternating Table-descentascent)は、様々な機械学習アプリケーションで広く使われている計算最適化アルゴリズムである。 本論文では,最小限の最適化問題を解くために,単一ループの高速なループ勾配計算アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-12-22T04:33:27Z)
• BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
  バイレベル最適化は多くの応用のために機械学習への関心が高まっている。 制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-06-21T20:16:40Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

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

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