PaperlayerView exact revision on arXiv

Source-linked AI summary

Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework

Junren Chen, Arian Maleki

arXiv:2609.02120v1cs.ITeess.SPmath.ST

TL;DR

Nonlinear observations make instance-optimal sparse recovery challenging, especially when exact recovery is impossible. The paper introduces a signal-dependent RAIC framework and obtains instance-optimal guarantees across three nonlinear recovery problems, with sparse phase retrieval using O(s^3) measurements up to logarithmic factors.

  • Problem

    Instance-optimal sparse recovery is well established for linear measurements, but nonlinear settings such as one-bit sensing and phase retrieval require robust error guarantees because exact recovery may be impossible.

  • Method

    The paper uses a signal-dependent restricted approximate invertibility condition for suitable gradients to establish instance optimality of iterative hard thresholding.

  • Results

    The framework yields instance-optimal guarantees for sparse phase retrieval, one-bit compressed sensing, and sparse ReLU regression under Gaussian designs, with sparse phase retrieval requiring s^3 samples.

  • Takeaways & Limitations

    The results provide a unified route to instance-optimal sparse recovery guarantees for several nonlinear measurement models.

  • Takeaways & Limitations

    An extra logarithmic factor appears in the model-error term, and whether it can be removed remains an open question.

Abstract

from arXiv · show

This paper develops a unified framework for instance optimal sparse recovery from nonlinear observations. The main ingredient is a signal-dependent restricted approximate invertibility condition (RAIC) of some gradient, which leads to the instance optimality of iterative hard thresholding. Under Gaussian designs, we apply the proposed framework to phaseless, one-bit, and ReLU measurements, which correspond to the problems of sparse phase retrieval, one-bit compressed sensing, and sparse ReLU regression, respectively. For sparse phase retrieval, we propose a variant of thresholded amplitude flow and show its instance optimality under $O(s^3)$ measurements (up to logarithmic factors), where $s$ is the sparsity level. To our best knowledge, this is the first instance optimal efficient algorithm for sparse phase retrieval and complements Gao, Wang and Xu (2016) that achieved this via a computationally intractable program. In one-bit compressed sensing, we establish the instance optimality of normalized binary iterative hard thresholding and strengthen the recent result of Matsumoto and Mazumdar (2024). In sparse ReLU regression, it is shown that a slight variant of the algorithm in Soltanolkotabi (2017) is instance optimal. Moreover, $(\ell_2,\ell_2)$ non-uniform instance optimal guarantees are obtained for these problems. The analysis is built upon a number of high-dimensional concentration bounds, including bounds on restricted eigenvalues and a novel instance-dependent hyperplane tessellation result.

1 Introduction

The paper asks how to achieve instance-optimal sparse recovery from nonlinear observations when signals are only approximately sparse and exact recovery may be impossible. It develops a unified RAIC-based framework for efficient IHT-type algorithms and applies it to several nonlinear recovery problems.

  • Motivation: Instance optimality measures robustness to model error by bounding recovery error proportionally to a signal’s distance from its best s-sparse approximation.For nonlinear problems, the attainable guarantee may be statistical optimality rather than exact recovery, even for s-sparse signals.
  • Unified framework: A signal-dependent restricted approximate invertibility condition on the problem-specific gradient directly yields instance optimality for IHT over signals suitably close to the sparse set.The framework decomposes the signal space into signals close to Σn_s and its complement, extending prior RAIC control beyond exactly sparse pairs.
  • Applications: The framework establishes instance-optimal IHT-type algorithms for sparse phase retrieval, one-bit compressed sensing, and ReLU regression under Gaussian designs.These nonlinear observations include y = |Ax| and y = sign(Ax), with ReLU regression as a third application.
  • Sparse phase retrieval: ˜O(s^3) measurements yield uniform instance-optimal guarantees for an efficient sparse phase-retrieval solver based on a variant of thresholded amplitude flow.The phase-retrieval error uses dist(u, v) = min{∥u + v∥2, ∥u − v∥2}; the fixed-signal counterpart requires ˜O(s^2) measurements.
  • One-bit compressed sensing: Normalized binary iterative hard thresholding achieves instance optimality for one-bit compressed sensing, with a logarithmic factor in the model-error term.The method is essentially normalized IHT with the ReLU loss, and the factor is log(1 / (∥x−x[s]∥1/√s ∧ 1/2)).
  • Analysis: The analysis combines concentration, embedding, restricted-eigenvalue, and hyperplane-tessellation bounds to obtain nonlinear guarantees comparable to classical compressed sensing.Some ingredients, including Lemma D.2, are presented as new and potentially independently useful.

