Dynamic Online Gradient Descent with Improved Query Complexity: A Theoretical Revisit
This work provides a theoretical improvement for online optimization in dynamic settings, particularly benefiting ill-conditioned problems, but it is incremental as it builds on existing frameworks.
The paper tackles the problem of reducing gradient query complexity in online gradient descent for dynamic environments, achieving a reduction from O(κ) to O(1) queries per iteration while maintaining state-of-the-art dynamic regret, which is significant for ill-conditioned problems with large κ.
We provide a new theoretical analysis framework to investigate online gradient descent in the dynamic environment. Comparing with the previous work, the new framework recovers the state-of-the-art dynamic regret, but does not require extra gradient queries for every iteration. Specifically, when functions are $α$ strongly convex and $β$ smooth, to achieve the state-of-the-art dynamic regret, the previous work requires $O(κ)$ with $κ= \fracβα$ queries of gradients at every iteration. But, our framework shows that the query complexity can be improved to be $O(1)$, which does not depend on $κ$. The improvement is significant for ill-conditioned problems because that their objective function usually has a large $κ$.