Pith. sign in

REVIEW 2 major objections 9 minor 22 references

The Convergence and Error Analysis of Coordinate Descent Methods with Compression for Full Configuration Interaction

T0 review · 2 major / 9 minor · reviewed 2026-07-31 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Compressed coordinate descent for full configuration interaction still converges linearly, and the ground-state energy error is only quadratic in the compression threshold.

desk verdict Solid local theory for an already-used compressed CDFCI solver: linear rate to a restricted eigenproblem and a usable O(τ²) energy error, with the usual caveats on assumptions and constants. read the letter →

arxiv 2607.24319 v1 pith:6WMFHEMB submitted 2026-07-27 math.NA cs.NAmath.OC

Yingzhou Li , Qiang Wu This is my paper · ORCID
classification math.NAcs.NAmath.OC MSC 65F1565K1081Q05
keywords fullconfigurationinteractioncoordinatedescentcompressioneigenvalueerrorlinearconvergenceexponentialdecaysparseHamiltonian
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Full configuration interaction finds the exact ground-state energy of a molecule inside a finite basis, but the Hamiltonian is so large that one cannot store full vectors. Coordinate Descent FCI updates one coordinate at a time and compresses tiny entries to keep the iterate sparse. This paper proves that, near a good starting guess, the compressed iteration still converges linearly—not to the true ground state, but to the ground state of the principal submatrix on the coordinates that ever become active. Under the extra assumption that the true eigenvector’s entries decay exponentially when sorted by size, the energy error between that restricted eigenvalue and the true ground-state energy is only on the order of the square of the compression threshold. The result justifies the practical compression rule used in large FCI calculations and supplies a concrete error model that can be used for extrapolation.

What carries the argument

The unrestricted nonconvex objective f(c) = ∥H + ccᵀ∥_F², whose local minimizers are exactly the scaled ground eigenvectors, together with the compression rule that only discards updates to coordinates that are still zero in c; the argument reduces the compressed dynamics to ordinary coordinate descent on the growing but finite support and then controls the residual of the unselected block by n_z τ.

What would settle it

On a molecular Hamiltonian whose sorted ground eigenvector is known not to decay exponentially, measure |λ − λ_{k-opt}| versus τ; if the observed scaling is slower than quadratic (or the linear rate fails near a Hartree–Fock start), the central error claim is false.

Watch

Extended reading notes

Core claim

Under local strong-convexity assumptions the compressed CDFCI iteration converges linearly to ±c_{k-opt}, the suitably normalized ground eigenvector of the principal submatrix on the cumulative support; when the true ground eigenvector also has a spectral gap and exponential tail decay, the eigenvalue error satisfies |λ − λ_{k-opt}| = O(τ²).

Load-bearing premise

After the true ground-state coefficients are sorted by size, their magnitudes must fall off exponentially; without that tail the paper only obtains a linear residual bound and loses the quadratic energy error.

Editorial extensions

If this is right

  • Compression can be used safely inside CDFCI without destroying the linear rate once the iterate is inside the local strong-convexity neighborhood.
  • The energy error is theoretically O(τ²), so energies computed at several thresholds can be extrapolated to τ = 0 by a quadratic fit.
  • The limiting point is exactly the ground eigenpair of the principal submatrix on the coordinates that ever become nonzero, giving an explicit characterization of what the algorithm actually solves.
  • Only coordinates that remain zero in c are ever discarded, so the Rayleigh quotient computed from the auxiliary vector b stays exact throughout.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same O(τ²) residual-to-energy conversion should apply to other selected-CI or compressed subspace methods whenever the target vector has an exponential tail and the discarded residual is controlled in ℓ_∞.
  • If a cheaper certificate of exponential decay (or a weaker polynomial tail with a correspondingly weaker power of τ) could be proved for general FCI Hamiltonians, the error bound would become unconditional for chemistry applications.
  • The extrapolation procedure already demonstrated on H₂O and C₂ suggests a practical workflow: run several moderately compressed CDFCI solves and fit rather than drive τ all the way to machine precision.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 9 minor

