Descent with Misaligned Gradients and Applications to Hidden Convexity

Thank you for your positive review! Below we address your questions:

1. The update in line 6 is essentially performing a projection. It’s possible that replacing this line with an ordinary projection to the sphere of radius $D$ would yield a similar final result, but it is not clear how to show such a thing. Instead, line 6 adds a correction to the update that still guarantees that the iterates do not grow too large (similar to projections), but can be integrated more easily into the calculations.
2. Yes, strong convexity should help in these cases. However, notice that unlike in standard convex optimization settings, we cannot simply regularize a non-strongly convex objective to become strongly convex because this would eliminate the correlation property and it is not clear what effect this would have on the analysis.
3. This is a nice idea and thank you for the suggestion, but unfortunately, it does not seem to help. Notice that the total number of gradient evaluations is $N=\sum_{t=1}^T B_t$, so with $B_t=\Theta(t)$, we’d have $N=\Theta(T^2)$. Thus, a convergence bound of $O(1/\sqrt{T})$ is actually $O(1/N^{1/4})$, which is worse than our $O(1/N^{1/3})$ result. Please let us know if we are missing something here!

Thanks very much for your review. Below we address some of the points you have raised:

Regarding comparison to known bounds: In the setting of Section 3, we are not aware of any works that consider exactly our setting, but we note that the dependence on $N$ is certainly tight due to standard bounds with unbiased gradients. As discussed in the response to reviewer SpNX, our results in Section 3 and 4 improve upon those of Ajalloeian & Stich 2020 by either weakening assumptions of improving the convergence bound from $O(1/N^{1/4})$ to $O(1/N^{1/3})$. In Section 5, we improve upon the $O(1/N^{1/4})$ rate obtained by Chen et al. 2022 to $O(1/N^{1/3})$.

Regarding the assumption statements: Thank you for your suggestion. In the revision we will present them formally as numbered Assumptions and refer to them in the Theorem restatements.

Regarding tightness: our first result is tight in the dependence on $N$ ($O(1/N^{1/2})$) as this is the lower bound even for exact gradient oracles. For the other results (or the dependencies on the $\mu$ and $\lambda$ parameters), our results are the best in their respective classes, but we are not aware of any lower bounds that apply.

Regarding the analysis novelty: Our analysis is unique in several respects. For example, our analysis for Section 3.2 makes critical use of a “stability” property enjoyed by anytime averaging (but not by the “standard” Polyak averaging). This stability is very rarely present in the literature. We also have never seen any result similar to our technique for viewing projection onto a sphere with the $\ell_2$-norm as projection onto a different unknown convex set using an unknown norm of interest (Lemma 3.1). In Sections 4 and 5, we introduce novel techniques to control the norm of the updates that were more analytically tractable than standard projections.

Regarding the questions:

1. Obtaining high-probability statements should be a fairly straightforward exercise, but it would unduly complicate the analysis. Note that all of our results involve summing up expected values of certain quantities. The difference between the realized value and the expected value is thus controllable with standard martingale concentration (e.g., Azuma–Hoeffding) bounds. Thank you pointing this out - we will remark on this in the revision.
2. Yes, you are correct. In our analysis $\nabla f$ can indicate an arbitrary subgradient whenever the gradient does not exist. Thank you for noticing this. We will clarify this point in the revision.

Thank you very much for your comments; they will be very helpful in improving our work!

Regarding the use of misaligned gradients, we believe that there is a misunderstanding. In all three sections of the paper, we consider misaligned gradients. Specifically, in

• Section 3, we assume that the expected gradient is obtained by multiplying the true gradient with a PSD matrix (unobserved); further, these matrices do not change much over time.
• Section 4, we consider a more general setup, where the expected gradient is simply assumed to be correlated with the true gradient. We also require a lower bound on the norm of the expected gradient.
• Section 5, we consider the setting of hidden convexity – here we wish to minimize a (non-convex) function f that can be expressed as a convex function after a non-linear transformation, i.e., $f(x) = C(P(x))$ where $C$ is convex and $P$ is a non-linear coordinate transform. Here, we obtain an unbiased estimate of the gradient of $f$; however, due to the transformation, this can be viewed as a misaligned gradient for $C$.

In the revision we will clarify our setting to avoid this confusion.

Regarding the questions,

1. It’s possible that there is a connection here, but it is certainly not obvious as there are several key differences in our usage. For example, we do not use the matrices as explicit preconditioners to form updates because we never actually observe these matrices at all!
2. Note that Beznosikov et al. assume strongly-convex losses, which we do not assume. As discussed in our paper, the standard conversion from non-strongly convex to strongly-convex via regularization does not obviously apply here. Moreover, it appears that the assumptions of Beznosikov et al. are actually stronger than ours - their Definition 2 in fact forces gradient estimates that decay to zero when the true gradient goes to zero. Our setting explicitly does not require this and so is able to obtain asymptotic convergence even in the presence of persistent bias. Thank you for bringing this to our attention - we will incorporate this discussion into the revision.
3. The use of hidden convexity by Shu, Ramachandran, and Wang is very different from ours. They consider a convex objective with a constraint that is non-convex, but for which it is possible to replace the constraint with a convex constraint without changing the objective value. Thus, the problem can be reformulated as a convex optimization problem. Our problem cannot be reformulated as a convex optimization problem.

Thank you for your work reviewing our paper! Below we answer your questions:

1. Thank you for pointing this out. Fortunately, the boundedness of the biased gradients holds in practice on many neural network tasks. See, e.g., the recent work of Defazio et al., where in Figure 3 they show that the assumption holds for commonly-studied models such as wide ResNet, IWSLT14, GPT, RoBERTa, DLRM, MRI, ViT, RCNN. (See also Figure 3 in Zhao et al., ICML 2022 and Figure 3 in Xiong et al., ICML 2020.) Note that even with this assumption, our analysis turns out to be rather nontrivial. Removing the boundedness assumption from our algorithm/analysis is an interesting open question and we will mention it in the revision.

2. The setting of Ajalloeian & Stich 2020 still requires that the bias is “smaller” than the true gradient (their $m\le 1$ condition in Assumption 4). While our setting 3 also requires the bias to vanish as the gradient approaches zero, it does not require the bias to be smaller than the gradient. This is a significant difference that makes analysis much more complicated because intuitively we cannot rely on the “sign” of the biased gradient to tell us the sign of the true gradient. Moreover, their bounds are worse: the relevant comparison is their Theorem 4, which implies convergence in gradient norm squared at a rate of $O(1/\epsilon^2)$, which implies function value convergence at a rate $O(1/\epsilon^4)$.

In contrast, in Section 4, our setting explicitly allows the bias to not vanish when we approach a solution, so it is unlikely that the condition in Ajalloeian & Stich 2020 would imply our assumptions. We consider this to be an interesting feature of the misalignment assumption: it provides a natural way to model non-vanishing bias that nevertheless allows for asymptotic convergence guarantees.

Thank you for suggesting these detailed comparisons - we will add them to the discussion in the paper!