2 Unified Framework

The framework uses signal-dependent RAIC conditions on gradient maps to establish linear convergence and instance-optimal recovery for IHT and normalized IHT. It decomposes signals into approximately sparse and complementary classes, yielding uniform and non-uniform error guarantees.

  • Algorithmic framework: IHT updates x_{t+1} = H_s(x_t − η · h_x(x_t)), while unit-sphere signals additionally use normalization through NIHT.The gradient map h_x serves as the gradient at the current iterate.
  • RAIC and convergence: An RAIC with a sufficiently large constraint set and error function μ1∥u − x∥2 + μ2 yields linear convergence of (N)IHT with proper initialization.The convergence results are stated separately for IHT and NIHT.
  • Uniform instance optimality: The uniform guarantee decomposes recovery error into exponentially decaying optimization error, signal-independent statistical error, and instance-optimal error.The optimization term is Eopt(t; x) = O(ρ^t∥x∥2) for some ρ ∈ (0, 1).
  • Proof scheme: The framework treats approximately sparse signals through signal-dependent RAIC and handles the complementary class with a separate, simpler argument and algorithmic regularization when needed.For approximately sparse signals, the error function depends on the signal through e(x).
  • Non-uniform guarantees: For fixed signals, non-uniform instance optimality retains the same three-term error decomposition but can provide a sharper model-error term than the uniform guarantee.This guarantee is weaker because it covers only a fixed x.

3 Sparse Phase Retrieval

This section introduces bounded thresholded amplitude flow (BTAF), the first efficient instance-optimal algorithm proposed for sparse phase retrieval, and establishes uniform and fixed-signal guarantees under Gaussian measurements. Uniform instance optimality requires ˜O(s^3) measurements, while the non-uniform fixed-signal guarantee requires ˜O(s^2) measurements and improves the model-error term.

  • Algorithm: BTAF is a variant of thresholded amplitude flow designed for sparse phase retrieval from Gaussian measurements.The algorithm combines amplitude-based IHT with spectral initialization and an additional projection.
  • Uniform instance optimality: ˜O(s^3) Gaussian measurements yield uniform instance optimality for BTAF.The analysis applies to approximately sparse signals, including all x ∈ R^n in sparse phase retrieval.
  • Uniform instance optimality: The ˜O(s^3) complexity remains an open improvement gap relative to the best known ˜O(s^2) for efficient exact recovery of arbitrary s-sparse signals.The paper identifies whether efficient and instance-optimal sparse phase retrieval can improve ˜O(s^3) as an open question.
  • Non-uniform instance optimality: ˜O(s^2) measurements provide non-uniform instance optimality for any fixed signal x ∈ R^n.Theorem 3.2 gives the guarantee under m ≳ s^2 log n with the stated high probability.
  • Non-uniform instance optimality: The fixed-signal guarantee tightens the model-error term from O(τ_s(x)) to O(δ_s(x)).This improvement follows because the RAIC and initialization bounds only need to hold for a fixed x.

4 One-Bit Compressed Sensing

