Climate data seriously challenges the state of the art in predictive modeling. This challenge comes from both the nature of the data itself as well as the nature of the problems that need to be solved. Prediction in climate science is strongly tied to the study of possible climate change, attribution of causes to such change, and adaptation and mitigation efforts that must follow; delays in detecting such changes can have overwhelming costs, in terms of economic impact as well as human lives and habitat loss. Therefore, we are developing generalizations of non-parametric regression models suitable for climate data, i.e., spatio-temporal, multivariate, and potentially nonlinear datasets. In addition, we are investigating an array of techniques to improve predictions of climate extremes, which have traditionally been analyzed using statistical approaches rooted in extreme value theory but require substantial advances for application to large-scale, high-resolution climate applications such as regional prediction or downscaling.