Deformable registration based multi-atlas segmentation has been successfully applied in a broad range of anatomy segmentation applications. However, the excellent performance comes with a high computational burden due to the requirement for deformable image registration and voxel-wise label fusion. To address this problem, we investigate the role of corrective learning (Wang et al., 2011) in speeding up multi-atlas segmentation. We propose to combine multi-atlas segmentation with corrective learning in a multi-scale analysis fashion for faster speeds. First, multi-atlas segmentation is applied in a low spatial resolution. After resampling the segmentation result back to the native image space, learning-based error correction is applied to correct systematic errors due to performing multi-atlas segmentation in a low spatial resolution. In cardiac CT and brain MR segmentation experiments, we show that applying multi-atlas segmentation in a coarse scale followed by learning-based error correction in the native space can substantially reduce the overall computational cost, with only modest or no sacrificing segmentation accuracy.