Reconstruction and Secrecy under Approximate Distance Queries

• URL: http://arxiv.org/abs/2511.06461v1
• Date: Sun, 09 Nov 2025 17:05:01 GMT
• Title: Reconstruction and Secrecy under Approximate Distance Queries
• Authors: Shay Moran, Elizaveta Nesterova,
• Abstract summary: Consider the task of locating an unknown target point using approximate distance queries.<n>This problem arises naturally in various contexts ranging from localization in GPS and sensor networks to privacy-aware data access.<n>We study this reconstruction game through a learning-theoretic lens, focusing on the rate and limits of the best possible reconstruction error.
• Score: 22.236519193323378
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consider the task of locating an unknown target point using approximate distance queries: in each round, a reconstructor selects a query point and receives a noisy version of its distance to the target. This problem arises naturally in various contexts ranging from localization in GPS and sensor networks to privacy-aware data access, and spans a wide variety of metric spaces. It is relevant from the perspective of both the reconstructor (seeking accurate recovery) and the responder (aiming to limit information disclosure, e.g., for privacy or security reasons). We study this reconstruction game through a learning-theoretic lens, focusing on the rate and limits of the best possible reconstruction error. Our first result provides a tight geometric characterization of the optimal error in terms of the Chebyshev radius, a classical concept from geometry. This characterization applies to all compact metric spaces (in fact, even to all totally bounded spaces) and yields explicit formulas for natural metric spaces. Our second result addresses the asymptotic behavior of reconstruction, distinguishing between pseudo-finite spaces -- where the optimal error is attained after finitely many queries -- and spaces where the approximation curve exhibits nontrivial decay. We characterize pseudo-finiteness for convex Euclidean spaces.

Related papers

• Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds [57.179679246370114]
  We construct metrics that are geodesically complete while ensuring that every stationary point under the new metric remains stationary under the original one.<n>An $$-stationary point under the constructed metric $g'$ also corresponds to an $$-stationary point under the original metric $g'$.<n>Experiments on a practical mesh optimization task demonstrate that our framework maintains stable convergence even in the absence of geodesic completeness.
  arXiv  Detail & Related papers  (2026-01-12T22:08:03Z)
• Preserving Topological and Geometric Embeddings for Point Cloud Recovery [43.26116605528137]
  We propose an end-to-end architecture named textbfTopGeoFormer, which maintains these critical properties throughout the sampling and restoration phases.<n>In experiments, we comprehensively analyze the circumstances using the conventional and learning-based sampling/up/recovery algorithms.
  arXiv  Detail & Related papers  (2025-07-25T09:58:41Z)
• Adaptive Locally Linear Embedding [10.331256742632835]
  A novel approach, Adaptive locally linear embedding(ALLE), is introduced to address this limitation.<n> Experimental results demonstrate that ALLE significantly improves the alignment between neighborhoods in the input and feature spaces.<n>This approach advances manifold learning by tailoring distance metrics to the underlying data, providing a robust solution for capturing intricate relationships in high-dimensional datasets.
  arXiv  Detail & Related papers  (2025-04-09T12:40:13Z)
• Metric properties of partial and robust Gromov-Wasserstein distances [3.9485589956945204]
  The Gromov-Wasserstein (GW) distances define a family of metrics, based on ideas from optimal transport.<n>GW distances are inherently sensitive to outlier noise and cannot accommodate partial matching.<n>We show that our new distances define true metrics, that they induce the same topology as the GW distances, and that they enjoy additional robustness to perturbations.
  arXiv  Detail & Related papers  (2024-11-04T15:53:45Z)
• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning.<n>We introduce a novel approach to disentangled representation learning based on quadratic optimal transport.<n>We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
  arXiv  Detail & Related papers  (2024-07-10T16:51:32Z)
• Curved Geometric Networks for Visual Anomaly Recognition [39.91252195360767]
  Learning a latent embedding to understand the underlying nature of data distribution is often formulated in Euclidean spaces with zero curvature. In this work, we investigate benefits of the curved space for analyzing anomalies or out-of-distribution objects in data.
  arXiv  Detail & Related papers  (2022-08-02T01:15:39Z)
• Information Entropy Initialized Concrete Autoencoder for Optimal Sensor Placement and Reconstruction of Geophysical Fields [58.720142291102135]
  We propose a new approach to the optimal placement of sensors for reconstructing geophysical fields from sparse measurements. We demonstrate our method on the two examples: (a) temperature and (b) salinity fields around the Barents Sea and the Svalbard group of islands. We find out that the obtained optimal sensor locations have clear physical interpretation and correspond to the boundaries between sea currents.
  arXiv  Detail & Related papers  (2022-06-28T12:43:38Z)
• Surface Reconstruction from Point Clouds by Learning Predictive Context Priors [68.12457459590921]
  Surface reconstruction from point clouds is vital for 3D computer vision. We introduce Predictive Context Priors by learning Predictive Queries for each specific point cloud at inference time. Our experimental results in surface reconstruction for single shapes or complex scenes show significant improvements over the state-of-the-art under widely used benchmarks.
  arXiv  Detail & Related papers  (2022-04-23T08:11:33Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Manifold Learning via Manifold Deflation [105.7418091051558]
  dimensionality reduction methods provide a valuable means to visualize and interpret high-dimensional data. Many popular methods can fail dramatically, even on simple two-dimensional Manifolds. This paper presents an embedding method for a novel, incremental tangent space estimator that incorporates global structure as coordinates. Empirically, we show our algorithm recovers novel and interesting embeddings on real-world and synthetic datasets.
  arXiv  Detail & Related papers  (2020-07-07T10:04:28Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.