R1: Comparison with inexact methods Aligning with prior exact papers [10, 18], we focus on comparisons with exact

We thank all five reviewers for their detailed and incisive feedback. We tested AustereMH [16], an inexact method, on robust linear regression in Section 5.1 with We added this to the Appendix. This does not affect the properties of TunaMH. Our theorem doesn't have this assumption; it suggests that for MHSubLhd with given user-specified The impact is 3-fold: it (1) provides an upper bound on performance for algorithms of Algorithm 1's TunaMH); (3) suggests directions for developing new algorithms. To be significantly faster than TunaMH, we either need more assumptions about the problem or new stateful algorithms.