Applications with a dynamic workload demand need access to a flexible infrastructure to meet performance guarantees and minimize resource costs. While cloud computing provides the elasticity to scale the infrastructure on demand, cloud service providers lack control and visibility of user space applications, making it difficult to accurately scale the infrastructure. Thus, the burden of scaling falls on the user. That is, the user must determine when to trigger scaling and how much to scale. Scaling becomes even more challenging when applications exhibit dynamic changes in their behavior. In this paper, we propose a new cloud service, Dependable Compute Cloud (DC2), that automatically scales the infrastructure to meet the user-specified performance requirements, even when multiple user requests execute concurrently. DC2 employs Kalman filtering to automatically learn the (possibly changing) system parameters for each application, allowing it to proactively scale the infrastructure to meet performance guarantees. Importantly, DC2 is designed for the cloud - it is application-agnostic and does not require any offline application profiling or benchmarking, training data, or expert knowledge about the application. We evaluate DC2 via implementation on OpenStack using a multi-tier application under a range of workload mixes and arrival traces. Our experimental results demonstrate the robustness and superiority of DC2 over existing rule-based approaches with respect to avoiding SLA violations and minimizing resource consumption.