論文の概要: Reconstruction and Secrecy under Approximate Distance Queries

• arxiv url: http://arxiv.org/abs/2511.06461v1
• Date: Sun, 09 Nov 2025 17:05:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-11 21:18:44.963864
• Title: Reconstruction and Secrecy under Approximate Distance Queries
• Title（参考訳）: 近似距離クエリによる再構築とセキュリティ
• Authors: Shay Moran, Elizaveta Nesterova,
• Abstract要約: 近い距離の問合せを用いて未知の目標点を探索する作業について検討する。 この問題は、GPSやセンサーネットワークのローカライゼーションからプライバシーに配慮したデータアクセスに至るまで、さまざまな状況で自然に発生する。 我々は,この再構成ゲームについて,学習理論レンズを用いて研究し,最良な再構成誤差の発生率と限界に着目した。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 各ラウンドでコンストラクタがクエリポイントを選択し、その距離のノイズバージョンをターゲットに受信する。 この問題は、GPSやセンサーネットワークのローカライズからプライバシーに配慮したデータアクセスに至るまで、さまざまな状況で自然に発生し、幅広い距離にまたがる。 リストストラクタ(正確なリカバリを探す)とレスポンダ(プライバシやセキュリティ上の理由から情報開示を制限する)の両方の観点から、これは関連性がある。 我々は,この再構成ゲームについて,学習理論レンズを用いて研究し,最良な再構成誤差の発生率と限界に着目した。 最初の結果は、幾何学からの古典的な概念であるチェビシェフ半径という観点から、最適誤差の厳密な幾何学的特徴を与える。 この特徴づけは、すべてのコンパクト距離空間(実際、すべての完全有界空間にも)に適用され、自然距離空間に対して明示的な公式を与える。 2つ目の結果は、有限個のクエリの後に最適な誤差が得られる擬有限空間と、近似曲線が非自明な崩壊を示す空間とを区別して、再構成の漸近的な振る舞いに対処する。 凸ユークリッド空間に対する擬有限性を特徴づける。

関連論文リスト

• Preserving Topological and Geometric Embeddings for Point Cloud Recovery [43.26116605528137]
  我々は、サンプリングおよび復元フェーズを通じてこれらの重要な特性を維持する、textbfTopGeoFormer というエンドツーエンドアーキテクチャを提案する。 実験では,従来型および学習型サンプリング/アップ/リカバリアルゴリズムを用いて,環境を包括的に分析する。
  論文  参考訳（メタデータ） (2025-07-25T09:58:41Z)
• Adaptive Locally Linear Embedding [10.331256742632835]
  適応的局所線形埋め込み(ALLE)という新しい手法が,この制限に対処するために導入された。 実験の結果,ALLEは入力空間と特徴空間の近傍のアライメントを著しく改善することが示された。 このアプローチは、基礎となるデータに距離メトリクスを合わせることで多様体学習を推進し、高次元データセットにおける複雑な関係をキャプチャするための堅牢なソリューションを提供する。
  論文  参考訳（メタデータ） (2025-04-09T12:40:13Z)
• Metric properties of partial and robust Gromov-Wasserstein distances [3.9485589956945204]
  グロモフ=ワッサーシュタイン距離(Gromov-Wasserstein distance, GW)は、最適な輸送のアイデアに基づいて、メトリクスの族を定義する。 GW距離は本質的に外れ音に敏感であり、部分的マッチングに対応できない。 我々の新しい距離は真の測度を定義し、それらがGW距離と同じ位相を誘導し、摂動にさらなる堅牢性をもたらすことを示す。
  論文  参考訳（メタデータ） (2024-11-04T15:53:45Z)
• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  乱れのないデータから歪んだ表現を学習することは、機械学習における根本的な課題である。 本稿では,2次最適輸送に基づく非交叉表現学習手法を提案する。 提案手法の有効性を4つの標準ベンチマークで示す。
  論文  参考訳（メタデータ） (2024-07-10T16:51:32Z)
• Information Entropy Initialized Concrete Autoencoder for Optimal Sensor Placement and Reconstruction of Geophysical Fields [58.720142291102135]
  そこで本稿では,スパーク計測による地場再構成のためのセンサ配置の最適化について提案する。 本研究では, (a) 温度と (b) バレンツ海周辺の塩分濃度場とスバルバルド諸島群を例に示す。 得られた最適センサ位置は, 物理的解釈が明確であり, 海流の境界に対応することが判明した。
  論文  参考訳（メタデータ） (2022-06-28T12:43:38Z)
• Surface Reconstruction from Point Clouds by Learning Predictive Context Priors [68.12457459590921]
  点雲からの表面の再構成は、3Dコンピュータビジョンにとって不可欠である。 推論時に各ポイントクラウドに対して予測的クエリを学習することで予測的コンテキスト優先を導入する。 一つの形状や複雑なシーンの表面再構成実験の結果, 広く使用されているベンチマークでは, 最先端のベンチマークよりも顕著な改善が見られた。
  論文  参考訳（メタデータ） (2022-04-23T08:11:33Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Manifold Learning via Manifold Deflation [105.7418091051558]
  次元削減法は、高次元データの可視化と解釈に有用な手段を提供する。 多くの一般的な手法は単純な2次元のマニフォールドでも劇的に失敗する。 本稿では,グローバルな構造を座標として組み込んだ,新しいインクリメンタルな空間推定器の埋め込み手法を提案する。 実験により,本アルゴリズムは実世界および合成データセットに新規で興味深い埋め込みを復元することを示した。
  論文  参考訳（メタデータ） (2020-07-07T10:04:28Z)

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

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