  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.
