Understanding the factors that determine regional climate variability and change is a challenge with important implications for the economy, security, and environmental sustainability of many regions around the globe. Unprecedented quantities of high-resolution climate data provide an enormous opportunity to explore this question systematically and exhaustively. Simple, offthe-shelf machine learning and statistical analysis methods can yield misleading results when applied directly to such data. Standard model selection methods are fragile in the face of complex dependence structures in the climate system. This abstract describes a regression scheme that explicitly accounts for spatiotemporally correlated features via a regularization approach based on an underlying correlation graph. Using large ensemble climate outputs to estimate the strength of correlations among features, we form a graph with edge weights corresponding to pairwise correlations. This graph is used to define a graph total variation regularizer that promotes similar weights for highly correlated features. We apply our scheme to predicting winter precipitation totals in the southwestern US using sea surface temperatures (SST) over the entire Pacific basin at multiple time lags, and demonstrate that our method provides strong predictive performance.