Online Optimization with Unknown Time-Varying Parameters Using Noisy Gradient Measurements

arXiv:2605.22251 · math.OC, cs.SY, eess.SY · Submitted 2026-05-21 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: Today's paper: "Online Optimization with Unknown Time-Varying Parameters Using Noisy Gradient Measurements".

Dev: We study online optimization problems in which the cost function depends on latent, time-varying parameters that are unmeasurable and governed by unknown dynamics.

Rosa: First, who's behind it and why it matters.

Title and authors: Rosa: Moving on to how they frame this work, the paper "Online Optimization with Unknown Time-Varying Parameters Using Noisy Gradient Measurements" tackles a scenario where your cost function parameters are changing over time in an unknown way, and you're only getting noisy gradient signals.

Dev: It essentially sets up the problem where the parameter evolution follows a linear stochastic dynamic, theta(t + one) = A theta(t) + w p(t), and the algorithm only has access to y(x(t), t), which includes the true gradient term plus some measurement noise.

Taro: So, the central difficulty isn't just solving a standard optimization problem; it's simultaneously estimating an unknown system evolution matrix A while optimizing against those evolving parameters and noisy data.

Rosa: That’s right, and their proposed solution involves using control theoretic tools to first reconstruct the latent parameters theta(t) via a Gauss-Markov estimator from the gradient observations, then identifying the dynamics A using an instrumental variable estimator based on past estimates.

Dev: The methodology relies heavily on these estimators—the Gauss-Markov for parameter estimation and the IV method for dynamics identification—to bridge the gap between noisy measurements and knowing what theta(t) is actually doing.

Taro: I'm wondering about the assumptions they make; they assume strong convexity of f in x, uniform bounds on its Hessian, and stability properties for matrix A. What happens if those assumptions don't hold in a highly volatile physical system?

Rosa: Those are necessary conditions to get the math to work cleanly, but the paper is trying to establish a framework where these tools *can* be applied under certain structural guarantees on the cost function and dynamics.

Dev: I worry about the practical implementation of those assumptions when dealing with hardware limitations; if my sensor noise w m is much larger than assumed, how robust is this entire identification scheme?

Taro: If we think about real-world misbehavior, like sudden external disturbances that aren't modeled by the linear dynamics A, does this framework still give us a useful estimate of the true state?

Rosa: The paper aims to provide a rigorous mathematical bound on the expected tracking error even under these conditions, which helps quantify how much uncertainty we have in our prediction.

Dev: That bound is important for setting performance expectations; it tells us exactly how many measurements N are required to achieve a specific level of prediction accuracy before we deploy this system.

Taro: So, the real value here is that it gives us a quantifiable metric for when the system transitions from just reacting to data to proactively planning based on inferred dynamics.

Rosa: Precisely; it moves us toward systems that can handle dynamic uncertainty by learning the underlying rules of change rather than just guessing based on immediate feedback.

The paper's summary: Dev: So, if we summarize what they found in "Online Optimization with Unknown Time-Varying Parameters Using Noisy Gradient Measurements," they are looking at online optimization where the cost function parameters theta(t) evolve under unknown linear stochastic dynamics.

Rosa: They focus on the fact that you only have finite noisy gradient measurements y(x(t), t), and they propose a solution that uses control theory to first reconstruct theta(t) with a Gauss-Markov estimator, then identifies the dynamics A using an instrumental variable estimator, and finally forecasts theta(t) for future minimizer computation.

Taro: That sequence—estimation of parameters, identification of dynamics, then forecasting—is a robust way to handle the unknown parameter evolution in real-time settings.

Dev: I find that the paper clearly lays out how each stage builds on the previous one; you use estimates from t < N to identify A, and then use that identified A to forecast future parameters needed for optimization when time is past N.

Rosa: It’s a structured approach because it decomposes the complex problem into manageable estimation and identification steps, which is what makes it applicable in online settings where you can't rewind or re-measure everything.

Taro: And the paper illustrates the effectiveness of this algorithm on a series of numerical examples, which shows that this framework actually works in practice under simulated conditions.

Dev: The numerical examples are useful for showing feasibility, but I still need to know how sensitive those results are to the initial conditions or the noise levels w m before I can trust them for a high-frequency system.

Rosa: The paper does provide bounds on the expected tracking error, which is a key part of their contribution because it puts a mathematical ceiling on how much error we can expect given N and h.

Taro: And that bound is what gives us the confidence to say, "we need this many data points before our system can reliably predict its future optimal behavior."

Dev: So, the summary boils down to a systematic method for learning unknown parameter dynamics from noisy gradient observations to predict the future minimizer x*(t) for time t N.

