Gradient computation is the methodological backbone of deep learning, but computing gradients can be challenging, in particular for some structured probabilistic models. Such models are of interest for a number of reasons, including improving interpretability, incorporating problem-specific constraints or improving generalization. Relaxed gradient estimators are a method to learn such models by optimizing a relaxed (surrogate) objective function during training. They incorporate bias in order to reduce variance, are easy to implement and often work well in practice. In my research, I develop relaxed gradient estimators and demonstrate their use for learning structured probabilistic models.