論文の概要: Computing the Integral R2 Indicator by Perspective Mapping and Box Decomposition

• arxiv url: http://arxiv.org/abs/2606.30530v2
• Date: Wed, 01 Jul 2026 15:26:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-02 15:15:53.069185
• Title: Computing the Integral R2 Indicator by Perspective Mapping and Box Decomposition
• Title（参考訳）: パースペクティブマッピングとボックス分解による積分R2指標の計算
• Abstract要約: この研究は、連続積分 R2 計算と固定軸整列箱の和集合上の積分の間の双方向の視点写像を導入する。 ボックス分解を出力するハイパーボリュームアルゴリズムは、通常のボックスボリュームを閉形式重み付きボックス積分に置き換えることで再利用することができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The continuous integral R2 indicator is a Pareto-compliant refinement of the classical finite-weight-vector R2 indicator, used in performance assessment, bounded archiving for a-posteriori multi-objective optimization, and skyline selection in databases. This work introduces a bidirectional perspective mapping between continuous integral R2 computation and integration over unions of anchored axis-aligned boxes. After translating the ideal point of a minimization problem to the origin, approximation points become strictly positive loss vectors, and the subgraph of the lower weighted Tchebycheff envelope over the weight simplex maps to the complement of an anchored-box union in reciprocal objective space. The Jacobian gives an absolute R2 formula as a weighted complement volume with density $(x_1+\cdots+x_N)^{-(N+1)}$, while differences of R2 values become finite weighted hypervolume differences. Hence, hypervolume algorithms that emit box decompositions can be reused by replacing ordinary box volumes with closed-form weighted box integrals. For $N$ objectives, this gives an output-sensitive overhead $O(2^N M)$ for an $M$-box decomposition, or $O(M)$ for fixed $N$. Using existing box-decomposition approaches, the integral R2 can be computed in $O(n \log n)$ for $N=2,3$, in $O(n^2)$ for $N=4$, and in $O\left(n^{\lfloor (N-1)/2\rfloor+1}\right)$ for $N\geq4$, with $n$ denoting the size of the approximation set. On the lower-bound side, exact value computation has an $Ω(n\log n)$ lower bound in the algebraic decision-tree model already in two objectives, this bound lifts to every fixed $N\geq2$, and exact computation is $\#P$-hard when $N$ is part of the input. Together, the proposed perspective mapping provides a powerful tool for transferring algorithmic and structural results between anchored-box union and hypervolume theory and integral R2 computation.
• Abstract（参考訳）: 連続積分R2インジケータは、古典的有限重ベクトルR2インジケータのパレート準拠の洗練であり、性能評価、アポテリオリ多目的最適化のための有界アーカイビング、およびデータベースにおけるスカイライン選択に用いられる。 この研究は、連続積分 R2 計算と固定軸整列箱の和集合上の積分の間の双方向の視点写像を導入する。 最小化問題の理想点を原点に変換した後、近似点は厳密な正の損失ベクトルとなり、重み付きチェビシェフエンベロープのグラフは、相互対象空間におけるアンカーボックスユニオンの補集合にマッピングされる。 ヤコビアン式は、密度$(x_1+\cdots+x_N)^{-(N+1)}$の重み付き補体積として絶対R2式を与えるが、R2値の差は有限重み付き超体積差となる。 したがって、ボックス分解を出力する超体積アルゴリズムは、通常のボックスボリュームを閉形式重み付きボックス積分に置き換えることで再利用することができる。 目標$N$の場合、$M$-box分解の場合は$O(2^N M)$、固定$N$の場合は$O(M)$となる。 既存のボックス分解法を用いて、積分 R2 は $O(n \log n)$ for $N=2,3$, inO(n^2)$ for $N=4$, inO\left(n^{\lfloor (N-1)/2\rfloor+1}\right)$ for$N\geq4$, with $n$ で計算できる。 ローバウンド側では、正確な値計算は代数的決定木モデルにおいて既に2つの目的において$Ω(n\log n)$低いバウンドを持ち、このバウンドは固定された$N\geq2$ごとに持ち上げられ、正確な計算は$N$が入力の一部であるときに$\#P$-hardである。 提案したパースペクティブマッピングは、アンカーボックス結合とハイパーボリューム理論と積分R2計算の間のアルゴリズム的および構造的結果を伝達する強力なツールを提供する。

関連論文リスト

• A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra [12.89814955033651]
  提案した2次形式と逆2次形式を両立させることにより、正確なメトロポリス調整ダイキンウォークを解析する。 n$不等式と$L$-Lipschitzポテンシャルで与えられるポリトープの場合、これは正規化されたリー-シドフォード・ウォークに対して、$widetilde O((d2+dL2R2)log(w/)$の温度開始混合をもたらす。
  論文  参考訳（メタデータ） (2026-08-26T01:18:00Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation [0.0]
  本稿では3つの目的において積分R2インジケータの問題点を考察する。 任意の固定基底線に対する積分 R2 の改善は単調部分モジュラー集合函数であることを示す。 また, 完全積分 R2 値を部分分割で評価するグリージーな実装も提案する。
  論文  参考訳（メタデータ） (2026-06-25T04:25:20Z)
• Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model [10.026496861838448]
  相互共分散の$C_21$に対して$s$-sparsityを要素的に課すことで、必要な通信やサンプルの複雑さを低減できることを示す。 被覆ネット量子化とエントリーワイドのハードしきい値化に基づくマッチングスキームを構築し,ポリ対数因子までの$s$スパースな下界を実現する。
  論文  参考訳（メタデータ） (2026-06-05T10:25:12Z)
• Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
  高次元データセットの各点における局所的な平均曲率の推定は、機械学習アルゴリズムの重要な要素である。 本稿では,このコストを桁違いに削減する2つの補完的貢献を紹介する。 実世界のデータセットの実験では、オリジナルの実装と比較して50倍から300倍のスピードアップが確認されている。
  論文  参考訳（メタデータ） (2026-06-04T16:04:31Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。 我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
  論文  参考訳（メタデータ） (2026-03-20T01:53:44Z)
• An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
  量子ビット効率の最適化を幾何学的問題として再検討する。 局所一貫性問題は、Sherali-Adams level-2 polytope $mathrmSA(2)$とちょうど一致する。
  論文  参考訳（メタデータ） (2025-11-11T15:38:57Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。 グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
  論文  参考訳（メタデータ） (2024-01-16T03:14:24Z)
• Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis [121.9821494461427]
  2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。 また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
  論文  参考訳（メタデータ） (2022-06-26T06:51:31Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)

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

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