Here are some general techniques to speed up hyperparameter optimization.
If you have a large dataset, use a simple validation set instead of cross validation. This will increase the speed by a factor of ~k, compared to k-fold cross validation. This won't work well if you don't have enough data.
Parallelize the problem across multiple machines. Each machine can fit models with different choices of hyperparameters. This will increase the speed by a factor of ~m for m machines.
Avoid redundant computations. Pre-compute or cache the results of computations that can be reused for subsequent model fits (or iteratively updated with less work than computing from scratch). A couple simple examples: if the model needs a pairwise distance matrix, compute all distances at the beginning, rather than re-computing them each time a model is fit. If the model needs a mean and covariance matrix, iteratively update them depending on the points in each training set, rather than computing from scratch.
If using grid search, decrease the number of hyperparameter values you're willing to consider (i.e. use a coarser grid). This can give potentially large speedups because the total number of combinations scales multiplicatively. The risk is that, if the grid becomes too coarse, you may miss the optimal values. You can compensate for this by performing an initial, coarse search, then performing a finer search in the neighborhood of the best initial values. This is safer than the first strategy, but there's still some risk that the initial, coarse search could end up in a suboptimal neighborhood from which the finer search can't escape.
Use random search. Bergstra and Bengio (2012) describe this strategy, and show that it can give large speedups compared to grid search. The reason is that model performance may be much more sensitive to some hyperparameters than others, and the important ones aren't known a priori. Grid search can waste iterations by trying many different values for non-influential hyperparameters while holding the influential ones fixed. Random search samples random hyperparameter values from some simple distribution, so all hyperparameters change on every iteration. Changing non-influential hyperparameters has little effect (so nothing is lost), and changing the influential ones gives more chance for improvement.
Whether using grid search or random search, make sure that the spacing between values is appropriate for each hyperparameter (in grid search, this is the grid spacing; in random search, it's related to the distribution from which hyperparameter values are sampled). For example, it makes sense to try linearly spaced values for some hyperparameters, and logarithmically spaced values for others. Using inappropriate spacing can either lead to poor coverage (increasing the risk of missing the optimal value) or require overly dense coverage to compensate (wasting computation time).
Use Bayesian optimization. This is a much more complicated approach, and is an active topic of research. In the context of hyperparameter optimization, it tries to learn a model of the loss function over hyperparameters, and use this model to adaptively choose the next hyperparameter values to try. The value of the loss function for the new hyperparameters is used in turn to update the model.
Bergstra and Bengio (2012). Random search for hyper-parameter optimization.