I'm struggling to wrap my head around how GBM and XGBoost are mathematically related. Specifically, I don't know how to relate the steps described in the XGBoost vignette to the steps of the gradient tree boosting algorithm described here. I get that an important difference is that XGBoost minimizes a regularized objective while GBM simply minimizes the loss function. But does XGBoost otherwise have the same basic structure, i.e. does it at each iteration compute the negative gradients of the objective function for the previous iteration, fit a tree to them and then add the leaf predictions of this tree to the predictions from the previous iteration?
Yes; your understanding is correct. XGBoost is a gradient boosting algorithm and it does perform the operations you describe. Realistically the main difference is that with XGBoost we use the Hessian information while standard GBM works only with the first derivatives. That means that XGBoost is much more efficient when it comes to optimising against our loss function. There is an exceptional answer on CV.SE going in more detail at: XGBoost Loss function Approximation With Taylor Expansion That has been a significant difference of XGBoost to prior GBM algorithms methodologically. Let me note that some other boosting implementations (e.g. MatrixNET, LambdaMART) that already used the Hessian information for Newton steps but they were not widely used and had specialised applications - recommender systems. (Yes, of course XGBoost had further features like sparsity-aware learning, weighted quantile sketch for split proposal calculation, etc. but those are focused on tree-growing.)