Source-linked AI summary
Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient
Tianbao Yang, Lijun Zhang, Rong Jin, Jinfeng Yi
TL;DR
The paper studies dynamic regret when a clairvoyant’s minimizers change slowly, addressing the need for regularity constraints on loss sequences. It develops path-variation lower and upper bounds under true, noisy, stochastic-gradient, and two-point bandit feedback, with optimal guarantees in the stated settings.
Problem
Dynamic regret cannot be sublinear for arbitrary loss sequences, motivating regularity constraints based on how quickly the clairvoyant’s minimizers change.
Method
The paper introduces path variation and derives lower bounds alongside online-learning upper bounds for true, noisy, stochastic-gradient, and two-point bandit feedback.
Results
The achieved upper bounds are optimal for non-strongly convex losses when the clairvoyant moves slowly, including matching full-information performance under a stated smooth-loss condition.
Takeaways & Limitations
Path variation provides a basis for optimal dynamic-regret guarantees across the paper’s stated feedback settings when the clairvoyant moves slowly.
Takeaways & Limitations
The analysis assumes Lipschitz-continuous losses and bounded feasible domains, and leaves the optimal path-variation regret for strongly convex losses open.
Abstract
from arXiv · showhide
This work focuses on dynamic regret of online convex optimization that compares the performance of online learning to a clairvoyant who knows the sequence of loss functions in advance and hence selects the minimizer of the loss function at each step. By assuming that the clairvoyant moves slowly (i.e., the minimizers change slowly), we present several improved variation-based upper bounds of the dynamic regret under the true and noisy gradient feedback, which are {\it optimal} in light of the presented lower bounds. The key to our analysis is to explore a regularity metric that measures the temporal changes in the clairvoyant's minimizers, to which we refer as {\it path variation}. Firstly, we present a general lower bound in terms of the path variation, and then show that under full information or gradient feedback we are able to achieve an optimal dynamic regret. Secondly, we present a lower bound with noisy gradient feedback and then show that we can achieve optimal dynamic regrets under a stochastic gradient feedback and two-point bandit feedback. Moreover, for a sequence of smooth loss functions that admit a small variation in the gradients, our dynamic regret under the two-point bandit feedback matches what is achieved with full information.
1. Introduction
The paper studies dynamic regret against a clairvoyant sequence of loss minimizers and uses path variation to capture how quickly those minimizers move. It establishes matching variation-based lower and upper bounds under full-information, true-gradient, stochastic-gradient, and two-point bandit feedback.
- Problem: Online convex optimization compares an online learner with a clairvoyant that selects each loss function's minimizer in advance.Dynamic regret is more demanding than static regret because the comparator changes over time.
- Problem: Sublinear dynamic regret requires regularity, so the paper measures temporal changes in optimal solutions using path variation.The metric accounts for potentially non-unique minimizers.
- Contributions: The paper presents a general lower bound depending solely on path variation and achieves optimal O(V p_T) dynamic regret under true gradients for a restricted smooth-function family.The true-gradient result applies to smooth functions with vanishing gradients in the feasible domain.
- Contributions: Under noisy gradient feedback, the paper gives a lower bound depending on path variation and T, then matches it with O(·) regret under stochastic gradients and two-point bandit feedback.The upper bound is achieved by online gradient descent with an appropriate step size.
- Contributions: For smooth losses with small gradient variation, the two-point bandit bound can match the full-information bound.The paper distinguishes its two-point bandit feedback from prior noisy one-point bandit feedback.
- Related work: Unlike prior variation measures based on function changes or simplex geometry, this work focuses on Euclidean OCO with noisy gradient feedback.Earlier analyses considered functional variation, gradient variation, or related comparator variation under different feedback models.
2. Optimal Dynamic Regret with Noiseless Information
The section establishes path-variation lower bounds and matching noiseless-feedback upper bounds for dynamic regret when the clairvoyant’s minimizers move slowly. Full information and suitable gradient feedback achieve rates governed by path variation under stated smoothness and vanishing-gradient conditions.
- Overview: The analysis seeks optimal dynamic regret bounds dependent solely on path variation, first establishing lower bounds and then matching upper bounds.The noiseless settings considered are full-information feedback and true-gradient feedback for suitable smooth losses.
- Lower bound: For any γ ∈(0, 1), the lower bound rules out improving the path-variation dependence to O((V p_T)^α) with α < 1.The paper identifies this as a novel lower-bound consequence of the constructed family.
- Lower bound: No policy can guarantee sublinear dynamic regret for unrestricted loss sequences, motivating a path-variation constraint.The lower-bound construction uses quadratic losses with independently sampled minimizers over a bounded feasible domain.
- Full information: Full information achieves an O(max(V p_T, 1)) dynamic regret bound, comparable to prior variation-based full-information results.The section also presents the full-information update after each submitted decision.
- Gradient feedback: In the analyzed batch instances, OGD reaches the minimizer after each batch’s first iteration, so decision–minimizer mismatch occurs only at batch starts.The construction uses constant-step-size OGD and yields the stated dynamic-regret behavior for the examples.
3. Optimal Dynamic Regret with Noisy Gradient
The paper establishes lower and upper dynamic-regret bounds for noisy-gradient settings, showing optimal rates under stochastic-gradient and two-point bandit feedback. For smooth losses, two-point bandit feedback can exploit gradient variation to match the path-variation lower bound.
- 3.1. A Lower Bound with Noisy Gradient Feedback: Noisy-gradient feedback is modeled as a subgradient perturbed by random noise with zero mean, bounded covariance trace, and a distributional regularity condition.The paper also notes that bounded-variance Gaussian noise satisfies these assumptions.
- 3.1. A Lower Bound with Noisy Gradient Feedback: A lower bound shows that no policy can generally improve on the noisy-feedback rate characterized by path variation and the time horizon.The result applies under the stated noise assumptions and rules out uniformly better rates for arbitrary loss sequences.
- 3.3. Online Learning with Bandit Feedback: Two-point bandit feedback achieves the same order as stochastic gradient feedback for general Lipschitz losses when regret is averaged over the two decisions.The construction uses randomized perturbations and an unbiased stochastic gradient of a smoothed loss.
- 3.3. Online Learning with Bandit Feedback: For smooth losses, adjusting the two-point bandit step size yields a gradient-variation-dependent bound that matches the path-variation lower bound when gradient variation is small.The result is stated for sequences satisfying both path-variation and gradient-variation constraints.
- 3.2. Online Learning with Bounded Stochastic Gradient Feedback: OGD with an appropriately chosen step size achieves an optimal path-variation dynamic-regret bound under bounded stochastic gradient feedback.The update projects a noisy-gradient step onto the feasible set, with the bound depending on gradient and noise magnitudes.
- 3.3. Online Learning with Bandit Feedback: The bandit analysis builds on prior static-regret methods and extends the improved smooth-loss guarantee to linear losses.The paper attributes the improvement to choosing a different step size and notes a corresponding extension for linear losses.
4. Conclusions
The paper develops optimal path-variation-based dynamic-regret bounds for non-strongly convex losses under true and noisy gradient feedback when the clairvoyant moves slowly, while leaving the strongly convex case open.
- 4. Conclusions: The achieved upper bounds are optimal against the presented lower bounds for non-strongly convex losses under true and noisy gradient feedback.The bounds are based on path variation, which measures temporal changes in the optimal solutions.
- 4. Conclusions: The optimal dynamic-regret bound for strongly convex losses in terms of path variation remains open.This is identified as an unresolved question in the conclusion.
B. Proof of Theorem 8
The proof combines the random-direction construction with bounded noisy-gradient quantities and intermediate inequalities to derive the stated bandit-feedback bound.
- B. Proof of Theorem 8: A random unit vector is introduced as part of the proof’s randomized perturbation construction.The proof then invokes a lemma before proceeding with the bound derivation.
- B. Proof of Theorem 8: The noisy-gradient update is treated as OGD on a sequence of smoothed functions, with the estimated gradient bounded by Gd.The proof follows the structure of an earlier lemma and combines this bound with subsequent inequalities.
- B. Proof of Theorem 8: The proof combines an intermediate inequality with Lemma 13 to obtain a term involving (r2 + 2rBT )G2d2T + G(3R1 + R2).This expression is the stated intermediate result in the supplied proof passage.
B.1. Proof of Lemma 10
The proof of Lemma 10 is obtained by applying the Lipschitz property of the loss functions and combining the resulting inequalities.
- B.1. Proof of Lemma 10: The proof invokes the Lipschitz property of ft(w) to establish the needed inequality.This is the main analytic property identified in the supplied proof passage.
- B.1. Proof of Lemma 10: The resulting inequalities are combined to complete the lemma’s bound.The supplied passage records the combination step without stating the full intermediate expressions.
C. Proof of Theorem 9
The proof of Theorem 9 assembles several lemmas, largely following earlier analyses, and bounds three summation terms to obtain the result.
- The proof follows the analysis of Chiang et al. (2013), with some lemma proofs omitted because they are identical.Constants independent of T are denoted by O(1).
- The proof of one lemma is deferred to a later part of the paper.
- Several intermediate lemmas are inherited from or follow the same arguments as earlier lemmas in Chiang et al. (2013).
- The analysis uses convexity of f_t(w), Lipschitz properties, and a smoothness parameter L.
- The proof proceeds by bounding the three summation terms on the right-hand side.
C.1. Proof of Lemma 11
The proof of Lemma 11 invokes the Lipschitz property and develops bounds involving repeated expressions in f_t evaluated at neighboring iterates.
- The argument begins from the Lipschitz property.