Related papers: Computing the Integral R2 Indicator by Perspective Mapping and Box Decomposition

Computing the Integral R2 Indicator by Perspective Mapping and Box Decomposition

URL: http://arxiv.org/abs/2606.30530v5
Date: Tue, 07 Jul 2026 13:24:24 GMT
Title: Computing the Integral R2 Indicator by Perspective Mapping and Box Decomposition
Abstract summary: This work introduces a bidirectional perspective mapping between continuous integral R2 computation and integration over unions of anchored axis-aligned boxes.<n>Hypervolume algorithms that emit box decompositions can be reused by replacing ordinary box volumes with closed-form weighted box integrals.
Score: 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.

Related papers

A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra [12.89814955033651]
We analyze exact-metric, Metropolis-adjusted Dikin walks by keeping the proposal determinant and reverse quadratic form together.<n>For a polytope given by $n$ inequalities and a $L$-Lipschitz potential, this yields warm-start mixing in $widetilde O((d2+dL2R2)log(w/)$ steps for the regularized Lee--Sidford walk.
arXiv Detail & Related papers (2026-08-26T01:18:00Z)
Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
arXiv Detail & Related papers (2026-07-28T09:29:37Z)
Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation [0.0]
This paper studies the problem for the integral R2 indicator in three objectives.<n>We show that the integral R2 improvement with respect to any fixed baseline is a monotone submodular set function.<n>We also give a tested greedy implementation that evaluates exact integral R2 values by subdivision.
arXiv Detail & Related papers (2026-06-25T04:25:20Z)
Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model [10.026496861838448]
We show that imposing elementwise $s$-sparsity on the cross-covariance $C_21$ can reduce the required communication and sample complexity.<n>We establish a matching scheme based on covering-net quantization and entry-wise hard thresholding, that attains the $s$-sparse lower bound up to polylogarithmic factors.
arXiv Detail & Related papers (2026-06-05T10:25:12Z)
Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
Estimating local mean curvature at each point of a high-dimensional dataset is a key ingredient of machine learning algorithms.<n>This paper introduces two complementary contributions that together reduce this cost by several orders of magnitude.<n> Experiments on real-world datasets confirm speedups of 50 to 300 times relative to the original implementation.
arXiv Detail & Related papers (2026-06-04T16:04:31Z)
Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
arXiv Detail & Related papers (2026-03-20T01:53:44Z)
An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
We recast qubit-efficient optimization as a geometry problem.<n>Local-consistency problem coincides exactly with the Sherali-Adams level-2 polytope $mathrmSA(2)$.
arXiv Detail & Related papers (2025-11-11T15:38:57Z)
Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
arXiv Detail & Related papers (2024-10-03T15:04:01Z)
Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
arXiv Detail & Related papers (2024-05-10T09:58:47Z)
Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
We consider the problem of partitioning a small data sample of size $n$ drawn from a mixture of 2 sub-gaussian distributions in $mathbbRp$.<n>We use semidefinite programming relaxations of an integer quadratic program that is formulated as finding the maximum cut on a graph.
arXiv Detail & Related papers (2024-01-16T03:14:24Z)
Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis [121.9821494461427]
We show how to significantly reduce the number of neurons required for two-layer ReLU networks. We also prove new lower bounds that improve upon prior work, and that under certain assumptions, are best possible.
arXiv Detail & Related papers (2022-06-26T06:51:31Z)
Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
arXiv Detail & Related papers (2020-07-16T06:44:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.