SPB Git

spb/wp28_uqo

Public
10.3 KB · 57 lines markdown
1# PRIORITY_AND_GAP — WP28 (literature cutoff 2026-10-28)23Sources: four theorem-level verification tasks (audits A–D in this directory; 56 rows in `PRIOR_ART_MATRIX.csv`, 24 of them read in4full text, the rest at abstract/metadata level and marked so). Page/theorem numbers refer to the versions read (arXiv or accepted5manuscripts when publisher pages were bot-blocked).67## 1. Verified anchors (theorem level)8| Paper | What it proves (our notation: K blocks of size m = N/K) | Rounds / uplink | Read |9|---|---|---|---|10| Zhang–Duchi–Wainwright 2013 (JMLR) | AVGM MSE O(1/N + 1/m²) ⇒ K ≲ √N (eq. 10); SAVGM = (θ̄₁ − rθ̄₂)/(1−r) with one random r-subsample, MSE O(1/N + 1/(r(1−r)²m³)), leading constant inflated by (2+3r)/(1−r)², K ≲ N^{2/3} (Thm 4, eq. 11). No jackknife, no Newton, multiple subsamples "open". | 1 / p (2p) | full |11| Huang–Huo 2019 (Math. Prog.) | Plain average + ONE aggregated-Hessian Newton step: √N-normal and equivalent to the full M-estimator when k = O(√N) (Thm 3.4); MSE ≤ 2TrΣ/N + O(N^{-2}) + O(k⁴N^{-4}) (Thm 3.5) — the k⁴N^{-4} term implicitly allows k = o(N^{3/4}) (not stated). No bias correction. | 2 / p + p² | arXiv v2 |12| Jordan–Lee–Yang 2019 (JASA) | CSL: machine-1 Hessian, gradients only; ‖θ̃ − θ̂‖ ≤ C(‖θ̄−θ̂‖² + (N^{-1/2} + m^{-1/2})‖θ̄−θ̂‖) (Thm 3.1/3.3); contraction C/√m per round; Cor 3.4 sandwich expansion. One round from the average ⇒ K = o(N^{2/3}) (translation). | t / p | arXiv v3 |13| Fan–Guo–Wang 2023 (JASA, CEASE) | Rounds frontier (p. 16, verbatim): one single-machine-Hessian step from the average matches θ̂ iff n³ ≫ N·polylog ⇒ K = o(N^{2/3}); t steps ⇒ K = o(N^{(t+1)/(t+2)}); averaged local-Hessian step in the linear model ⇒ K = o(N^{3/4}). | t / p | arXiv v2 + PMC |14| Zhu–Li–Wang 2021 (JCGS) | TWLSE: average → one LOCAL Newton step per machine → local-Hessian-weighted average: efficient iff m/N^{1/4} → ∞, "allows K = O(N^{3/4})" (Thm 2); iterated version with m/log N → ∞ rounds (Prop 2); unequal n_k. | 2 / p + p² | arXiv v4 |15| Gu–Chen 2023 (JMLR) | Analytic (Rilstone-type) local bias correction with sample splitting, then Hessian-weighted average: χ² limit if K = o(m²) ⇔ K = o(N^{2/3}) (Thms 4–6); beats the SAVGM constant; quasi-likelihood/sandwich; heterogeneity. | 1 / p + p² | arXiv v1 |16| Wu–Zhu–Wang 2023 (Statistica Sinica) | Delete-one jackknife within each subsample, then average: bias O(m^{-2}) + O(N^{-1}), normal under N = o(m⁴) (⇔ K = o(N^{3/4})) for smooth functions of means (Thm 2, 4). | 1 / p | arXiv v1 |17| Yin 2022 (arXiv 2207.06253) | Bias-adjusted one-step estimator from the plain average (analytic removal of quadratic terms): efficient iff K = o(m²) ⇔ K = o(N^{2/3}) (Thm 3.2); Fisher information from gradients with error O_p(m^{-1} + K^{-1}). | 2 / p + summaries | arXiv v1 |18| Dhaene–Jochmans 2015 (RES) | Half-panel jackknife 2θ̂ − θ̄_{1/2}; general h-th order split-panel jackknife with Vandermonde-type weights (eqs. 5.1–5.3); bias-optimal partitions G = {2, 3, …, h+1}; first-order variance unchanged; higher-order variance left open. Panel, not distributed. | — | manuscript |19| Hahn–Hughes–Kuersteiner–Newey 2024 (QE) | Split-sample bias estimates are inconsistent (O_p(1)); split-sample corrections have twice the higher-order variance of delete-one (Props 5–7). | — | full |20| Volgushev–Chao–Cheng 2019 (AoS) | Plain averaging of quantile regressions: sufficient S = o(√N/log N), NECESSARY S = o(√N) via an explicit worst-case model (Thm 3.2, Cor 3.3). Template for sharpness statements. | 1 / p | arXiv + NSF |21| Lin–Xi 2011; Rosenblatt–Nadler 2016; Battey et al. 2018; Shamir et al. 2014 (DANE); Wang et al. 2017 (EDSL); Chen–Liu–Zhang 2022 (FONE); Shang–Cheng 2017; Gao et al. 2022 (review) | One-shot weighting (K ≪ N^{1/4}); bias of the average = m × centralized bias; √N barrier for plain averaging; local-Hessian contraction (β/λ)² ≍ 1/m per round; gradient-only multi-round; sharp machine counts in nonparametrics; review confirming "one-step C₁/N + O(m^{-4} + N^{-2})" and no (order, rounds) frontier as of 2022. | | full/abstract |2223## 2. Claim-by-claim map24| # | Claim in the prior draft / mandate | Status after audit |25|---|---|---|26| (i) | Half-block (and quarter-block) jackknife of local MLEs cancels the O(1/m) (and O(1/m²)) bias while preserving the first-order influence term | **Known in components**: the extrapolation algebra is Quenouille (1956) / Schucany–Gray–Owen (1971) / Dhaene–Jochmans (2015, panel); "debias locally then average" exists with analytic corrections (Gu–Chen 2023; Yin 2022), delete-one jackknife (Wu–Zhu–Wang 2023) and one-level subsampling (ZDW 2013 SAVGM). **Possibly new**: the general r-th order *nested split* construction of local MLEs with the influence-preservation argument and explicit remainder constants A_r (Lemma 3) in the distributed setting; r ≥ 3 not found anywhere. |27| (ii) | Half-block jackknife + one aggregated-Hessian Newton step ⇒ first-order equivalence for K = o(N^{7/8}) | **Not found**; closest: Huang–Huo (plain average + one step, stated √N, implicit 3/4), Zhu–Li–Wang (3/4 with local steps), Yin (2/3 with analytic adjustment), CEASE (2/3 single-machine). The exponent 7/8 appears nowhere. **Demonstrably new with specified proof** (Theorem 1, cell (2,1)). |28| (iii) | General (r, q) frontier K = o(N^{1 − 1/(2^{q+1} r)}) | **Not found**; rounds-only frontiers exist (CEASE (t+1)/(t+2) with a single-machine Hessian; JLY ⌈log K/log m⌉ rounds). **Demonstrably new with specified proof** (Theorem 1). The CEASE rounds frontier is recovered exactly as the single-machine-Hessian case of our Theorem 3 (α = 1 − 1/(2r + q), r = 1). |29| (iv) | Exact exponential boundary limit −4θ0c⁴ at K ~ cN^{7/8} | **New** (sharpness for a corrected construction). Generalised to all (r, q): −θ0(β_r c^r)^{2^q} (Theorem 2). Necessity results in the literature concern plain averaging only (Volgushev et al.; Shang–Cheng). |30| (v) | Inexact / stale / single-machine / quantized Hessians change the admissible exponent | **Partially known** (JLY factor m^{-1/2}; DANE/CEASE factor 1/m; Zhu–Li–Wang 3/4) but **never expressed as an exponent frontier nor with byte/bit accounting**; the quantized-Hessian statistical statement was not found. Theorem 3 unifies and extends. |31| (vi) | Unequal block sizes; misspecification | **Known** as extensions (Zhu–Li–Wang, Gu–Chen, Lin–Xi, JLY Cor 3.4). Present as Proposition 4 / Remark, not as a contribution. |32| (vii) | Communication–computation decision rule (one more local level vs one more round) | **No explicit rule found**; only qualitative remarks. Proposition 5 is a *conditional cost-model* result calibrated on measured hardware, labelled as such. |33| (viii) | Communication accounting in rounds, messages, numbers and bytes | Only O(p)/O(p²) remarks in the literature; our accounting is bookkeeping, not a theorem. |3435## 3. Candidate contributions36- **A (strongest, GO):** the joint local-order / global-round frontier (Theorem 1) with its sharpness in an exact model (Theorem 2) and the inexact-derivative extension that recovers the CSL/CEASE and averaged-local-Hessian cases and adds quantization/bit requirements (Theorem 3). Novelty: no joint frontier, no sharpness for corrected constructions, no bit-precision statement in the audited literature.37- **B (feasible backup, GO as supporting material):** the general nested-split extrapolation family with explicit remainder/amplification constants A_r, exact finite-sample bias and variance identities in the exponential model, the Newton basin of attraction, and the finite-sample comparison with analytic (Gu–Chen-type) and delete-one corrections. Novelty: incremental; positioned as the local building block.38- **C (negative results, GO):** (a) Proposition: higher-order split corrections lose in RMSE to lower orders for moderate m and have positive probability of leaving the Newton basin (exponential model, exact); (b) in exponential families with aggregable sufficient statistics (and in the exponential model for the full CSL surrogate) the approximate protocols are dominated by exact pooling — no computational lower bound is claimed; (c) unweighted averaging with unequal sizes is not first-order equivalent without a Newton step.3940## 4. Decisions41| Proposed claim | Decision |42|---|---|43| "Jackknife + Newton is a novel estimator" | **DROP** (components known: HH19, ZDW13, DJ15, GC23, WZW23). Rephrase as "a known local correction and a known global correction, analysed jointly for the first time". |44| K = o(N^{7/8}) for (2,1) and the general α(r, q) | **GO** (Theorem 1) with explicit comparison table against HH19 (√N stated / 3/4 implicit), ZLW21 (3/4), GC23 (2/3), Yin22 (2/3), CEASE (rounds frontier). |45| Sharpness (−4θ0c⁴ and general) | **GO** (Theorem 2), scoped as "for this construction, in this model"; cite Volgushev et al. as the template and state that it is not a universal lower bound. |46| Inexact Hessian frontier + quantization bits | **GO** (Theorem 3); cite JLY Thm 3.1/3.3, DANE Thm 2, CEASE Thm 4.1, ZLW Thm 2, Alimisis et al. (optimization only). |47| Heterogeneous sizes / misspecification | **REVISE** → extension Proposition 4 + remark, with citations; no novelty claim. |48| Cost-model decision rule | **REVISE** → conditional Proposition 5 ("under the measured cost model"), calibrated on the cluster benchmark; empirical, not general. |49| Adaptive (r, q) selection with proof | **DROP as theorem** → heuristic + numerical evaluation only, labelled open. |50| Wall-clock / energy / dollar claims | **DROP** unless measured in Phase 8; report measured quantities only. |51| Minimax / communication lower bounds | **DROP** (explicitly disclaimed; exact sufficient-statistic pooling dominates in exponential families). |5253## 5. Items not verifiable in this audit (to check against library copies before journal submission)54Quenouille 1949/1956 texts; Tukey 1958 abstract; Schucany–Gray–Owen 1971 determinant system; Sharot 1976; Rilstone et al. 1996 and55Bao–Ullah 2007 texts; Le Cam 1956; Bickel 1975 technical statements; van der Vaart §5.7 content; Cordeiro–McCullagh original notation;56published JASA theorem numbering for JLY, CEASE, FONE; Springer text of Huang–Huo; Yin's 2022 Temple thesis.57
Files · 960926063a6ca5ed53de00e9616d11db178d3b22
Menu

Theme