  We consider the problem of minimizing a strongly convex function that depends
on an uncertain parameter $\theta$. The uncertainty in the objective function
means that the optimum, $x^*(\theta)$, is also a function of $\theta$. We
propose an efficient method to compute $x^*(\theta)$ and its statistics. We use
a chaos expansion of $x^*(\theta)$ along a truncated basis and study
first-order methods that compute the optimal coefficients. We establish the
convergence rate of the method as the number of basis functions, and hence the
dimensionality of the optimization problem is increased. We give the first
non-asymptotic rates for the gradient descent and the accelerated gradient
descent methods. Our analysis exploits convexity and does not rely on a
diminishing step-size strategy. As a result, it is much faster than the
state-of-the-art both in theory and in our preliminary numerical experiments. A
surprising side-effect of our analysis is that the proposed method also acts as
a variance reduction technique to the problem of estimating $x^*(\theta)$.
