Online Optimization with Unknown Time-Varying Parameters from Noisy Gradient Measurements
For researchers in online optimization and control, this work addresses the challenge of optimizing under unknown parameter dynamics with noisy gradients, though it is incremental as it combines existing estimation techniques.
The paper tackles online optimization with unknown time-varying parameters in the cost function, using only noisy gradient measurements. It proposes a method combining Gauss-Markov and instrumental-variable estimators to reconstruct and forecast parameters, achieving bounded expected tracking error.
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. We illustrate the effectiveness of our algorithm on a series of numerical examples.