Convex-relaxed counterfactual optimization for non-differentiable classifiers via neural surrogates

Counterfactual explanations (CE) facilitate actionable recourse by identifying minimal perturbations that transition an instance across a model's decision boundary. However, generating CEs for non-differentiable and non-smooth classifiers, including common nonparametric models such as kNN, random forests, and kernel SVMs, remains challenging because gradient information is unavailable or unreliable near irregular decision boundaries. Current model-agnostic approaches often neglect inherent structural priors, while surrogate-based methods frequently suffer from "metric distortion," where latent feature-space optimizations map to topologically invalid instances in the original input space. To resolve these theoretical impasses, we propose ECOer (Efficient Counterfactual Optimization with metric-preserving reconstruction regularization), a mathematically principled, end-to-end framework for post-hoc counterfactual generation for non-differentiable classifiers. ECOer constructs a ReLU-ReLU Single-hidden-layer Neural Network (R2SNN) as a differentiable surrogate, which we prove to possess tight universal approximation bounds for measurable decision regions. To preserve metric fidelity during latent-space search, we derive a novel metric-preserving reconstruction regularization mechanism grounded in Extreme Learning Machine (ELM) theory, ensuring that optimized features remain tied to the valid data manifold. Furthermore, we introduce a convex relaxation technique that yields a region-wise convex objective with zero relaxation gap within fixed decision regions. Extensive theoretical analysis and empirical evaluations on real-world benchmarks demonstrate that ECOer achieves a favorable trade-off between validity, proximity, plausibility, and online generation latency among the evaluated baselines. This work provides a rigorous algorithmic foundation for robust and reliable XAI in decision-critical tabular domains.