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

Abstract

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.