This section establishes instance-optimal recovery for normalized binary iterative hard thresholding (NBIHT) in one-bit compressed sensing, viewing NBIHT as an instance of NIHT with a ReLU loss. It also presents an instance-dependent hyperplane tessellation bound that preserves the optimal statistical rate and gives a non-uniform guarantee without a logarithmic loss in the model-error term.

  • Algorithm: The ReLU loss used by NBIHT is a convex relaxation of the Hamming-distance loss, with a corresponding subgradient driving the iteration.The section specializes NIHT to normalized binary iterative hard thresholding through the chosen loss and step-size construction.
  • Main result: NBIHT is established as an instance-optimal algorithm for recovering sparse unit-norm signals from Gaussian one-bit measurements.The measurements are y = sign(Ax), with A Gaussian, and NBIHT is identified as a specific instance of the unified NIHT algorithm.
  • Main result: One-bit measurements cannot perfectly recover x, so the error includes a statistical term O(√(s/m)) that is optimal up to logarithmic factors.The statistical error reflects the inherent limitation of one-bit observations, even for exactly sparse signals.
  • Main result: Theorem 4.1 upgrades Matsumoto and Mazumdar’s result to instance optimality, while the model-error bound retains an extra logarithmic factor whose removal remains open.The section identifies NBIHT as an efficient algorithm attaining the rate ˜O(√(s/m)) and notes that the additional logarithmic factor arises in the model error.
  • Technical contribution: A novel instance-dependent hyperplane tessellation bound achieves a constant term ˜O(s/m), improving on ˜O((s/m)1/4) and retaining the optimal statistical error.The sharper bound trades an O(∥x − x[s]∥2) model-error term for ˜O(τs(x)), consistently up to logarithmic factors with related instance-optimal results.
  • Non-uniform guarantee: Theorem 4.2 gives non-uniform instance optimality for a fixed x and does not lose a logarithmic factor in the model-error term.This non-uniform result is contrasted with Theorem 4.1 and yields faster rates for signals satisfying the stated δs(x) condition.

5 Sparse ReLU Regression

For sparse ReLU regression, the paper introduces bounded ReLU iterative hard thresholding (BReLUIHT), a projected-gradient variant with an additional projection to control iterates. It establishes uniform and fixed-signal instance-optimal recovery guarantees under Gaussian designs.

  • Problem setup: Sparse ReLU regression recovers an s-sparse x from measurements y = ReLU(Ax), with ReLU(a) = max{a, 0} = a+|a|.The signal model is x ∈ Rn with an s-sparse prior.
  • Algorithm: BReLUIHT is a slight projected-gradient variant using a ReLU-based ℓ2 loss, fixed step size η = 1, and an additional projection for bounded iterates.The method uses 2∥x0∥2 as a crude upper bound on ∥x∥2 before projecting onto a suitable ball.
  • Uniform recovery: The main result establishes instance optimality of BReLUIHT for sparse ReLU regression.This provides the analogue of the paper’s general instance-optimality guarantee for this measurement model.
  • Uniform recovery: Under Gaussian A, the uniform guarantee holds when m ≳ s log(en/s), with probability at least 1 − C exp(−c s log(en/s)) and error bound 2t + C2τs(x).The guarantee holds for all t ≥ 0 and x ∈ Rn.
  • Non-uniform recovery: For any fixed x under Gaussian A, the non-uniform guarantee also requires m ≳ s log(en/s), with probability at least 1 − C exp(−c s log(en/s)) and error bound 2t + C2δs(x).The result holds for all t ≥ 0.

6 Conclusion · A Proofs for Convergence of IHT and NIHT

