Partially Lazy Gradient Descent for Smoothed Online Learning

1. Problem Definition: Smoothed Online Convex Optimization (SOCO)

The paper addresses the Smoothed Online Convex Optimization (SOCO) problem, a setting where a learner interacts with an environment over $T$ rounds.

• Objective: At each round $t$, the learner selects an action $x_t$ from a convex compact set $\mathcal{X}$.
• Costs: The learner incurs two types of costs:
  1. Hitting Cost: $f_t(x_t)$, a convex loss function revealed after the decision is made.
  2. Movement (Switching) Cost: $m(x_t, x_{t-1}) = \|x_t - x_{t-1}\|$, penalizing changes between successive decisions.
• Metric: The performance is measured by Dynamic Regret with Switching Cost:
  $$R_T = \sum_{t=1}^T (f_t(x_t) - f_t(u_t)) + \sum_{t=1}^{T-1} \|x_{t+1} - x_t\|$$
  where $\{u_t\}$ is an arbitrary comparator sequence with path length $P_T = \sum_{t=1}^{T-1} \|u_{t+1} - u_t\|$.
• Goal: Achieve a regret bound of $O(\sqrt{(P_T + 1)T})$, which is minimax-optimal.

2. Methodology: $k$-lazyGD

The authors propose $k$-lazyGD, an algorithm that interpolates between two classical extremes:

1. Greedy OGD ($k=1$): Updates based solely on the most recent gradient ($x_{t+1} = \Pi(x_t - \frac{1}{\sigma}g_t)$). It is highly reactive but incurs high switching costs.
2. Lazy GD / Dual Averaging ($k=T$): Updates based on the cumulative sum of all past gradients ($x_{t+1} = \Pi(-\frac{1}{\sigma}\sum_{i=1}^t g_i)$). It is highly stable (low switching) but fails to track non-stationary comparators, leading to linear regret in dynamic settings.

The $k$-lazyGD Mechanism:
The algorithm partitions the time horizon into phases of length $k$. Within each phase, it accumulates gradients (like Lazy GD) but re-initializes the accumulation at the start of the phase using the current iterate as an anchor.

• Update Rule:
  $$x_{t+1} = \Pi\left( x_{t-n_t} - \frac{1}{\sigma} \sum_{\tau=t-n_t}^{t} g_\tau \right)$$
  where $n_t = (t-1) \mod k$.
• FTRL Interpretation: The authors cast $k$-lazyGD as an instance of the Follow-the-Regularized-Leader (FTRL) framework. They introduce a "pruning" mechanism where, at the start of every $k$-th step, the accumulated state vector is replaced by the current iterate (via a specific normal cone correction term). This allows the algorithm to retain the stability of lazy methods while periodically "resetting" to maintain responsiveness.

3. Key Contributions

A. Theoretical Characterization of Laziness

The paper establishes a precise trade-off between laziness (stability) and responsiveness (tracking ability).

• Lower Bound: The authors prove that for any $k$-lazyGD algorithm, the dynamic regret is lower-bounded by $\Omega(k P_T)$. This implies that if $k$ is too large (specifically $k \gg \sqrt{T/P_T}$), the algorithm becomes too slow to track the comparator, resulting in suboptimal regret.
• Upper Bound & Optimal Slack: They prove that $k$-lazyGD achieves the optimal regret rate $O(\sqrt{(P_T + 1)T})$ provided the laziness slack $k$ satisfies:
  $$k \leq \Theta\left(\sqrt{\frac{T}{P_T}}\right)$$
  This formally identifies the maximum allowable "laziness" that does not compromise dynamic regret.

B. Properties of Lazy Updates

The analysis formalizes two geometric properties that $k$-lazyGD exploits to reduce switching costs without sacrificing hitting performance:

1. Iterate Staleness: If the new gradient does not change the minimizer of the accumulated sum within the current phase, the iterate remains unchanged ($x_{t+1} = x_t$). This happens more frequently with larger $k$.
2. Iterate Stability: Even when the iterate moves, the magnitude of the movement is attenuated. The movement is proportional to the deviation of the current gradient from the running mean of the phase, rather than the raw magnitude of the gradient.

C. Adaptive Ensemble Framework

Since the optimal $k$ depends on the unknown path length $P_T$, the authors propose an ensemble (meta-learning) approach.

• They run multiple instances of $k$-lazyGD in parallel, each with a different pair of parameters $(k, \sigma)$.
• Using the SAder meta-learner (from Zhang et al., 2021), they aggregate these experts.
• Result: The ensemble achieves the optimal $O(\sqrt{(P_T + 1)T})$ regret without prior knowledge of $P_T$, automatically adapting to the environment's non-stationarity.

4. Results

• Regret Guarantee: The proposed method achieves the minimax-optimal dynamic regret bound $O(\sqrt{(P_T + 1)T})$.
• Switching Cost Reduction: Empirical results and theoretical bounds show that $k$-lazyGD significantly reduces switching costs compared to standard Greedy OGD ($k=1$), often matching the low switching costs of fully Lazy GD ($k=T$) while maintaining competitive hitting costs.
• Simulation Evidence: Experiments on stochastic shifting sequences and corrupted deterministic sequences demonstrate that $k$-lazyGD outperforms standard OGD by up to 45% in total regret. The ensemble method (SAder-k) further improves performance by automatically selecting the optimal $k$ for the specific sequence.

5. Significance

• Bridging the Gap: This work resolves the long-standing tension between stability (low switching) and responsiveness (low dynamic regret) in SOCO. It demonstrates that one does not need to choose between the extremes of Greedy and Lazy updates; a "partially lazy" approach is optimal.
• Theoretical Insight: It provides the first formal characterization of the "laziness slack" $k$ in dynamic settings, showing that the allowable accumulation of past gradients is inversely proportional to the comparator's path length.
• Practical Applicability: By proving that laziness can be retained without sacrificing tracking ability, the paper offers a robust algorithm for real-world applications where switching costs are high (e.g., data center cooling, portfolio rebalancing, or network routing) but the environment is non-stationary.
• FTRL Generalization: The introduction of the "pruning" trick within the FTRL framework offers a new tool for designing online learning algorithms that can control memory and responsiveness dynamically.

In summary, $k$-lazyGD is a novel algorithm that unifies the best properties of greedy and lazy updates, achieving optimal dynamic regret while significantly reducing unnecessary movement through a principled, phase-based accumulation of gradients.