The following generic framework describes, among other things, some problems in optimization and control: we wish to minimize an objective function in the presence of some uncertainty by posing queries to a black box and using the current collection of queries and black-box responses to either select the next query or stop and produce a candidate solution. For example, in convex optimization a query is a point in a compact convex domain and the response may be the values of an objective function and its derivatives at that point. In control, a query is a control signal applied to a plant with uncertain dynamics, and the response is the resulting state. Query responses may be (and often are) corrupted by noise. Information-based complexity, in the sense of Traub and others, is a study of the minimal number of queries needed to achieve the desired objective. In this talk, I will present an information-theoretic approach to bounding information-based complexity in convex optimization and adaptive control which is based on assessing the impact of noise and initial uncertainty upon the maximal rate at which any querying policy can approach the objective. Parts of this talk are based on joint work with Alexander Rakhlin (UPenn).