Suppose we want to minimize the objective function $f(x)$ with respect to $x\in \mathbb{R}^p$. Wtih a linear transformation of $x$, e.g., $z = Qx$ for a proper $Q\in\mathbb{R}^{p\times p}$, the new optimization problem minimizing $\tilde f(z) := f(Ax)$ is essentially the same with the original one.
However, if we choose to solve the optimization problems by gradient descent, the variable transformation does seem to affect the algorithmic performance. For an example, consider $f(x)$ to be the sum-of-squares loss for solving the linear system $y = Ax$. In this case, it is often recommended to first normalize the columns of $A$. Let $A^\top = Q^\top R^\top $ be a QR decomposition. Then, we can reformulate the linear system as $y = Rz$, where $z = Qx$. The normalization step essentially rescales each feature to be of the same unit. In practice, gradient descent (assume that the step-sizes are determined by line search) often converges faster in the normalized version.
For more complicated optimization problems, it will be harder to tell how a variable transformation might affect the gradient descent. Let's take PCA as an example. Let $X \in \mathbb{R}^{n\times p}$ to be a data matrix. Then, to extract the top $k$ principal components and the corresponding eigenvalues, one can (not necessary though) solve the following problem: $$\min_{V\in\mathbb{R}^{p\times k},\ \ \lambda\in\mathbb{R}^k} \|\frac{1}{n}X^\top X - VD(\lambda) V^\top\|, \tag{P}$$ subject to $V^\top V=I_p$, where $D(\lambda)$ represents the diagonal matrix constructed by $\lambda$. Now, let $Q\in\mathbb{R}^{p\times p}$ be a non-singular matrix and let $G$ be $(QQ^\top)^{-1}$. Then problem (P) can be transformed to $$\min_{U\in\mathbb{R}^{p\times k},\ \ \lambda\in\mathbb{R}^k} \|\frac{1}{n}X^\top X - Q^{-1}UD(\lambda) U^\top (Q^\top)^{-1}\|, \tag{Q}$$ subject to $U^\top G U=I_p$. Can we judge whether or not the transformation can affect the gradient descent?
I want to discuss the PCA example because I recently found a case where the (projected) gradient descent works significantly better in (P) than that in (Q). For (Q), the gradient iterations seem to be trapped in a local minimum.
