論文の概要: The Hypervolume Indicator Hessian Matrix: Analytical Expression, Computational Time Complexity, and Sparsity

• arxiv url: http://arxiv.org/abs/2211.04171v1
• Date: Tue, 8 Nov 2022 11:24:18 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-09 17:13:02.429939
• Title: The Hypervolume Indicator Hessian Matrix: Analytical Expression, Computational Time Complexity, and Sparsity
• Title（参考訳）: 超体積指標ヘッセン行列:解析的表現、計算時間複雑度、空間性
• Authors: Andr\'e H. Deutz, Michael T.M. Emmerich, Hao Wang
• Abstract要約: 本稿では,$d$次元決定空間における$n$点の(固定サイズ)集合からスカラー超体積指標値への写像のヘッセン行列の解析式を確立する。 ヘッセン行列はニュートン・ラフソン最適化法のような二階法において重要な役割を担い、局所最適集合の検証に使用できる。
• 参考スコア（独自算出の注目度）: 4.523133864190258
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of approximating the Pareto front of a multiobjective optimization problem can be reformulated as the problem of finding a set that maximizes the hypervolume indicator. This paper establishes the analytical expression of the Hessian matrix of the mapping from a (fixed size) collection of $n$ points in the $d$-dimensional decision space (or $m$ dimensional objective space) to the scalar hypervolume indicator value. To define the Hessian matrix, the input set is vectorized, and the matrix is derived by analytical differentiation of the mapping from a vectorized set to the hypervolume indicator. The Hessian matrix plays a crucial role in second-order methods, such as the Newton-Raphson optimization method, and it can be used for the verification of local optimal sets. So far, the full analytical expression was only established and analyzed for the relatively simple bi-objective case. This paper will derive the full expression for arbitrary dimensions ($m\geq2$ objective functions). For the practically important three-dimensional case, we also provide an asymptotically efficient algorithm with time complexity in $O(n\log n)$ for the exact computation of the Hessian Matrix' non-zero entries. We establish a sharp bound of $12m-6$ for the number of non-zero entries. Also, for the general $m$-dimensional case, a compact recursive analytical expression is established, and its algorithmic implementation is discussed. Also, for the general case, some sparsity results can be established; these results are implied by the recursive expression. To validate and illustrate the analytically derived algorithms and results, we provide a few numerical examples using Python and Mathematica implementations. Open-source implementations of the algorithms and testing data are made available as a supplement to this paper.
• Abstract（参考訳）: 多目的最適化問題のパレートフロントを近似する問題は、ハイパーボリュームインジケータを最大化する集合を見つける問題として再構成することができる。 本稿では,d$-dimensional decision space (または$m$ dimensional objective space) における n$ 個の点からなる (固定サイズ) 集合からスカラーハイパーボリュームインジケータ値への写像のヘッセン行列の解析的表現を確立する。 ヘッセン行列を定義するために、入力集合はベクトル化され、行列はベクトル化集合から超体積指標への写像の解析的微分によって導出される。 ヘッセン行列はニュートン・ラフソン最適化法のような二階法において重要な役割を担っており、局所最適集合の検証に使うことができる。 これまでのところ, 完全解析式は, 比較的単純な二重対象の場合に対してのみ確立され, 解析された。 本稿では任意の次元(m\geq2$ objective function)の式を導出する。 実際に重要な3次元の場合、ヘッセン行列の非零成分の正確な計算のために、o(n\log n)$ の時間複雑性を持つ漸近的に効率的なアルゴリズムを提供する。 非ゼロなエントリの数に対して、1,12m-6$のシャープなバウンドを確立する。 また、一般の$m$-次元の場合、コンパクトな再帰的解析式を確立し、そのアルゴリズム的実装について論じる。 また, 一般の場合においても, 再帰的な表現によって, 疎結合の結果が確立される。 解析的に導出されたアルゴリズムと結果の検証と説明のために,Python と Mathematica の実装を用いて数値的な例を示す。 本論文のサプリメントとして,アルゴリズムとテストデータのオープンソース実装が利用可能である。

関連論文リスト

• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
  ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。 第一のアルゴリズムは真の解に線形に収束する。 第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
  論文  参考訳（メタデータ） (2024-10-08T21:19:22Z)
• 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)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Low-complexity subspace-descent over symmetric positive definite manifold [9.346050098365648]
  対称正定値多様体(SPD)上の関数の最小化のための低複素性アルゴリズムを開発する。 提案手法は、慎重に選択された部分空間を利用して、更新をイテレートのコレスキー因子とスパース行列の積として記述することができる。
  論文  参考訳（メタデータ） (2023-05-03T11:11:46Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Approximate Vanishing Ideal Computations at Scale [21.01267270902429]
  私たちはOracle Approximate Vanishing Idealアルゴリズム(OAVI)のスケールアップに注力しています。 OAVIは大規模機械学習のための魅力的な前処理技術である。
  論文  参考訳（メタデータ） (2022-07-04T07:17:28Z)
• Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
  整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。 大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
  論文  参考訳（メタデータ） (2022-05-16T02:24:52Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。 我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
  論文  参考訳（メタデータ） (2022-02-09T15:26:03Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。 次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
  論文  参考訳（メタデータ） (2021-03-24T23:11:32Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)

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

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