General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization

Yes

This is a solid theory paper on extending the theoretical understanding of schedule-free methods to nonconvex optimization. The main contribution is the development of a general framework for online-to-nonconvex conversion, which converts a given online learning algorithm into a nonconvex optimization algorithm. By specifying the choice of sequences, this framework can recover existing conversions and also leads to two new conversion schemes that cover the schedule-free SGD method. Overall, I found the contribution of this work very fundamental, and the developed framework may spark new research directions on nonconvex optimization algorithm design and analysis.

Most claims in this paper are supported by rigorous mathematical proofs. However, I have some reservations regarding the practical insights provided by the analysis.

• The authors observe that under their framework, the choice of $\kappa_t$ for schedule-free SGD is close to 1, which aligns with the empirical observations in Defazio et al. (2024). On the other hand, other aspects of the parameter selection do not exactly match practical choices. Specifically, in Defazio et al. (2024), the choice of $c_t$ is independent of $\kappa_t$ and scales as $1/t$, which is different from the suggestion in Proposition 5.2. Due to this discrepancy, it seems unclear which formulation better explains the empirical success of schedule-free SGD.

• At the end of Section 5, the authors claim that the learning rate $\gamma$ for schedule-free SGD is $\Theta(\frac{(G+\sigma)^2}{\epsilon^2})$ times larger than the optimal step size for SGD with momentum. However, in Proposition 5.2, $\gamma$ is compared to the OMD step size $\eta_*$ for the online learning problem, which does not directly correspond to the step size in SGD with momentum. In fact, as mentioned by the authors, SGD with momentum corresponds to Option I with OMD as the online learner. Following the reformulation in Zhang and Cutkosky (2024), the effective learning rate for SGD with momentum is given by $\frac{\beta \eta}{\eta \mu + \alpha} = \frac{\eta \xi}{1- \xi}$. Since $\xi$ is close to 1 in the considered setting, the learning rates only differ by a constant close to 1. Hence, the analysis does not necessarily suggest a much larger learning rate than SGD with momentum.

The paper is well-written and easy to follow. However, one potential concern is that its theoretical contribution may not be significantly more substantial than that of Zhang and Cutkosky (2024), as it builds upon the same key concepts and techniques. While the authors introduce two new conversion schemes within their new framework, all proposed schemes ultimately achieve the same convergence guarantees (up to a constant). This raises the question of what advantages the newly proposed schemes offer beyond the existing approach.

Yes.

Designing and analyzing algorithms for the nonconvex and non-smooth setting is a very interesting direction. Given that SFO works so well in practice, it is very interesting to see that it is optimal for the nonconvex and non-smooth setting and that the parameter choices required to achieve optimal rates for this variant of schedule-free SGD correspond to those that lead to the best empirical performance.

All the claims made in this paper are supported by sufficient evidence.

Strengths:

• This paper follows a good structure, the writing is good and most claims are presented with sufficient explanations to help explain the main results.
• The designed random EMA iterate is a novel scheme that allows for improved convergence results and is consistent with practical applications.
• The convergence analysis provided in this work is solid and based on relatively mild assumptions.

Weaknesses:

• I think including some experimental results possibly in some simple settings could help illustrate the behavior of the presented algorithms and potentially help clarify the advantage of schedule-free methods for non-convex optimization.