Summary. The paper analyzes CDFCI with threshold compression within the unconstrained formulation min ‖H+ccᵀ‖²_F of [12]. Three results are claimed: (i) under local strong convexity on D±, the compressed iteration converges linearly to ±c^{k-opt}, the ground eigenvector of the principal submatrix H_{VV} on the cumulative support V (Thm 3.7); (ii) the compression-induced ℓ∞ residual is O(n_z τ) (Lemma 3.5, Eq. (4.3)); (iii) under a spectral gap (Assump. 3.8) and exponential decay of the sorted ground eigenvector (Assump. 3.9), the eigenvalue error obeys |λ−λ_{k-opt}| = O(τ²) with an explicit prefactor (Thm 3.13). Numerics on synthetic matrices and H2O/C2 cc-pVDZ confirm linear convergence, the τ² scaling, and support a τ²-extrapolation scheme.

Significance. This is, to my knowledge, the first convergence theory for CDFCI as actually implemented (with compression), a method in practical use for FCI. The τ² result gives a principled basis for the energy-extrapolation heuristic, and the paper ships a falsifiable scaling prediction that is tested on both synthetic and realistic systems, with honest reporting of the bound's looseness (ratios 10¹–10⁴, §6.2). The proof architecture (residual control → restricted-problem identification → pseudoinverse tail bound → quadratic form) is sound in outline, and the extrapolation protocol of §6.3 is a useful practical deliverable. The theory is explicitly conditional (local assumptions, realized support), which is appropriate for the problem.

major comments (2)
  1. [§4.1, Eq. (4.2)-(4.3)] Eq. (4.3) (and the same issue in (3.2)): the residual accounting is not rigorous as written. 'b_i has been compressed at most k times' is unjustified — selected coordinates are revisited many times, so the number of discarded contributions per (i,j) pair is unbounded a priori. The salvageable argument is: b_i^{(l)}=0 forces every contribution to have been discarded at the most recent selection of each j, giving |H_ij c_j^{(l)}| ≤ τ directly. Two more gaps: (b) coordinates with b_i≠0 but c_i=0 are untreated, though the argmax rule (2.3) uses the proxy b; (c) on selected coordinates b differs from Hc by the frozen pre-acceptance error (bounded by n_z τ via the same argument), so the claim above (4.2) that |∇_{j_l}f| attains the max over selected coordinates holds only up to O(n_z τ) slack. Lemma 3.5 feeds Lemma 3.6, Thm 3.7 and Lemma 3.11, so this needs a careful rewrite; constants, not ex
  2. [§5.3, Eq. (5.23) / Assumption 3.9] The proof conflates two index orderings. Assumption 3.9 is formulated in the magnitude-sorted order of c, while 'the first k coordinates are selected' is the algorithm-determined ordering. The bound Σ_{j>k}|(c_2)_j| ≤ Q‖c_2‖∞ used in (5.23)–(5.24) holds only if the unselected set is (a subset of) the magnitude tail of c; this does not follow from the stated assumptions, since the dynamics need not select coordinates in magnitude order. Without it, the dimension-independent prefactor in (3.5) is not established. Please either add an assumption/lemma that unselected entries are small (e.g. derived from (3.2) via a resolvent bound) or restate Thm 3.13 accordingly. Relatedly, note that the τ² rate itself does not require Assumption 3.9: by Cauchy interlacing and (5.15), λ^{k-opt}−λ = ⟨H_21c_1^{k-opt}, (H_22−λI)^{-1}H_21c_1^{k-opt}⟩/(c^{k-opt⊤}c) ≤ 2kn_z²τ²/((−λ)gap(H)). Stating this wouldcl
