Online Algorithms: From Prediction to Decision

Chen, 2018

Category: Online Algorithms

Overall Rating

3.3/5 (23/35 pts)

This paper presents a valuable conceptual framework: designing online decision algorithms whose structure... is deliberately adapted to the statistical structure of prediction errors, modeled via an effective impulse response function.
The most actionable path lies in exploring whether modern complex time-series forecasting errors (from deep learning, etc.) can be reliably characterized in terms of such an impulse response.
If feasible, this framework offers a principled method for tailoring control algorithms to specific error properties, providing an alternative to purely data-driven end-to-end approaches which can lack theoretical guarantees.
...realizing its practical value for modern predictors requires solving a significant, unaddressed challenge: reliably characterizing complex, non-linear forecasting errors within this structured model.

This thesis introduces a significant contribution by proposing a general, structured model for prediction errors in online convex optimization problems with switching costs, moving beyond restrictive adversarial or simple i.i.d. noise assumptions.
Crucially, the model represents prediction error as filtered white noise, characterized by an impulse response function f(t).
This thesis provides a framework to characterize these complex prediction errors quantitatively via their effective impulse response, rather than treating the forecasting model as a black box or oversimplifying its error structure.
This enables a modular design where a complex predictor's output characteristics (specifically, its error structure via f(t)) inform the structure of the decision algorithm (v), leading to controllers that are theoretically grounded to be optimal given the specific statistical properties of the forecasts they receive.

The core of the thesis... is deeply rooted in smoothed online convex optimization (SOCO) and classical model predictive control (MPC). While these are foundational, the cutting edge in handling uncertainty in sequential decision-making has shifted significantly since 2018.
The proposed colored noise model... is more general than i.i.d., but modeling real-world prediction errors solely as a linear filter on i.i.d. noise might still be too simplistic for complex systems...
The assumption of i.i.d. per-step noise e(s) underlying the colored noise model... is a critical simplification. Real-world noise processes... often exhibit heteroskedasticity... or non-Gaussian distributions, which are not directly captured or analyzed within this framework.
The specific theoretical results are also tied to assumptions (like strong convexity or t-valley-filling) that limit their direct generalizability today.

Watch