Deep neural networks (DNNs), which underpin modern AI technologies, demand substantial computational resources, posing challenges for deployment on energy-constrained devices (e.g., battery-powered smartphones). A viable solution is to reduce the complexity of trained DNNs via approximate computing techniques, such as low-bit quantization or pruning, which significantly lower energy consumption with minimal impact on inference accuracy. In this paper, we adapt our AppMax method—originally developed for estimating regression error of approximated neural networks (NNs)—to upper-bound the cross-entropy loss between the output categorical probability distributions of a trained classification DNN with softmax (e.g., a convolutional NN) and its low-energy approximation. Using the concept of shortcut weights and optimal linear interpolation of the exponential function, AppMax bounds this loss via linear programming over convex polytopes around test/training data points, constrained to regions where the same category is originally inferred with high probability. Preliminary MNIST experiments show that AppMax identifies inputs with maximum cross-entropy loss, some of which are misclassified by the approximated NN (with reduced weight bitwidth), even though its overall accuracy on the test data is preserved. This error bound can be used to evaluate different approximation strategies and identify those that best balance accuracy and energy efficiency.