minor comments (9)
  1. [Lemma 3.12 vs Eq. (5.16)] Lemma 3.12 states m = √(−λ^{k-opt}‖c‖₁²/(4kλ²)+1), but the proof (5.16) derives m = √(−4λ^{k-opt}‖c‖₁²/(kλ²)+1) — a factor-16 discrepancy inside the root that propagates into the constant of Thm 3.13. Please reconcile.
  2. [Eq. (5.4) vs definition of B±] d in (5.4) is written with √(−λ) in the numerator, but the radius of B± in §3.1 has it in the denominator; only the latter is consistent with the subsequent bounds d < ½√(−λ) and 2d < ½√(−λ).
  3. [§3.2, statements of Lemmas 3.10–3.12] 'As a direct consequence of Theorem 3.9' and 'Under Theorem 3.8 and Theorem 3.9' should refer to Assumptions 3.8/3.9. Also in Lemma 3.11's statement the premise should read |(Hc^{k-opt})_i| < n_z τ, matching (3.2), not < τ.
  4. [Lemma 3.4] As proved, V is finite merely because V ⊆ {1,…,n}; this gives no effective control. Since k = |V| enters the final bound as √k in (3.5) and |V| grows as τ decreases, please state explicitly that the theory is conditional on the realized support, and that the limit point in Thm 3.7 is defined by that support (i.e., the algorithm converges to the optimum on its own limit support) — this should also temper the abstract's phrasing.
  5. [§5.2, Eq. (5.13)-(5.14)] The system (5.13) is singular; solvability requires RHS ⊥ ker(λI−H) = span(c) (which holds since cᵀ(H−λI)=0), and the solution-set argument requires λ simple (implied by gap(H)>0). Please add these checks; they are one line each.
  6. [§3.2 and §6.3] By Cauchy interlacing λ ≤ λ^{k-opt}, so computed energies are variational upper bounds. This sign information justifies E(τ)−E_0 > 0 in the log-ansatz (6.2) and the bisection direction; worth stating explicitly.
  7. [§2.1 / Fig. 1] §2.1 asserts exponential decay of the FCI ground eigenvector as fact, supported only by one H2O/STO-3G log-linear fit (R²=0.95, Fig. 1, showing ~5×10⁴ of 2×10⁶ entries). Please temper the wording and/or cite broader evidence, since Assumption 3.9 is the theory's key empirical input.
  8. [Table 2 and §6] State the reference ('exact') energies used for the error columns, the τ samples, and the synthetic matrices' parameters (n, n_z, gap, decay constants — Fig. 3 suggests n=1000 but the text does not say). Please also add a code/data availability statement for the numerics.
  9. [Throughout] Typos/formatting: 'T echnical proof', 'V erification' headings; 'local maximizer' → 'maximizers' (§2.2); 'each is supported' (§3.1); 'adjustsb' (§2.2); missing period after the reference list in §1; Ref. [7] lacks venue/year; Ref. [4] title in all caps.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: convergence and O(τ²) error are proved implications of stated assumptions, not definitional or fitted tautologies.

full rationale

The paper is a standard local convergence/error analysis. Theorem 3.7 (linear convergence to ±c_{k-opt}) follows from strong convexity on D±, the exact line-search descent inequality carried over from the uncompressed analysis, and ℓ∞ gradient control induced by the compression rule; c_{k-opt} is defined as the minimizer of the restricted problem on the cumulative support V, so the limit characterization is not circular. Theorem 3.13’s |λ−λ_{k-opt}|=O(τ²) is derived from the residual bound |(Hc_{k-opt})_i|<n_z τ on unselected coordinates, a pseudo-inverse/gap argument for the tail, and the exponential-decay assumption (3.9) used only to convert ℓ∞ tail bounds into dimension-free ℓ1 bounds. That assumption is an explicit hypothesis motivated by chemistry practice and one plot, not smuggled in as a conclusion. Self-citations to prior CDFCI work supply the uncompressed baseline and the optimization formulation; they are not load-bearing uniqueness claims that force the compressed error identity. The numerical extrapolation ansatz E(τ)=E_0+aτ² is an application of the proved scaling to improve energy estimates, not a fit that defines the theorem. No step reduces a claimed prediction to its own inputs by construction.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The paper is a local convergence + perturbation analysis. It inherits the unconstrained FCI formulation and uncompressed CDFCI from prior work, then adds compression dynamics. Load-bearing external inputs are: local strong convexity near ±√(−λ)c_0, a positive spectral gap, row-sparsity n_z, an initial guess inside D±, and exponential decay of the ground eigenvector. No new physical entities; τ is a user threshold, not a fitted universal constant.