Rosa: And that's the main point—it’s a method for handling time-varying parameters in online optimization problems under uncertainty.

The paper's improvements: Taro: Speaking of improvements, the paper suggests using the Gauss-Markov estimator and then an instrumental variable estimator as sequential steps to move from parameter estimation to dynamic identification.

Dev: That sequence is interesting because it directly addresses the correlation between the true parameter and the regressor, which is what motivates using (t-k) as an instrument z(t).

Rosa: The instrumental variable setup is motivated by two things: first, that past estimates of theta(t-k) are correlated with the true regressor through the dynamic equation, and second, that the noise terms entering those past estimates are temporally independent of the noise driving them now.

Dev: So it's using temporal independence to create a useful instrument for isolating the parameter dynamics A from all that measurement noise structure.

Taro: That's a clever way to use the properties of independence to decouple the parameter dynamics from the measurement noise, which is key when we have finite data points.

Rosa: And finally, they show how this leads to bounding terms like E beta(t) squared and E (t) - theta(t) squared in terms of those dynamic properties as shown in equations (fifteen).

Dev: The final bound involves the term alpha k which scales with k, which is related to the input sequence, showing that more data helps reduce the error.

Taro: So, the improvement isn't just about having a better optimizer; it’s about having a principled way to learn how to adapt those dynamics when things go wrong.

Rosa: It provides that principle by providing a rigorous bound on the expected tracking error as we increase our measurement budget N, which is what makes this paper valuable for deployment considerations.

Conclusion: Dev: So, to wrap up the paper "Online Optimization with Unknown Time-Varying Parameters Using Noisy Gradient Measurements," it provides a systematic three-stage process involving parameter reconstruction, dynamic identification via instrumental variables, and future forecasting.

Rosa: Essentially, they show that by using these tools sequentially, we can bound the expected tracking error as a function of the number of measurements N and the prediction horizon h.

Taro: The implication is that this gives us a concrete way to quantify exactly how much data you need to collect before our system can reliably predict its future optimal solution under dynamic uncertainty.

Dev: For me, it’s about knowing the required loop rate—if we can nail down the necessary data collection period N, we can design a control loop that operates within those constraints without excessive latency.

Rosa: So, to summarize, this paper is a method for handling time-varying parameters in online optimization problems under uncertainty by using sequential estimation and identification tools.

Taro: I think the real impact here is providing that mathematical framework for when our autonomy encounters novel dynamic changes, allowing us to plan ahead instead of just reacting blindly.

Dev: It gives us a way to understand the performance limits imposed by the dynamics A and noise tr(Q), which helps us design systems that are robust against those known sources of error.

Rosa: That’s the whole picture for this paper, focusing on how structured estimation techniques can provide reliable prediction bounds for online optimization problems with unknown time-varying parameters.

University of California, Riverside

math.OC, cs.SY, eess.SY

Submitted: 2026-05-21

Updated: 2026-09-28

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 77/100

The gist: We study online optimization problems in which the cost function depends on latent, time-varying parameters that are unmeasurable and governed by unknown dynamics.

Key concepts

Gauss-Markov estimator: This is a control theoretic tool used to reconstruct the latent cost function parameters theta(t) from noisy gradient observations. It serves as the first step in estimating what the changing parameters are doing over time.
Instrumental variable estimator (IV method): This method is used to identify the system evolution matrix A, which describes how the parameters change. It uses past estimates of theta(t-k) as an instrument to isolate the parameter dynamics from measurement noise structure.
Tracking error bound: The paper provides a mathematical bound on the expected tracking error. This metric quantifies the uncertainty in predictions and tells engineers exactly how many measurements (N) are needed to achieve a specific level of prediction accuracy.

Terminology

System Identification — 7× in this paper · explained in 3 episodes
Stochastic Dynamics — 6× in this paper · explained in 2 episodes
IEEE Conference on Decision and Control — 2× in this paper
Latent Dynamics — 2× in this paper · explained in 2 episodes
Accuracy — 1× in this paper · explained in 1 episode
Generalization — 1× in this paper · explained in 13 episodes
Trace — 1× in this paper · explained in 2 episodes
alpha — 1× in this paper · explained in 1 episode

Summary

We study online optimization problems in which the cost function depends on latent, time-varying parameters that are unmeasurable and governed by unknown dynamics. Specifically, we consider a strongly convex cost function whose linear term evolves according to unknown linear stochastic dynamics, while the algorithm has access only to finite noisy gradient measurements. We propose a solution that uses control theoretic tools to reconstruct the latent parameters from gradient observations using a Gauss-Markov estimator, then identifies the parameter dynamics using an instrumental-variable estimator, and finally forecasts the parameters to compute the future minimizer. We provide a bound on the expected tracking error.

