Minimax Estimation of Graphon Probability Matrices under Spectral Constraints

We study estimation of the sampled probability matrix from one dense graph generated by a bounded measurable graphon. The latent coordinates are independent and uniformly distributed. For fixed singular-value envelopes satisfying the stated assumptions, we characterize the minimax risk under normalized squared Frobenius loss. Matching upper and lower bounds identify how the full spectral envelope determines the estimation rate. The lower bound holds even when the latent coordinates are observed. A single spectral threshold estimator attains the rate without knowing the envelope and uses only the adjacency matrix. Square summability of the envelope is necessary and sufficient for uniform consistency over the fixed class. We also characterize minimax rates for positive semidefinite graphon operators under polynomial spectral envelopes. Comparing these rates with those for the general class shows when positive semidefiniteness improves the estimation rate or changes whether uniform consistency is possible. The paper provides precise finite-sample statements, complete proofs, examples for several spectral decay regimes, and a comparison with prior work.