The paper develops a general framework for instance-optimal sparse recovery from nonlinear measurements, using a signal-dependent RAIC for a suitable gradient map to establish instance optimality of IHT. Its convergence proofs control post-hard-thresholding error through the top-2s ℓ2 norm and best s-sparse approximation properties.

  • 6 Conclusion: The framework targets instance optimality, a notion characterizing algorithm robustness to model error in compressed sensing.Its non-uniform counterpart also connects naturally to oracle inequalities in statistics.
  • 6 Conclusion: A signal-dependent RAIC for a suitable gradient map is the framework’s main ingredient for establishing instance optimality of IHT.
  • A Proofs for Convergence of IHT and NIHT: The convergence proof begins with a lemma controlling post-hard-thresholding error by the top-2s ℓ2 norm.
  • A Proofs for Convergence of IHT and NIHT: For supports of Hs(u) and a comparison vector v, the proof represents the relevant restriction using their union.The restriction involves the support sets T1 and T2 of Hs(u) and v.
  • A Proofs for Convergence of IHT and NIHT: Hs(u) is the best s-sparse approximation to its restriction on the union of the two supports.
  • A Proofs for Convergence of IHT and NIHT: The proof bounds the restricted difference by the full difference, yielding ∥v − uT1∪T2∥2 ≤ ∥u − v∥2,2s.

A.1 Proofs of Theorems 2.1–2.2 (Convergence of IHT and NIHT) … C.1.2 Proof of the Initialization Guarantee (3.7)

The proofs establish geometric error control for IHT and NIHT, then develop the Gaussian-width, restricted-eigenvalue, RAIC, and initialization ingredients used for sparse phase retrieval. The sparse phase-retrieval analysis decomposes the RAIC and bounds its components using prior RAIC results, Gaussian estimates, and concentration-based inequalities.

  • A.1 Proofs of Theorems 2.1–2.2 (Convergence of IHT and NIHT): The resulting error sequence satisfies f_0=∥x_0−x∥2 and f_{t+1}=ρf_t+b, yielding f_t≤ρ^t∥x_0−x∥2+b/(1−ρ).The one-step estimate follows from triangle inequalities, Lemma A.1, and the assumed RAIC.
  • B Gaussian Width and Covering Number: Section B introduces Gaussian width and covering numbers, with log N(U,r) identified as the metric entropy of U at radius r.These quantities collect the geometric estimates used in subsequent concentration lemmas.
  • C Proofs for Sparse Phase Retrieval: The sparse phase-retrieval proofs define a structured set X and invoke Gaussian-matrix restricted-eigenvalue bounds as foundational estimates.The set is X={u∈R^n:τ_s(u)≤c*∥u∥2} for sufficiently small c*>0.
  • C.1.1 Proof of the RAIC in (3.6): To prove the RAIC in (3.6), the analysis begins with a decomposition that separates the terms requiring control.The decomposition is the starting point for the subsequent bounds.
  • (i) Bounding ∥u −x[s] −hx[s](u)∥2s,2: For the first RAIC component, both u and x[s] are s-sparse, enabling use of the RAIC established in [18] to control ∥u−x[s]−h_x[s](u)∥_{2s,2}.The argument applies [18, Theorem B.9] together with estimates (B.2)–(B.3), under a sufficiently small universal constant.
  • (ii) Bounding ∥hx(u) −hx[s](u)∥2s,2: The second RAIC component, ∥h_x(u)−h_x[s](u)∥_{2s,2}, is bounded through truncation decomposition, Cauchy–Schwarz, Γ_s(·), and a Gaussian-matrix lemma.Substitution into the decomposition and ∥x−x[s]∥2≤τ_s(x) yields (C.3).
  • C.1.2 Proof of the Initialization Guarantee (3.7): The initialization proof normalizes x, computes E[˜S_x] using rotational invariance of a_i, and identifies universal constants c♭≈0.7809 and c⋄≈0.6899.It establishes the remaining condition needed for (2.12).

(iii) A Deterministic Initialization Error Bound … C.2 Proof of Theorem 3.2 (Non-Uniform Instance Optimality)