The problem formulation is:

min

x∈Rn

f(x, θ(t)) = g(x)Tθ(t), (1)

where f: R n × Θ → R is the cost function with unknown, unmeasurable, time-varying parameter θ(t) ∈ Θ ⊂ R p, and g: R n → R p is a known vector-valued function whose entries depend on x. The unknown parameter vector θ(t) evolves under unknown linear, stochastic dynamics:

θ(t + 1) = Aθ(t) + wp(t), (2)

with unknown A ∈ R p×p and Q ⪰ 0. At each time t, given x(t) ∈ R n, the algorithm queries a gradient oracle and obtains y(x(t), t) = ∇xf(x(t), θ(t)) + wm(t) = ∂g⊤/∂xC(x)θ + wm. (3)

with wm(t) ∼ N (0, R), R ≻ 0, mutually independent of wp(t).

We aim to design an algorithm that produces the predicted minimizer xˆ∗(t) for t ≥ N, and to bound the expected prediction tracking error E∥xˆ∗(t) − x∗(t)∥2 as a function of the number of available measurements N and the prediction horizon h:= t − (N − 1) ≥ 1.

We impose the following assumptions:

(A1) The cost function f(·, θ) is twice continuously differentiable and uniformly strongly convex in x, i.e., there exists a constant µ > 0 such that ∇2 x f(x, θ) ⪰ µIn, ∀x ∈ R n, ∀θ ∈ Θ.

(A2) The matrix A is Schur stable, ρ(A) < 1, invertible, and the pair (A, Q1/2) is controllable.

(A3) The selected sequence for t=0 to N-1 is contained in a bounded set X ⊂ R n, and there exists α > 0 such that 1/N PN-1t=0 C(x(t))⊤C(x(t)) ⪰ αIp for all sufficiently large N.

The proposed approach has three stages:

First, we use the Gauss-Markov theorem to estimate θ(t) from Y = y(0) · · · y(N − 1), where Y is the data collected from the oracle over the data collection period. The best linear unbiased estimator of y¯t = C¯tθ(t) + ¯wmt is ˜θ(t):= (C¯T t R¯−1C¯)−1C¯T t R¯−1 ybar, with covariance (C̄T t R̄−1C̄)−1. This leads to the decomposition of the estimation error:

˜θ(t) − θ(t) = K∗ t wbarmtz]η(t):noise + K∗ t b(t)z]β(t):bias.

Second, using the available estimates of θ(t) for t < N, we identify the dynamics A via instrumental variables. We adopt an instrumental variable (IV) estimator with instrument z(t):= ˜θ(t − k), motivated by: (i) θ(t − k) is correlated with θ(t) through (2), so ˜θ(t − k) is correlated with the true regressor; (ii) η(t − k) depends on block of noises preceding the noises entering η(t) and η(t+1), so by temporal independence of wm, it is independent of both; (iii) wp(t) is independent of the past, hence of ˜θ(t−k). Together, (i)–(iii) yield E[˜θ(t−k)ξ(t)] ≈ 0.

Improvements for AI systems

Here are the specific improvements to AI systems that can be made by applying the methodology from this paper, along with what those improved systems could achieve:

Enhanced Tracking of Time-Varying Optimal Control/Optimization Problems:
Robustness to Unknown and Unmeasurable Dynamics in Real-Time Systems:
Adaptive State Estimation for Parameter Tracking in Dynamic Environments:
Accurate Prediction of Future Optimal Solutions Under Uncertainty:

Detailed Specific Improvements and Capabilities:

The system can accurately track the minimizer of a time-varying quadratic objective function (e.g., trajectory tracking or control problems) even when the underlying parameters driving that objective evolve according to unknown linear dynamics (like those in robotics or aerospace systems).
The improved AI system will maintain high performance in real-time decision-making by continuously estimating the latent, unmeasurable parameters from noisy gradient measurements (like sensor readings) using a Gauss-Markov estimator.
The system can robustly identify the specific dynamics governing parameter evolution (the transition matrix, e.g., how a robot's target position changes over time) using an instrumental-variable estimator that accounts for measurement noise and regressor correlation biases.
The AI can predict the optimal solution far into the future (prediction horizon), allowing it to compute the best possible action or state trajectory even when no new measurements are available, significantly reducing tracking error compared to methods that rely solely on immediate gradient descent.
In complex scenarios like road congestion control, the system can accurately estimate and forecast time-varying congestion weights based on historical gradients, leading to better long-term predictive performance than models that assume static or slowly changing parameters.
The algorithm provides a mathematically rigorous upper bound on the tracking error, allowing engineers to quantify exactly how many measurements are needed (the training horizon) to achieve a desired level of prediction accuracy before deployment.