Appendix: Mathematical Background

In Sections A.1-A.3 of this appendix, we provide some basic definitions, notational conventions, and results from linear algebra and real analysis. We assume that the reader is familiar with these subjects, so no proofs are given. For additional related material, we refer to textbooks such as Hoffman and Kunze [HoK71], Lancaster and Tismenetsky [LaT85], and Strang [Str76] (linear algebra), and Ash [Ash72], Ortega and Rheinboldt [OrR70], and Rudin [Rud76] (real analysis). In Section A.4, we provide a few convergence theorems for deter-ministic and random sequences, which we will use for various convergence analyses of algorithms in the text. Except for the Supermartingale Convergence Theorem for sequences of random variables (Prop. A.4.5), we provide complete proofs. Set Notation If X is a set and x is an element of X, we write x ∈ X. A set can be specified in the form X = {x | x satisfies P }, as the set of all elements satisfying property P. The union of two sets X 1 and X 2 is denoted by X 1 ∪ X 2 , and their intersection by X 1 ∩ X 2. The symbols ∃ and ∀ have the meanings " there exists " and " for all, " respectively. The empty set is denoted by Ø. The set of real numbers (also referred to as scalars) is denoted by ℜ. The set ℜ augmented with +∞ and −∞ is called the set of extended real numbers. We write −∞ < x < ∞ for all real numbers x, and −∞ ≤ x ≤ ∞ for all extended real numbers x. We denote by [a, b] the set of (possibly extended) real numbers x satisfying a ≤ x ≤ b. A rounded, instead of square, bracket denotes strict inequality in the definition. Thus (a, b], [a, b), and (a, b) denote the set of all x satisfying a < x ≤ b, a ≤ x < b, and 443