The proof establishes a deterministic initialization error bound, shows projection does not alter the relevant iterates, and combines these ingredients with RAIC and a separate complement argument to obtain non-uniform instance optimality.

  • (iii) A Deterministic Initialization Error Bound: For nonzero signals with sufficiently small τs(x)/∥x∥2, initialization satisfies dist(x0, x) ≲ √¯c∥x∥2.The bound follows from controlling support mismatch and leading-eigenvector perturbation, with Davis–Kahan’s theorem used for the latter.
  • (iii) A Deterministic Initialization Error Bound: The initialization analysis combines eigenvalue-gap control with high-probability concentration bounds over the signal and sparse-index classes.The proof uses truncation, symmetrization, contraction, Massart’s inequality, and Gaussian empirical quadratic-form bounds.
  • C.1.3 Projection Has No Effect on x ∈X: For iterates satisfying (3.8), the additional projection onto B_n(2λx) has no effect, so the projected Algorithm 1 inherits the previously established recursion.The argument first proves the claim for signals in X and then handles the complementary class separately.
  • (vi) Establishing (C.43): For x ∈X, bounds from (3.8) and (C.10) imply 2λx exceeds ∥xt∥2, establishing (C.43).The displayed inequalities give 2λx ≥ 8/5∥x∥2 ≥ 3/2∥x∥2 > ∥xt∥2.
  • C.1.4 A Separate Argument for x ∈X c: For x ∈X^c, the projection yields the desired error bound through a separate direct argument using the defining tail-to-signal relation.Specifically, x ∈X^c implies ∥x[s]∥2 ≤ ∥x∥2 ≤ 1/c∗ τs(x).
  • C.2 Proof of Theorem 3.2 (Non-Uniform Instance Optimality): The proof of Theorem 3.2 follows three steps: decompose Rn into X and X^c, establish RAIC and initialization on X, then prove instance optimality on X^c.The set X is defined by δs(u) ≤ c∗∥u∥2, while the complement requires only a Θ(1) error bound.
  • C.2 Proof of Theorem 3.2 (Non-Uniform Instance Optimality): Under m ≳s^2 up to logarithmic factors, initialization holds with high probability, and projection does not affect the iterates satisfying (3.8).Together with RAIC on X and the Θ(1) complement argument, these steps yield the claimed non-uniform instance optimality.

C.2.1 Proof of the RAIC in (C.45) if x ∈X … D.1 Proof of Theorem 4.1 (Instance Optimal 1bCS)

The appendix proves the required RAIC and initialization conditions for x ∈ X, controls the projection and complementary case, and begins the one-bit compressed-sensing instance-optimality proof.

  • C.2.1 Proof of the RAIC in (C.45) if x ∈X: The appendix first proves the RAIC in (C.45) for nonzero x ∈ X.The argument invokes triangle inequality, Cauchy–Schwarz, Gaussianity, and a restricted norm bound.
  • C.2.2 Proof of the Initialization Guarantee (C.46) if x ∈X: Lemma C.4 is reused to establish the initialization guarantee (C.46), with (C.9) supplied by choosing c∗ sufficiently small.The remaining requirements are (C.10)–(C.12).
  • Establishing (C.10): m ≳log n guarantees (C.10) through a tighter norm estimate based on sub-Gaussian concentration.The estimate uses ∥λx/∥x∥2 −1∥ψ2 = O(m−1/2).
  • C.2.3 The Projection Has No Impact if x ∈X: The projection onto Bn_2(2λx) has no impact because the iterates satisfying (C.47) obey ∥xt∥2 ≤2λx for every t ≥0.The proof obtains this from sufficiently small c∗ and c, together with bounds relating λx and ∥x∥2.
  • C.2.4 A Separate Argument if x ∈X c: For x ∈ X^c, the separate argument uses ∥xt∥2 ≤2λx ≤3∥x∥2 to bound dist(xt, x) by 4∥x∥2.This yields the stated relationship to ∥x−x[s]∥2/c∗.
  • D Proofs for One-Bit Compressed Sensing: The one-bit compressed-sensing proof introduces the relevant expression for nonzero u and x and reduces the remaining task to proving (4.2).The reduction follows directly from the definition.
  • D.1 Proof of Theorem 4.1 (Instance Optimal 1bCS): In the proof of Theorem 4.1, establishing (4.2) is identified as the remaining step for the instance-optimal one-bit compressed-sensing result.The passage states that (4.2) is equivalent to the displayed definition-based condition.

