Quantum error mitigation techniques promise to suppress noise on current small-scale hardware, without the need for fault-tolerant quantum error correction. One method in this family of mitigation techniques is the quasiprobability method that simulates a noise-free quantum computer with a noisy one, with the caveat of only producing the correct expected values of measurement observables. The cost of a quasiprobability simulation manifests as a sampling overhead which scales exponentially in the number of error-mitigated gates in the circuit. In this work, we present two novel approaches to reduce the exponential basis of that overhead. First, we introduce a robust quasiprobability method that allows for a tradeoff between the approximation error and the sampling overhead via semidefinite programming. Second, we derive a new algorithm based on mathematical optimization that aims to choose the quasiprobability decomposition in a noise-aware manner. Both techniques lead to a significantly lower overhead compared to existing approaches.