A huge number of edge applications including self-driving cars, mobile health, robotics, and augmented reality / virtual reality are enabled by deep neural networks (DNNs). Currently, much of this computation for these applications happens in the cloud, but there are several good reasons to perform the processing on local edge platforms such as smartphones: improved accessibility to different parts of the world, low latency, and data privacy. In this paper, we present a general hardware and software co-design framework for energy-efficient edge AI for both simple classification and structured output prediction tasks (e.g., 3D shapes from images). This framework relies on two key ideas. First, we design a space of DNNs of increasing complexity (coarse to fine) and perform input-specific adaptive inference by selecting a DNN of appropriate complexity depending on the hardness of input examples. Second, we execute the selected DNN on the target edge platform using a resource management policy to save energy. We also provide instantiations of our co-design framework for three qualitatively different problem settings: convolutional neural networks for image classification, graph convolutional networks for predicting 3D shapes from images, and generative adversarial networks on photo-realistic unconditional image generation. Our experiments on real-world benchmarks and mobile platforms show the effectiveness of our co-design framework in achieving significant gain in energy with little to no loss in accuracy of predictions.