Slow Rates of Convergence in Optimization with Side Information

In this work, we study convergence properties for optimization problems with side information. In these problems, there is side information that is correlated with the uncertain elements of the stochastic optimization problem and that can be used to improve decision-making. Ideally, a method for an optimization problem with side information should quickly converge to an optimal policy. This is impossible to guarantee unless some regularity conditions are placed on the relationship between the side information and the uncertain parameter. In this work, we identify regularity conditions for which convergence rates can be arbitrarily slow. The results that we provide cannot be greatly strengthened, since there are methods in the existing literature that have associated convergence rates under only slightly stronger regularity conditions. This provides a starting point for researchers who want to provide convergence guarantees. Any attempt to provide such guarantees will necessarily require regularity conditions stronger than the ones that we present.