Second-Order Complexity Theory for Risk, Explanation, and Calibration in Machine Learning

Many machine-learning quantities are straightforward to compute once a finite data set is fixed, but their population versions can encode much harder computational problems. We study this gap for population risk, attribution, counterfactual explanation, and calibration certification, asking which of these quantities can be approximated in time polynomial in the requested number of bits. The formal basis is the Kawamura-Cook second-order complexity theory, instantiated here with compact-domain real functions carrying explicit evaluation, continuity, and range information. In this framework, expected risk has exactly the difficulty of real integration. Integrated gradients behave differently by dimension: in one dimension they reduce to evaluating endpoints, while in two dimensions even one coordinate can already encode one-dimensional integration when the relevant derivative is provided. The same lens separates the costs in related explanation and certification methods. Interventional SHAP is integration-hard even with two features, succinct coalitional SHAP is #P-hard, nearest-threshold counterfactual search is NP-hard, and continuous calibration certificates combine integration with maximization. These results give a taxonomy of when population-level explanation and certification admit polynomial-time bit approximations, and what additional structure is needed for tractability.