In my experience, textbooks and tutorials on approximate inference often make claims like "inference is hard because computing the (log) partition function is hard." I don't doubt that computing the log partition function is hard, but I do fail to see why that is "the" barrier to inference.

1. We need the partition function to compute expected values. If we only know the unnormalized distribution $p^*(\mathbf{x};\boldsymbol{\theta}) = \exp\left(\boldsymbol{\phi}(\mathbf{x})^\top\boldsymbol{\theta}\right)=p(\mathbf{x};\boldsymbol{\theta})Z(\boldsymbol{\theta})$, then we also only know $\mathbb{E}[f]$ up to scaling by $Z(\boldsymbol{\theta})$.
2. Exact inference is #P-Hard in the worst case.
3. If we have the gradient of the log partition function, then we have the mapping between natural parameters and mean parameters, $$\nabla_\boldsymbol{\theta} \log Z(\boldsymbol{\theta}) = \mathbb{E}\left[\boldsymbol{\phi}(\mathbf{x})\right]\equiv\boldsymbol{\mu} \quad ,$$ and knowing the mean parameters $\boldsymbol{\mu}$ can aid in other stages of inference or in computing expected values in some circumstances (e.g. if $f$ lies in the span of $\boldsymbol{\phi}$, then $\mathbb{E}[f]$ is linear in $\boldsymbol{\mu}$).

Consider this thought experiment: imagine you are given an oracle who computes $Z(\boldsymbol{\theta})$ efficiently. What can you now do that you could not do before? Take bullet (1) above - can you now compute expected values more easily? It seems to me that there remains a difficult problem, namely computing a high-dimensional integral over $\mathbf{x}$. In fact, much of the space may have negligible probability mass. Personally, I would rather have an oracle that tells me which regions of $\mathbf{x}-$space to look in -- solve the search problem for me. This is how Self-Normalized Importance Sampling (SNIS) works - you draw samples from a proposal distribution that is essentially guess about where $\mathbf{x}$ has non-negligible mass, then plug in an estimate of $Z(\boldsymbol{\theta})$ based on those samples, namely $$\hat{Z}(\boldsymbol{\theta}) = \frac{1}{S}\sum_{i=1}^S p^*(\mathbf{x}^{(i)};\boldsymbol{\theta}) \qquad \mathbf{x}^{(i)}\sim q(\mathbf{x})\quad.$$ The hard problem in SNIS is constructing a good proposal distribution $q$, then you get $Z(\boldsymbol{\theta})$ "for free."

EDIT: to clarify, the kind of problem I have in mind is where $\mathbf{x}$ is a latent variable in a graphical model with conditional exponential family distributions, as is the focus of Wainwright & Jordan (2008), for instance. Finding an optimal $\boldsymbol{\theta}$ may be a variational inference problem. Conditioned on some data, another common problem would be drawing posterior samples of $\mathbf{x}$.

In my experience, textbooks and tutorials on approximate inference often make claims like "inference is hard because computing the (log) partition function is hard." I don't doubt that computing the log partition function is hard, but I do fail to see why that is "the" barrier to inference.

1. We need the partition function to compute expected values. If we only know the unnormalized distribution $p^*(\mathbf{x};\boldsymbol{\theta}) = \exp\left(\boldsymbol{\phi}(\mathbf{x})^\top\boldsymbol{\theta}\right)=p(\mathbf{x};\boldsymbol{\theta})Z(\boldsymbol{\theta})$, then we also only know $\mathbb{E}[f(\mathbf{x})]$ up to scaling by $Z(\boldsymbol{\theta})$.
2. Exact inference is #P-Hard in the worst case.
3. If we have the gradient of the log partition function, then we have the mapping between natural parameters and mean parameters, $$\nabla_\boldsymbol{\theta} \log Z(\boldsymbol{\theta}) = \mathbb{E}\left[\boldsymbol{\phi}(\mathbf{x})\right]\equiv\boldsymbol{\mu} \quad ,$$ and knowing the mean parameters $\boldsymbol{\mu}$ can aid in other stages of inference or in computing expected values in some circumstances (e.g. if $f$ lies in the span of $\boldsymbol{\phi}$, then $\mathbb{E}[f(\mathbf{x})]$ is linear in $\boldsymbol{\mu}$).

Consider this thought experiment: imagine you are given an oracle who computes $Z(\boldsymbol{\theta})$ efficiently. What can you now do that you could not do before? Take bullet (1) above - can you now compute expected values more easily? It seems to me that there remains a difficult problem, namely computing a high-dimensional integral over $\mathbf{x}$. In fact, much of the space may have negligible probability mass. Personally, I would rather have an oracle that tells me which regions of $\mathbf{x}-$space to look in -- solve the search problem for me, e.g. by providing a set of samples of $\mathbf{x}$ from the posterior or something close to it. Digging into this notion of ``search'' a little deeper, note that this is how Self-Normalized Importance Sampling (SNIS) works: you draw samples from a proposal distribution that is essentially guess about where $\mathbf{x}$ has non-negligible mass, then plug in an estimate of $Z(\boldsymbol{\theta})$ based on those samples, namely $$\hat{Z}(\boldsymbol{\theta}) = \frac{1}{S}\sum_{i=1}^S p^*(\mathbf{x}^{(i)};\boldsymbol{\theta}) \qquad \mathbf{x}^{(i)}\sim q(\mathbf{x})\quad.$$ The hard problem in SNIS is constructing a good proposal distribution $q$, then you get $Z(\boldsymbol{\theta})$ "for free."