Implicit Interpretation of Importance Weight Aware Updates
This provides theoretical justification for IWA updates, addressing a bottleneck in convex machine learning optimization, though it is incremental as it builds on existing frameworks.
The paper tackles the problem of learning rate tuning in subgradient descent by analyzing Importance Weight Aware (IWA) updates, showing for the first time that they have a strictly better regret upper bound than plain gradient updates in online learning.
Due to its speed and simplicity, subgradient descent is one of the most used optimization algorithms in convex machine learning algorithms. However, tuning its learning rate is probably its most severe bottleneck to achieve consistent good performance. A common way to reduce the dependency on the learning rate is to use implicit/proximal updates. One such variant is the Importance Weight Aware (IWA) updates, which consist of infinitely many infinitesimal updates on each loss function. However, IWA updates' empirical success is not completely explained by their theory. In this paper, we show for the first time that IWA updates have a strictly better regret upper bound than plain gradient updates in the online learning setting. Our analysis is based on the new framework, generalized implicit Follow-the-Regularized-Leader (FTRL) (Chen and Orabona, 2023), to analyze generalized implicit updates using a dual formulation. In particular, our results imply that IWA updates can be considered as approximate implicit/proximal updates.