### Abstract

We study the intrinsic limitations of sequential convex optimization through the lens of feedback information theory. In the oracle model of optimization, an algorithm queries an oracle for noisy information about the unknown objective function and the goal is to (approximately) minimize every function in a given class using as few queries as possible. We show that, in order for a function to be optimized, the algorithm must be able to accumulate enough information about the objective. This, in turn, puts limits on the speed of optimization under specific assumptions on the oracle and the type of feedback. Our techniques are akin to the ones used in statistical literature to obtain minimax lower bounds on the risks of estimation procedures; the notable difference is that, unlike in the case of i.i.d. data, a sequential optimization algorithm can gather observations in a controlled manner, so that the amount of information at each step is allowed to change in time. In particular, we show that optimization algorithms often obey the law of diminishing returns: the signal-to-noise ratio drops as the optimization algorithm approaches the optimum. To underscore the generality of the tools, we use our approach to derive fundamental lower bounds for a certain active learning problem. Overall, the present work connects the intuitive notions of information in optimization, experimental design, estimation, and active learning to the quantitative notion of Shannon information.

Original language | English (US) |
---|---|

Article number | 5766746 |

Pages (from-to) | 7036-7056 |

Number of pages | 21 |

Journal | IEEE Transactions on Information Theory |

Volume | 57 |

Issue number | 10 |

DOIs | |

State | Published - Oct 2011 |

### Keywords

- Convex optimization
- Fano's inequality
- feedback information theory
- hypothesis testing with controlled observations
- information-based
- information-theoretic converse
- minimax lower bounds
- sequential optimization algorithms
- statistical estimation complexity

### ASJC Scopus subject areas

- Information Systems
- Computer Science Applications
- Library and Information Sciences

## Fingerprint Dive into the research topics of 'Information-based complexity, feedback and dynamics in convex programming'. Together they form a unique fingerprint.

## Cite this

*IEEE Transactions on Information Theory*,

*57*(10), 7036-7056. [5766746]. https://doi.org/10.1109/TIT.2011.2154375