論文の概要: Optimal Reconstruction from Linear Queries

• arxiv url: http://arxiv.org/abs/2605.19625v1
• Date: Tue, 19 May 2026 10:04:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-20 15:03:09.270275
• Title: Optimal Reconstruction from Linear Queries
• Title（参考訳）: リニアクエリからの最適再構成
• Authors: Yuval Filmus, Shay Moran, Elizaveta Nesterova,
• Abstract要約: 近似線形クエリから$mathbbRd$の未知点を再構成する問題について検討する。 この設定は、低次元リモートセンシングや信号回復から高次元データ分析、プライバシーに敏感な推論まで、様々なアプリケーションで自然に発生する。
• 参考スコア（独自算出の注目度）: 22.749520200232624
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of reconstructing an unknown point in $\mathbb{R}^d$ from approximate linear queries. This setting arises naturally in applications ranging from low-dimensional remote sensing and signal recovery to high-dimensional data analysis and privacy-sensitive inference. Our main goal is to characterize the optimal reconstruction error as a function of the number of queries $T$, the ambient dimension $d$, and the noise parameter $δ$. We first analyze the limit $T \to \infty$ and show that the optimal reconstruction error converges to the explicit value $\sqrt{2d/(d+1)} δ$, which plays a role analogous to the Bayes optimal error in supervised learning. When the dimension is fixed, we show that the excess error above this limit decays doubly exponentially fast as $T \to \infty$, a rate that is significantly faster than those typically encountered in learning curves. When the dimension grows, we show that a number of queries on the order of $\exp(d)$ is necessary and sufficient to achieve vanishing excess error. Finally, we introduce and analyze an improper variant of the reconstruction problem. From a technical perspective, our main contribution is a generalization of Jung's theorem (1901). The classical theorem bounds the maximum possible radius of a set of diameter 1 and characterizes extremal bodies. Our generalization provides a robust variant that characterizes near-extremal bodies and is proved via geometric and dynamical arguments exploiting symmetry and Lie group actions.
• Abstract（参考訳）: 近似線形クエリから$\mathbb{R}^d$の未知点を再構成する問題を考察する。 この設定は、低次元リモートセンシングや信号回復から高次元データ分析、プライバシーに敏感な推論まで、様々なアプリケーションで自然に発生する。 我々の主な目標は、最適再構成エラーをクエリ数$T$、環境次元$d$、ノイズパラメータ$δ$の関数として特徴づけることです。 まず、極限$T \to \infty$ を解析し、最適再構成誤差が明示的な値 $\sqrt{2d/(d+1)} δ$ に収束することを示す。 次元が固定されたとき、この極限を超える過大な誤差は、学習曲線で見られるものよりもはるかに速い$T \to \infty$として指数関数的に高速に崩壊することを示す。 次元が大きくなると、$\exp(d)$の順番にあるクエリが必要で、余分なエラーを解消するのに十分であることを示す。 最後に,再建問題の不適切な変種を紹介し,解析する。 技術的な観点から、我々の主な貢献はユングの定理(1901年)の一般化である。 古典的な定理は、直径 1 の集合の最大半径を制限し、極小体を特徴づける。 我々の一般化は、極端に近い体を特徴づける頑健な不変量を提供し、対称性とリー群作用を利用する幾何学的および力学的な議論によって証明される。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• The power of small initialization in noisy low-tubal-rank tensor recovery [19.197039630139464]
  本研究では,低ツバルランクテンソル $mathcalX_starin mathbbRn times n times k$ を雑音線形測定から回収する問題について検討する。
  論文  参考訳（メタデータ） (2026-03-03T08:29:04Z)
• Parameter-free Algorithms for the Stochastically Extended Adversarial Model [59.81852138768642]
  拡張逆数(SEA)モデルの既存のアプローチは、ドメインの直径$D$や損失関数のリプシッツ定数$G$といった問題固有のパラメータの事前知識を必要とする。 パラメータを不要にするためにOptimistic Online Newton Step (OONS) アルゴリズムを利用するパラメータフリー手法を開発した。
  論文  参考訳（メタデータ） (2025-10-06T10:53:37Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  本稿では,テクスト幾何学的強単調ゲームに対する新たな収束結果を確立する。 我々のキーとなる結果は、RGDがテクスト幾何学的手法で最終定位線形収束を実現することを示しています。 全体として、ユークリッド設定を超えるゲームに対して、幾何学的に非依存な最終点収束解析を初めて提示する。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Restricted Strong Convexity of Deep Learning Models with Smooth Activations [31.003601717265006]
  本研究では,スムーズなアクティベーション機能を持つディープラーニングモデルの最適化問題について検討する。 Restricted Strong Convexity (RSC) に基づく最適化の新しい解析手法を提案する。 深層学習モデルのためのRCCに基づくGDの幾何収束性を確立するための最初の結果である。
  論文  参考訳（メタデータ） (2022-09-29T21:24:26Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  基本最小二乗構成におけるノイズレスモデルについて検討する。 最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
  論文  参考訳（メタデータ） (2021-02-05T14:02:20Z)
• Multiscale regression on unknown manifolds [13.752772802705978]
  マルチスケールで$mathcalM$に低次元座標を構築し、ローカルフィッティングによるマルチスケール回帰を行います。 本手法の一般化誤差を,事前のリッチクラス上で高い確率で有限サンプル境界を証明することによって解析する。 私たちのアルゴリズムは、サンプルサイズの準線形複雑性を持ち、定数は$D$で、指数は$d$です。
  論文  参考訳（メタデータ） (2021-01-13T15:14: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)

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

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