Optimal Reconstruction from Linear Queries

Technical Summary: Optimal Reconstruction from Linear Queries

Problem Formulation
This work investigates the problem of reconstructing an unknown point $x^* \in \mathbb{R}^d$ using approximate linear queries. The setting is formalized as an interactive game between a reconstructor and an adversary. In each round $t \in [T]$, the reconstructor submits a unit vector query $v_t \in \mathbb{R}^d$. The adversary responds with a value $r_t$ satisfying $|r_t - \langle v_t, x^* \rangle| \le \delta$, where $\delta > 0$ is a fixed additive noise parameter. The reconstructor aims to output an estimate $\hat{x}$ minimizing the worst-case $\ell_2$-distance $\|\hat{x} - x^*\|_2$. The central question is to characterize the optimal minimax reconstruction error, denoted $\text{OPT}_d(T, \delta)$, as a function of the noise $\delta$, the number of rounds $T$, and the ambient dimension $d$.

This problem models scenarios ranging from low-dimensional adaptive sensing to high-dimensional privacy-preserving data analysis, where linear queries probe a dataset with noise added to prevent sensitive information reconstruction. It differs from prior work on distance queries (e.g., Moran and Nesterova, 2025) by focusing on linear functionals rather than metric distances.

Methodology and Technical Tools
The analysis relies heavily on the geometry of the feasible region $\Phi_T$, defined as the intersection of strips consistent with the query transcript:
$$\Phi_T := \{ x \in \mathbb{R}^d : |\langle x, v_i \rangle - r_i| \le \delta, \forall i \in [T] \}.$$
The optimal reconstruction error is shown to be equivalent to the Chebyshev radius (the radius of the minimal enclosing ball) of this feasible region, $\text{rad}(\Phi_T)$.

The core technical contribution is a Robust Generalization of Jung's Theorem (1901).

• Classical Jung's Theorem: States that any set $S \subset \mathbb{R}^d$ with diameter $D$ has a Chebyshev radius at most $\text{Jung}_d \cdot D$, where $\text{Jung}_d = \sqrt{\frac{d}{2(d+1)}}$. Equality holds if and only if $S$ contains the vertices of a regular simplex of edge length $D$.
• Robust Variant: The authors prove that if a set $S$ has diameter slightly larger than 1 (specifically $1+\beta$) and a Chebyshev radius close to the extremal value $\text{Jung}_d$, then the "witnesses" (subsets of size $d+1$ that determine the radius) must cluster tightly around the vertex set of a single regular simplex. This result is proved using geometric arguments, dynamical systems, and Lie group actions to analyze the rigidity of regular simplices.

Key Results

1. Asymptotic Optimal Error (Main Theorem 1):
   As the number of rounds $T \to \infty$, the optimal reconstruction error converges to:
   $$\text{OPT}_d(\infty, \delta) = \sqrt{\frac{2d}{d+1}} \delta.$$
   This limit is analogous to the Bayes-optimal error in supervised learning. It is achieved by querying a dense net of directions, which bounds the diameter of the feasible region, and then applying Jung's theorem.

2. Doubly-Exponential Decay of Excess Error (Main Theorem 2):
   For fixed dimension $d \ge 2$, the excess error $\text{ExcessErr}_d(T, \delta) = \text{OPT}_d(T, \delta) - \text{OPT}_d(\infty, \delta)$ decays at a doubly exponential rate in $T$:
   $$\text{ExcessErr}_d(T, \delta) = 2^{-2\Theta_d(T)} \delta.$$

   • Upper Bound: The authors propose a two-phase algorithm. The first phase (preprocessing) queries a dense net to ensure the feasible region's diameter is small enough for the Robust Jung Theorem to apply. The second phase (refinement) adaptively queries directions parallel to the edges of the simplex identified by the witnesses. Each refinement step squares the current excess error, leading to the rapid convergence.
   • Lower Bound: An adversary strategy maintains a feasible region containing a "thickened" regular simplex. By carefully rotating the simplex at each step, the adversary ensures the excess error decays no faster than the doubly exponential rate.

3. Dimension-Dependent Query Budgets (Main Theorem 3):
   The paper characterizes the query complexity required to achieve vanishing excess error as $d \to \infty$:

   • If $T(d) = 2^{o(d)}$ (subexponential), the excess error diverges to infinity.
   • If $T(d) = 2^{\omega(d)}$ (superexponential), the excess error vanishes.
     This establishes that an exponential number of queries in $d$ is necessary and sufficient to control the diameter of the feasible region sufficiently for the refinement phase to begin.

4. Improper Reconstruction:
   The authors also analyze an "improper" variant where the reconstructor outputs a function $\hat{G}: S^{d-1} \to \mathbb{R}$ to predict future linear queries, rather than a single point.

   • The asymptotic limit is strictly lower: $\delta$ (compared to $\approx \sqrt{2}\delta$ in the proper setting).
   • However, the convergence rate is only polynomial in $T$ (specifically $O(T^{-2/(d-1)})$), significantly slower than the doubly exponential rate in the proper setting. This is because improper reconstruction depends directly on the diameter of the feasible region, which requires a dense net of queries to shrink, whereas proper reconstruction can exploit the geometric structure (Chebyshev radius) more efficiently once the diameter is bounded.

Significance and Claims
The paper claims to provide a complete characterization of the optimal reconstruction error for linear queries under adversarial noise.

• Theoretical Contribution: The generalization of Jung's theorem to a robust setting is presented as the primary technical innovation, enabling the proof of the doubly exponential convergence rate.
• Learning-Theoretic Insight: The work frames the problem as interactive learning, identifying the asymptotic limit as a "Bayes-optimal" baseline and demonstrating that interactive adaptivity can yield convergence rates (doubly exponential) far superior to typical learning curves.
• Dimensionality Gap: The results highlight a sharp threshold in query complexity relative to dimension, showing that while high-dimensional reconstruction is theoretically possible, it requires an exponential number of queries to even begin the rapid convergence phase.

The authors note that their techniques rely on the invariant that the secret point remains within the feasible region (adversarial noise is consistent). They leave open the extension to non-adaptive settings and settings with inconsistent (corrupted) answers.