In classical optimization, the goal is to reach the global minimum of a static cost function. We initialize a model and iterate until the gradient vanishes or the parameters stop changing. However, in modern streaming applications—such as tracking a moving target, monitoring a shifting social network, or processing high-velocity text streams—the "optimal" solution is a moving target.
If we attempt to solve a full optimization problem to convergence for every new data point, the computational cost becomes prohibitive. The core insight of this research direction is that we don't have to. Instead, we can perform a single optimization step per observation. This "truncated" approach allows models to track time-varying optima in real-time with theoretical guarantees that often match their batch-processing counterparts.
The Intuition of Temporal Continuity
The reason a single step works is rooted in the continuity of time-varying systems. In most real-world scenarios, the state of a system at time $t$ is very close to its state at time $t-1$. Therefore, the optimal solution from the previous time step serves as an excellent "warm start" for the current one.
Shah et al. provided a foundational theoretical basis for this, demonstrating that performing just one iteration of alternating minimization per time step is sufficient to eventually reach the optimal steady-state solution. Because the environment changes incrementally, a single update step is often enough to move the estimate into a "neighborhood" of the new optimum. As Brouillon et al. argue, collapsing iterative loops into a single update per time step maintains convergence guarantees while drastically reducing latency in high-frequency control systems.
Implicit Regularization and Tracking
Beyond speed, single-step updates offer a hidden structural benefit: implicit temporal regularization. When we perform only one gradient or proximal step starting from the previous estimate, the new estimate is naturally biased to stay near the old one.
Mateos et al. highlight that this mechanism allows models to track evolving structures—like dynamic graphs—without the need for explicit, memory-heavy penalty terms. By performing a single proximal gradient update for each incoming signal, the algorithm ensures the estimated topology evolves smoothly. Buciulea et al. further demonstrate that this is sufficient even when parts of the system (hidden nodes) are unobservable, provided the structural changes are not excessively abrupt.
Efficiency Without Accuracy Loss
A common concern is that "truncating" the optimization might lead to poor accuracy or high regret. However, recent work shows that the trade-off is surprisingly favorable.
- Regret Bounds: Kasiviswanathan et al. showed that using an "inexact" update step (a single iteration of ADMM) maintains a sublinear regret bound, meaning the online model's performance remains competitive with batch solvers over time.
- Projection Costs: In constrained optimization, the "projection" step (mapping parameters back into a valid range) is often the bottleneck. Zhao et al. demonstrated that reducing these operations to a single projection per round can result in a 10x practical speedup without degrading the quality of regret bounds.
- Matrix Factorization: For Nonnegative Matrix Factorization (NMF), Zhao et al. found that a single-step projected gradient update achieved a six-fold reduction in processing time while maintaining theoretical convergence.
Applications Across Domains
This "one-pass" or "single-step" philosophy has been successfully applied to diverse problems where data velocity is high:
- Graph Learning: Saboksayr et al. and Mateos and Saboksayr use single-step proximal updates to track network topologies in brain activity and other dynamic systems.
- Target Tracking: Yuen-Man Pun proved that because the loss landscape in target localization is locally strongly convex, a simple online gradient descent update per measurement is more robust than complex second-order methods.
- Sparse Estimation: Zachariah and Stoica showed that a single iteration of cyclic coordinate descent per sample is sufficient to track high-dimensional sparse vectors, matching the efficiency of recursive least squares.
- Visual Tracking: Shu et al. utilize efficient optimization (conjugate gradient) for online model updates, allowing trackers to adapt to appearance changes at 50 frames per second.
By shifting the focus from solving a problem to tracking its solution, these methods enable sophisticated machine learning models to operate in the chaotic, high-speed environments of the real world.
Key Foundational Work
Adaptive Alternating Minimization Algorithms (2007) — contributed 1 concept elements to this direction.
Sequence Labelling SVMs Trained in One Pass (2008) — contributed 1 concept elements to this direction.