D.1.1 Proof of the RAIC in (D.1) … E Proofs for Sparse ReLU Regression

The proofs establish the RAIC through a novel instance-dependent hyperplane tessellation and derive non-uniform instance optimality using the unified framework. Subsequent bounds control the remaining error terms and initiate the sparse ReLU regression analysis for nonzero signals.

  • D.1.1 Proof of the RAIC in (D.1): A novel instance-dependent hyperplane tessellation result provides the key uniform, signal-dependent bound needed to establish the RAIC.The result concerns hyperplanes separating x and x[s] and is used in the subsequent RAIC analysis.
  • D.1.1 Proof of the RAIC in (D.1): The RAIC proof concludes by combining bounds on the constituent terms with ∥x − x[s]∥2 ≤ e0(x), yielding the claimed inequality.The final substitution uses the bounds established earlier in the proof.
  • D.2 Proof of Theorem 4.2 (Non-Uniform Instance Optimality): The non-uniform instance optimality proof decomposes the sphere, applies the unified framework on the controlled set, and uses a crude bound on its complement.For x ∈ X^c, the proof uses ∥x_t−x∥2 ≤ 2δs(x)/c∗.
  • D.2.1 Proof of the RAIC in (D.18): The proof of the RAIC in (D.18) performs a sharp two-vector analysis using x and x[s]/∥x[s]∥2 and an orthogonal basis of their span.The argument decomposes each Gaussian vector ai according to this basis.
  • Bounding Ξ7 and Ξ8: Moment-based Bernstein’s inequality and established Gaussian facts supply the main tools for bounding Ξ7 and Ξ8.The section explicitly invokes Lemma D.4 and Lemma D.5 for these bounds.
  • Bounding Ξ9: The Ξ9 estimates are combined with the preceding bounds to obtain (D.20), completing that part of the proof.The derivation uses the cited probabilistic estimates and equations (D.22), (D.23), (D.25), and (D.21).
  • E Proofs for Sparse ReLU Regression: The sparse ReLU regression proofs define hx(u) as in (5.1) and restrict the subsequent analysis to nonzero x because x = 0 is recovered exactly.The exact-recovery statement motivates excluding the zero signal from the remaining analysis.

E.1 Proof of Theorem 5.1 (Instance Optimal Sparse ReLU Regression)

The proof follows the unified framework by decomposing R^n, establishing a signal-dependent RAIC, verifying initialization, and handling the projection operator to obtain instance optimality.

  • RAIC: A signal-dependent RAIC is established with parameters μ_2 = 0, e(x) = 6τ_s(x), and R_loc^x = c||x||_2.The conditions are stated to satisfy (2.9)–(2.11) when c* is chosen sufficiently small.
  • Initialization: The proof establishes initialization and applies Theorem 2.3 to the iterates produced by Algorithm 3 without P_{B_2^n}(2||x_0||_2).The initialization result is stated under sparsity and sufficiently small c*, while the projection is later shown to have no effect on nonzero iterates in X.
  • Instance Optimality for x ∈ X^c: Using P_{B_2^n}(2||x_0||_2) and the definition of X, the proof establishes instance optimality for x ∈ X^c.This is presented as the third main proof step.

E.1.1 Proof of the RAIC in (E.2) … E.1.4 A Separate Argument for x ∈X c

