AdaFM: Adaptive Variance-Reduced Algorithm for Stochastic Minimax Optimization

-The authors consider a crude assumption that the gradients are bounded, compared to a more refined assumption of bounded variance which is much more standard in the literature.

-The authors seem to have missed an important point about adaptivity: which is adaptivity to the noise variance. Concretely, the complex learning rate in the STORM paper is designed to ensure that in the case where the variance is zero, then STORM guarantees the faster convergence rate known for the noiseless case. This does not apply to the current paper, and also cannot apply since they use a non-adaptive momentum of $1/t^{2/3}$, which can only provide rates that optimally match the noisy case.

-The authors do not compare the dependence of their convergence rate to the one of VARAdaGDA, in terms of $G,L$, it seems that the fact that they can take the constants $\gamma,\lambda$ to be $1$, may substantially degrade the performance with respect to $G,L$. This again means that the claimed adaptivity is not really beneficial.

-In term of proof/algorithmic techniques, I do not think that there is anything very novel or challenging.

• The results seem to only apply for SC and PL settings (since in the concave case, $\mu$ is zero - thus blowing up the final bound), which limits the application of the method.

I do not understand what exactly is adaptive about the proposed method.

More specifically, “adaptivity” in optimization typically means that there is some problem parameter (e.g. variance in gradients, smoothness constant, strong convexity constant etc) such that without prior knowledge of the parameter, the algorithm is able to achieve nearly the same convergence guarantee as would be possible given prior knowledge of the parameter. Usually this means that even if the algorithm has some hyperparameters, these parameters have minimal impact on the convergence guarantee. I don’t see how that occurs here.

The authors appear to not be considering the variance of the gradients (Assumption 2 is just a coarse Lipschitz bound), so the only parameter to “adapt” to is the condition number $\kappa$. However, the convergence guarantees do not explain the impact of the algorithm hyperparameters at all - it is all hidden in the big-Oh. Moreover, it appears that perhaps the dependence on $\kappa$ is not even correct: https://arxiv.org/pdf/2308.09604 appears to achieve a much better complexity of $\kappa^3/\epsilon^3$ in a non-adaptive way. This work appears to obtain $\kappa^{15}/\epsilon^3$ instead. I’m willing to believe that proper setting of $\lambda$ or $\gamma$ would alleviate this issue, but that is not obvious since the influence of these parameters was not provided in the theorem statement. Moreover, this would defeat the purpose of the adaptivity.

In summary, I don’t think this paper accomplishes the stated goal of adaptivity. Perhaps the authors meant a different goal, but if so they should clearly explain what they are trying to achieve and why it is desirable.

None.