Source-linked AI summary
Dynamical Models and Tracking Regret in Online Convex Programming
Eric C. Hall, Rebecca M. Willett
TL;DR
Online optimization often compares performance with static or slowly changing comparators, while dynamical models may be unknown or change over time. This paper introduces DMD and DFS to incorporate candidate dynamics and bounds regret by comparator deviation from those dynamics; DMD also shows strong tracking behavior under switching models in real and simulated data.
Problem
Method
Results
DMD shows strong tracking behavior on real and simulated data even when the underlying dynamical models switch.
Source: §8 · p. 8Takeaways & Limitations
Tracking regret can be bounded by comparator deviation from the best sequence of candidate dynamical models rather than only by raw comparator variation.
Source: §1 · p. 1, §6 · p. 6Fixed Share has linear complexity but its comparator class assumes a fixed number of switches; alternatives may incur higher regret or complexity.
Source: §6 · p. 6
Abstract
from arXiv · showhide
This paper describes a new online convex optimization method which incorporates a family of candidate dynamical models and establishes novel tracking regret bounds that scale with the comparator's deviation from the best dynamical model in this family. Previous online optimization methods are designed to have a total accumulated loss comparable to that of the best comparator sequence, and existing tracking or shifting regret bounds scale with the overall variation of the comparator sequence. In many practical scenarios, however, the environment is nonstationary and comparator sequences with small variation are quite weak, resulting in large losses. The proposed Dynamic Mirror Descent method, in contrast, can yield low regret relative to highly variable comparator sequences by both tracking the best dynamical model and forming predictions based on that model. This concept is demonstrated empirically in the context of sequential compressive observations of a dynamic scene and tracking a dynamic social network.
1. Introduction
The paper combines dynamical-model state updates with online convex optimization to make predictions and derive tracking-regret bounds for dynamic environments. It motivates the approach with streaming applications and high-dimensional, data-starved settings.
1. Introduction
- Classical filters typically require an accurate, fully known dynamical model and strong assumptions about how observations are generated.Existing performance analyses usually do not address model mismatch.Source: §1 · p. 1
- DMD combines dynamical-model state updates with online convex optimization, and its tracking-regret bounds scale with a comparator’s deviation from a known dynamic.The bounds simplify to previously shown bounds when there are no dynamics.Source: §1 · p. 1
- The framework targets high-dimensional, data-starved settings where dynamical modeling and sparsity regularization play a key role.The paper focuses on methods combining regularization with dynamical modeling.Source: §1 · p. 2
- Experiments consider motion-imagery reconstruction from compressive-camera observations and dynamic social-network estimation from more than 200 years of U.S. Senate rollcall data.The paper aims to bridge these streaming applications with methods that are typically batch-oriented.Source: §1 · p. 2
2. Problem formulation
The problem is framed as sequential prediction over a convex feasible set, with each prediction based only on observations already available. The analysis compares predictions with time-varying comparator sequences and seeks regret bounds that reflect their fit to a dynamical model.
2. Problem formulation
- The Forecaster predicts from the observations available so far, then receives the next observation and incurs a loss.The prediction at time t can depend only on observations through time t−1.Source: §2 · p. 2
- The loss combines a data-fit cost with a time-invariant regularizer that can promote sparsity or other low-dimensional structure.The data-fit term is a convex function of the prediction and the current observation.Source: §2 · p. 2
- The target is low regret against time-varying comparators, with a bound scaling by their deviation from a dynamical model rather than only covering static comparators.The passage contrasts this goal with prior O(√T) regret for static comparators.Source: §2 · p. 2
3. Static, tracking, shifting, and adaptive regret
Static regret compares an online method with one fixed comparator, while tracking regret considers a sequence of comparators. The paper measures sequence complexity by deviation from dynamical models, yielding a tracking-regret notion suited to comparators that follow those dynamics.
3. Static, tracking, shifting, and adaptive regret
- Static regret is regret against a time-invariant comparator, whereas tracking regret compares against a time-varying sequence chosen with full knowledge of the data.Tracking-regret analyses typically require a measure of comparator-sequence complexity.Source: §3 · pp. 2–3
- Existing tracking bounds often rely on piecewise-constant comparators or scale with the comparator’s temporal variability.These bounds characterize complexity through changes over time or switches.Source: §3 · p. 3
- The paper’s tracking-regret bounds use comparator deviation from a dynamical model, a more general complexity measure than temporal variation alone.For a family of models, comparator complexity is measured against the best sequence of dynamical models.Source: §3 · p. 3
- When a comparator follows the dynamics, its model-relative complexity can be small, even if the dynamics are not part of the observation-generating process.Setting the deviation to zero gives a dynamic analogue of static regret, comparing with a single trajectory under the model.Source: §3 · p. 3
- Unlike predictable-process methods that assume a good estimate of the data process and give static-regret bounds, this paper makes assumptions about comparators and bounds tracking regret.The contrasting methods include a variation term for deviation of input data from the underlying process.Source: §3 · p. 3
4. Online convex optimization
Online convex optimization updates predictions using loss information and a Bregman-divergence geometry. The section also describes composite mirror descent, which handles regularization separately from data fit to support sparse predictions.
4. Online convex optimization
- Mirror Descent forms a new prediction using a loss subgradient, a Bregman divergence from the current prediction, and a step-size parameter.The section presents it as a common approach to forming predictions.Source: §4 · p. 3
- Mirror Descent generalizes online gradient descent and weighted majority.The section also situates it alongside methods that separate data fit from regularization.Source: §4 · p. 4
- Composite Objective Mirror Descent separates data fit from regularization, which can make individual predictions sparse rather than approximately sparse.The passage identifies this as helpful when the regularizer promotes sparsity.Source: §4 · p. 4
5. Dynamical models in online convex programming
This section introduces Dynamic Mirror Descent (DMD), which extends tracking regret to dynamic comparators by measuring their deviation from a specified dynamical model. Unlike conventional tracking bounds for slowly changing or piecewise-constant comparators, this framework accommodates broader dynamic sequences.
5. Dynamical models in online convex programming
- Conventional tracking bounds typically cover piecewise-constant comparators or scale with their step-to-step variation, while the proposed bounds cover broader dynamic comparator sequences.The paper contrasts bounds based on comparator movement with bounds based on deviation from a dynamical model.Source: §5 · p. 4
- DMD balances minimizing loss with keeping predictions close to the comparator transformed by Φ_t, without assuming the model relates to observed data.The update is likened to a stochastic filter that uses dynamics to update a state before filtering.Source: §5 · p. 4
- With no dynamics, DMD is equivalent to COMID; extending tracking-regret bounds to regularized dual averaging remains an open problem.The paper suggests equivalence results between COMID and RDA might support such bounds, but leaves that proof open.Source: §5 · p. 4
- When ∆Φ_t≤0 and step sizes are nonincreasing, DMD’s tracking-regret bound scales with the comparator’s deviation from the dynamical model Φ_t.V_Φt(θT) measures this deviation.Source: §5 · pp. 4–5
- When Φ_t is the identity, Theorem 4 recovers existing tracking or shifting bounds; the ∆Φ_t≤0 condition is contraction-like and includes additive models and matrices with eigenvalues at most one.The paper notes that without this condition, repeated dynamics can magnify a poor prediction.Source: §5 · p. 5
6. Prediction with a family of dynamical models
Because the best dynamics may be unknown or change in nonstationary settings, the method uses a finite set of candidate models and comparators that can switch models over time. Its tracking-regret bound accounts for comparator deviation from the best model sequence as well as model-switching costs.
6. Prediction with a family of dynamical models
- A finite set of candidate dynamical models supports tracking when the best model is unknown or changes in a nonstationary environment.The comparator class allows different dynamical models on different time intervals.Source: §6 · p. 5
- The regret decomposition separates the algorithm’s tracking regret against switching model sequences from those sequences’ regret against comparators in Θm.The model sequences have at most m switches.Source: §6 · p. 5
- The overall expected tracking-regret bound includes an (m + 1)(log N + Dmax) term and a term measuring comparator deviation from the best model sequence.The best sequence uses m + 1 segments.Source: §6 · p. 6
- Choosing λ = m/T uses an upper bound on the number of switches that is independent of T; the doubling trick applies when T is unknown.The comparator-deviation term is no larger than that for any fixed candidate model.Source: §6 · p. 6
- The approach generally yields lower regret than using a fixed dynamical model, but incurs loss for not knowing the optimal switch count or times.That cost is accounted for in T1.Source: §6 · p. 6
- Fixed Share combines estimates from candidate dynamics with linear complexity and low regret for comparator classes with a fixed number of switches.Alternatives can handle larger expert classes or avoid assuming the switch count, at the cost of higher regret or complexity.Source: §6 · p. 6
7. Experiments and results
The experiments evaluate Dynamic Fixed Share (DFS) on compressed video reconstruction and Senate-vote network tracking. In both settings, the reported results show benefits from adapting to dynamical models, with the network estimates also exhibiting changing political factions.
7.1. Compressive video reconstruction
- The video experiment reconstructs 150 × 150 grayscale frames from sequential 500 × 22500 compressed observations with Gaussian noise of variance 1.The scene changes motion models between t = 1–240 and t = 241–500; the candidate family has nine models, including a static model.Source: §7.1 · p. 6
- DFS rapidly switches among motion models and outperforms every individual prediction, including the COMID baseline, in video reconstruction.The comparison shows NE motion performing well before t = 240 and SE motion after t = 240.Source: Figure 1 · p. 6, §7.1 · p. 6
7.2. Tracking dynamic social networks
- The network experiment tracks Senate-seat voting relationships from 1795 to 2011 using a negative-log Ising pseudolikelihood loss and a dynamical model of emerging shared connections.Votes are represented as +1 or −1, with 0 for unavailable votes.Source: §7.2 · p. 7
- Applying a dynamical model improves average per-round loss over COMID, and DFS successfully aggregates the model predictions.The comparison uses a 30-year time window.Source: Figure 3 · p. 7, §7.2 · p. 8
- DFS estimates show Senate factions forming after the Civil War, dissipating during the Civil Rights Movement, and forming again in more recent years.Seats are sorted separately in each matrix, and the groupings align with known political factions.Source: Figure 5 · p. 8, §7.2 · p. 8
8. Conclusion and future directions
The conclusion presents DMD and DFS as online methods that incorporate dynamical models without requiring a true, fixed model. Experiments with real and simulated data show strong tracking behavior when the underlying dynamics switch.
8. Conclusion and future directions
- DMD incorporates dynamical-model state updates without assuming a true known model or an unchanging best model.DFS adaptively selects the most promising candidate model at each time step.Source: §8 · p. 8
- The paper identifies adaptive regret bounds and automatic step-size tuning as possible applications of its techniques.The conclusion presents these as directions suggested by recent work on shifting or tracking regret bounds.Source: §8 · p. 8
- Experiments with real and simulated data show strong DMD tracking behavior even when the underlying dynamical models switch.Source: §8 · p. 8
9. Proofs
The proof of Lemma 5 uses an optimality condition to bound instantaneous regret, then combines inequalities justified by convexity and related inequalities.
9. Proofs
- The proof uses the optimality condition of (5a) to bound instantaneous regret.Source: §9 · p. 8
- Convexity of the loss and regularizer, together with the optimality condition, supports the intermediate inequality (14c).Source: §9 · p. 8
- Strong convexity of the Bregman divergence, Young’s inequality, convexity of ψ, and Cauchy–Schwarz yield bounds combined to complete the lemma.Source: §9 · p. 8