Motived by the experience with a large online marketplace, we study a middle-mile network design problem in e-commerce. One novel feature in our problem is that while we decide the network configuration, the network flow and shortfall are controlled by the fulfillment policy employed by a different decision entity and are unknown. We develop a predictive model for the unknown response using observed shipment data. In particular, we apply the idea of decomposition in developing the predictive model. The predictive model is then embedded in the network design. To solve this problem, we characterize it as a c-supermodular minimization problem and propose two linear time approximation algorithms. In a numerical study, we demonstrate that these two algorithms are scalable and effective.