Weak supervisors are usually judged by their own errors, but what matters is what a student learns from them. For squared loss and any linear learner shared by all supervisors, we show that a supervisor’s value is determined by its errors after they pass through the student’s learning operator. Consequently, the inner products of the supervisors’ raw errors can be compatible with every feasible value of the student’s risk, and weighting supervisors by them can be arbitrarily worse than the best weighting in relative excess risk. This student-relative value is not identifiable from unlabeled data, but what is missing is small: one finite-dimensional projection of the target decides whether training on a weak aggregate helps, another decides how to weight the supervisors. Known teacher training rules, or a label-model condition stated in student-relative form, shrink it further. Clean labels close the remaining gap at a cost set by the geometry of the unresolved directions rather than by the dimension of the student’s representation, with matching worst-case lower bounds. In Gaussian designs we also quantify when exact teacher structure beats ordinary stacking and when weak supervisors are worth their anchors compared with every procedure that uses the clean labels alone. The guarantees extend to fitted ridge students and finite unlabeled data.

We derive deterministic conditions under which objective accuracy implies structural recovery in prototype clustering. For Euclidean k-means, we control the improvement obtained by reassigning observations away from a benchmark partition. A sufficiently small boundary belt yields profiled quadratic growth on a neighborhood that can contain incorrectly assigned candidates. An independent localization bound then converts a small objective gap into small prototype displacement and exact recovery after nearest-prototype assignment. A second route compares optimized partition costs directly. In a two-ball model, it gives error bounds for arbitrary near-optimal solutions without a displacement assumption, together with sufficient recovery thresholds whose dependence on imbalance is optimal in order. Squared loss and one-dimensional continuous linear loss require different separation scales, c_b^−1/2 and c_b⁻¹, respectively, where c_b is the proportion of observations in the smallest benchmark cluster. A loss-increment condition number organizes these comparisons. Local margins describe recoverable cluster interiors, while a coarse conditional inequality supports extensions to heterogeneous and evolving objectives. We distinguish these benchmark-relative guarantees from empirical stability diagnostics.

Clustering algorithms report a single partition, yet the objective often admits many near-optimal partitions with substantially different structure, and agreement among random restarts certifies nothing. We develop a theory of sound but incomplete certification for the near-optimal set of the two-cluster k-means objective. The central object is the structural barrier: the smallest objective value attainable at Hamming distance at least m from a reported partition. Comparing it with the incumbent value and a global lower bound yields a three-valued output (stable, ambiguous, or inconclusive) and separates three sources of uncertainty that are usually conflated: optimization gap, structural slack, and relaxation error. We show that the cost of every alternative partition is an explicit concave quadratic function of a single vector of moved residuals. Consequently, the exact barrier is attained at vertices of a moved-sum polytope and is computable in polynomial time in fixed dimension, although the decision problem is NP-complete in general. Closed-form coupled bounds give explicit radius certificates whose dependence on cluster imbalance is sharp up to a constant factor, and a forced-flip refinement certifies simultaneously valid pointwise cores. For statements about a latent partition, an exact profiled chi-square pivot transfers any intrinsic certificate into a finite-sample confidence statement. We quantify the calibration tax paid by absolute loss cutoffs, show that likelihood-ratio calibration removes it under strong separation, and prove posterior-overlap lower bounds that limit every honest radius and core.

We ask which clustering of a single observed network yields cluster robust inference that is theoretically valid. Building on Leung (2023), who showed that a low-conductance clustering is necessary and sufficient for asymptotic independence, we study a clustering algorithm, spectral clustering, and provide theoretical guarantees. A row normalized spectral clustering algorithm that drops the trivial Laplacian eigenvector before applying k-means yields clusterings with two properties that inference requires, low conductance and balance. First, for a fixed k and under a spectral gap, the resulting clustering achieves near optimal k-way conductance deterministically on the observed graph. Second, under Ahlfors-regular volume growth, any such low-conductance clustering is automatically balanced, excluding tiny “whisker” clusters. These guarantees provide the primitive conditions for the t-test in Ibragimov and Müller (2010) and the randomization test in Canay et al. (2017), thereby establishing a principled procedure for valid inference on network data.