free parameters (3)
  • compression threshold τ = experiment-dependent (e.g. 1e-8–1e-4)
    User-chosen cutoff that defines which new b-entries are kept; all error bounds are expressed in powers of τ. Not fitted to prove the theorem, but chosen in experiments and in the extrapolation fit.
  • exponential-decay constants N, P (and derived Q)
    Assumption 3.9 introduces N,P; Lemma 3.10 builds Q=Q(N,P). These are system-dependent descriptors used to close the O(τ²) bound; not universal constants derived in the paper.
  • extrapolation coefficient a in E(τ)=E_0+aτ² = fit per system/regime
    Section 6.3 fits a (and refines E_0) by least squares / bisection on computed energies; used only for the numerical extrapolation demo, not for the main theorems.
assumptions (6)
  • domain assumption Objective f(c)=∥H+cc^T∥_F² is strongly ∥·∥_2-convex on neighborhoods B± of ±√(−λ)c_0 with μ_2=3 min(2|λ|,|λ−λ_2|), and initial c^{(0)} lies in D±.
    Lemma 3.2 and the standing local-initialization hypothesis; inherited from uncompressed CDFCI analysis [12], essential for linear rate.
  • domain assumption H has a positive spectral gap gap(H)=min_{λ_H≠λ}|λ−λ_H|>0 (Assumption 3.8).
    Used to bound ∥(λI−H)^†∥_2 and hence the discarded tail c_2 in Lemma 3.12 / Theorem 3.13.
  • domain assumption Ground eigenvector has exponential magnitude decay after sorting (Assumption 3.9).
    Upgrades residual O(τ) control into energy error O(τ²); motivated by chemistry and Fig. 1, not proved in general.
  • domain assumption Each row of H has at most n_z nonzeros; analysis often takes k>n_z.
    Standard FCI sparsity from at-most-double excitations; enters every residual bound via factors n_z, n_z².
  • ad hoc to paper Once a coordinate is selected into the active set it is never compressed again; only b-entries with c_i=0 may be discarded.
    Compression rule of the algorithm (Section 2.2); makes Rayleigh quotient exact via b and freezes support growth pattern used in the limit characterization.
  • standard math Stationary-point geometry of f: only ±√(−λ)c_0 are local minimizers (from [12]).
    Used to identify c_{k-opt} as the restricted local minimizer and to exclude other stationary points outside B± when τ is small.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Convergence and Error Analysis of Coordinate Descent Methods with Compression for Full Configuration Interaction." pith.science (2026). https://pith.science/paper/6WMFHEMB

@misc{pith2026260724319,
  author       = {Pith},
  title        = {Pith review of: The Convergence and Error Analysis of Coordinate Descent Methods with Compression for Full Configuration Interaction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6WMFHEMB}},
  note         = {Machine review of arXiv:2607.24319}
}
abstract

We study the effect of compression in Coordinate Descent Full Configuration Interaction (CDFCI) within an unconstrained optimization formulation of the full configuration interaction ground-state problem. Under suitable local assumptions, we prove that the compressed iteration converges linearly to the solution of an associated restricted problem. We also characterize the convergence point of the compressed algorithm. Under an additional exponential decay assumption on the target eigenvector, we show that the resulting eigenvalue error is of order $\tau^2$, where $\tau$ denotes the compression threshold. Numerical results support the analysis.

Figures

Figures reproduced from arXiv: 2607.24319 by the authors.