The section proves the RAIC for exactly sparse signals and extends it to nonsparse x using truncation and ReLU Lipschitz bounds. It then establishes initialization, shows projection is inactive for x ∈ X \ {0}, and treats x ∈ X^c separately.

  • E.1.1 Proof of the RAIC in (E.2): For x ∈ X \ {0}, the RAIC is extended by setting c = ˜c and decomposing the error through x[s] and h_x[s](u).The decomposition is given in equation (E.5).
  • E.1.1 Proof of the RAIC in (E.2): The extension controls ∥u − x[s]∥2 by (c + c∗)∥x∥2 ≤ ˜c∥x∥2 and uses ∥x − x[s]∥2 ≤ τ_s(x).The condition c∗ ≤ ˜c ensures the final inequality.
  • E.1.2 Proof of the Initialization Guarantee (E.3): The initialization proof bounds its terms using Lemma A.1, Lemma C.13, estimates (B.2) and (B.4), and m ≳ s log(en/s).The resulting guarantee holds with probability at least 1 − 2 exp(−c′s log(en/s)).
  • E.1.3 The Projection Has No Effect on x ∈X \ {0}: For x ∈ X \ {0}, the RAIC and initialization guarantees imply ∥x^t − x∥2 ≤ (c + 30c∗)∥x∥2 for all t ≥ 0.This also bounds ∥x^t∥2 by (1 + c + 30c∗)∥x∥2.
  • E.1.3 The Projection Has No Effect on x ∈X \ {0}: When c and c∗ are small enough, the projection PB_n^2(2∥x_0∥2) does not affect the iterates satisfying (E.4).Thus, the iterates produced by Algorithm 3 also satisfy (E.4).
  • E.1.4 A Separate Argument for x ∈X c: For x ∈ X^c, the proof uses a separate argument based on the projection PB_n^2(2∥x_0∥2) to control Algorithm 3’s iterates.The bounds rely on triangle inequality, Cauchy–Schwarz, Lemma C.1, and (C.44).

E.2 Proof of Theorem 5.2 (Non-Uniform Instance Optimality) … E.2.4 Separate Argument if x ∈X c

The proof establishes non-uniform instance optimality by verifying the RAIC and initialization conditions on X, showing projection is inactive there, and treating X^c separately through iterate bounds.

  • E.2 Proof of Theorem 5.2 (Non-Uniform Instance Optimality): The proof decomposes R^n into X = {u ∈ R^n : δ_s(u) ≤ c*∥u∥_2} and its complement, using separate instance-optimality arguments.The set X is defined for a sufficiently small universal constant c* > 0.
  • E.2 Proof of Theorem 5.2 (Non-Uniform Instance Optimality): Theorem 2.1 combines the established components to yield the desired guarantee for x ∈ X.This step reuses the initialization bound from Theorem 5.1 to ensure condition (2.12).
  • E.2.1 Proof of the RAIC (E.10) if x ∈X: For fixed x ∈ X, the proof establishes the required RAIC, with the key remaining bound handled using inequalities (E.7), (C.50), and (C.51).Combining these ingredients yields (E.12), identified as the desired RAIC (E.10).
  • E.2.2 Proof of the Initialization Guarantee (E.11) if x ∈X: For fixed x, the initialization guarantee ∥x_0 − x∥_2 ≤ c∥x∥_2 holds for x ∈ X when m ≳ s log(en/s), under sufficiently small c* and with high probability.The probability statement is inherited from the cited concentration argument and Lemma C.13.
  • E.2.3 The Projection Has No Effect if x ∈X: For x ∈ X, the iterates remain within the projection radius because ∥x_t∥_2 ≤ 2∥x_0∥_2 for every t ≥ 0.The bound follows from the instance-optimality estimate and the initialization relation between x_0 and x.
  • E.2.4 Separate Argument if x ∈X c: For x ∈ X^c, the proof instead uses the high-probability event (E.13) to show ∥x_t∥_2 ≤ 2∥x_0∥_2 ≤ 4∥x∥_2 + 6∥x − x_[s]∥_2.This separate argument controls the iterates without assuming x belongs to X.
Loading 2609.02120v1…