Figure 1
Figure 1. Exponential decay of the ground-state eigenvector components for H [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Convergence behavior under different compression thresholds. The horizontal [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Sparsity pattern of a representative Type 2 matrix. [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Comparison of the actual error and the theoretical bound under varying [PITH_FULL_IMAGE:figures/full_fig_p018_4.png]
Figure 5
Figure 5. Figure 5: Compression error and theoretical error bound for H [PITH_FULL_IMAGE:figures/full_fig_p019_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 2 canonical work pages

  1. [12]

    Mathematical programming , volume=

    Coordinate descent algorithms , author=. Mathematical programming , volume=. 2015 , publisher=

    2015

  2. [1]

    1975 , issn =

    The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices , journal =. 1975 , issn =. doi:https://doi.org/10.1016/0021-9991(75)90065-0 , url =

    doi:10.1016/0021-9991(75)90065-0 1975

  3. [2]

    The Journal of Chemical Physics , volume=

    Iterative perturbation calculations of ground and excited state energies from multiconfigurational zeroth-order wavefunctions , author=. The Journal of Chemical Physics , volume=. 1973 , publisher=

    1973

  4. [3]

    Journal of chemical theory and computation , volume=

    Heat-bath configuration interaction: An efficient selected configuration interaction algorithm inspired by heat-bath sampling , author=. Journal of chemical theory and computation , volume=. 2016 , publisher=

    2016

  5. [4]

    The Journal of chemical physics , volume=

    Fermion Monte Carlo without fixed nodes: A game of life, death, and annihilation in Slater determinant space , author=. The Journal of chemical physics , volume=. 2009 , publisher=

    2009

  6. [5]

    Nature , volume=

    Towards an exact description of electronic wavefunctions in real solids , author=. Nature , volume=. 2013 , publisher=

    2013

  7. [6]

    SIAM Journal on Scientific Computing , volume=

    The full configuration interaction quantum Monte Carlo method through the lens of inexact power iteration , author=. SIAM Journal on Scientific Computing , volume=. 2020 , publisher=

    2020

  8. [7]

    Journal of chemical theory and computation , volume=

    Coordinate descent full configuration interaction , author=. Journal of chemical theory and computation , volume=. 2019 , publisher=

    2019

Show all 22 references
  1. [8]

    Journal of Chemical Theory and Computation , volume=

    Coordinate descent full configuration interaction for excited states , author=. Journal of Chemical Theory and Computation , volume=. 2023 , publisher=

    2023

  2. [9]

    Journal of Chemical Theory and Computation , volume=

    Parallel multicoordinate descent methods for full configuration interaction , author=. Journal of Chemical Theory and Computation , volume=. 2025 , publisher=

    2025

  3. [10]

    SIAM Journal on Optimization , volume=

    Efficiency of coordinate descent methods on huge-scale optimization problems , author=. SIAM Journal on Optimization , volume=. 2012 , publisher=

    2012

  4. [11]

    Mathematical Programming , volume=

    Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function , author=. Mathematical Programming , volume=. 2014 , publisher=

    2014

  5. [13]

    , author=

    Truncated Power Method for Sparse Eigenvalue Problems. , author=. Journal of Machine Learning Research , volume=

  6. [14]

    Analysis of

    Liu, Hexuan and Aravkin, Aleksandr , year =. Analysis of. doi:10.48550/arXiv.2103.13523 , archiveprefix =. 2103.13523 , primaryclass =

    doi arXiv

  7. [15]

    Advances in neural information processing systems , volume=

    A direct formulation for sparse PCA using semidefinite programming , author=. Advances in neural information processing systems , volume=

  8. [16]

    SIAM Journal on Scientific Computing , volume=

    Approximating matrix eigenvalues by subspace iteration with repeated random sparsification , author=. SIAM Journal on Scientific Computing , volume=. 2022 , publisher=

    2022

  9. [17]

    arXiv preprint arXiv:2505.10882 , year=

    Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation , author=. arXiv preprint arXiv:2505.10882 , year=

    arXiv

  10. [18]

    arXiv preprint arXiv:2602.20948 , year=

    Lanczos with compression for symmetric eigenvalue problems , author=. arXiv preprint arXiv:2602.20948 , year=

  11. [19]

    Taiwanese Journal of Mathematics , volume =

    Chen, Xiao Shan and Li, Wen and Xu, Wei Wei , year =. Taiwanese Journal of Mathematics , volume =. doi:10.11650/twjm/1500406535 , langid =

  12. [20]

    Fan, Jianqing and Wang, Weichen and Zhong, Yiqiao , langid =. An

  13. [21]

    A Convergence Analysis of the Inexact

    Jia, ZhongXiao and Wang, Zhen , year =. A Convergence Analysis of the Inexact. Science in China Series A: Mathematics , volume =. doi:10.1007/s11425-008-0050-y , copyright =

    doi

  14. [22]

    SIAM Journal on Scientific Computing , volume=

    Coordinatewise descent methods for leading eigenvalue problem , author=. SIAM Journal on Scientific Computing , volume=. 2019 , publisher=

    2019

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.