Scalable Analytics: Chapter 10

Comparison of Offline and Online Algorithms

• Classic Model (Offline Algorithms):

  • The algorithm is provided with the entire input dataset upfront.

  • The computation proceeds after seeing the complete data.

  • Examples include standard sorting or graph algorithms where the entire graph is available in memory.

• Online Algorithms:

  • Input arrives one piece at a time in a sequential manner.

  • Decisions must be made immediately as each piece arrives.

  • These decisions are irrevocable; once a choice is made, it cannot be changed even if future data makes it appear suboptimal.

  • This model is closely related to the data stream model of analytics where data is too large to store and must be processed on the fly.

Online Bipartite Matching

• Bipartite Graph Definitions:

  • A bipartite graph consists of two sets of nodes (e.g., Boys and Girls) where edges only exist between nodes of different sets.

  • Nodes: Represent entities (e.g., Boys in set $B$ and Girls in set $G$).

  • Edges: Represent preferences or possible connections between a boy and a girl.

  • Matching ($M$): A subset of edges such that no two edges share a common node.

  • Cardinality ($|M|$): The number of edges in the matching.

  • Perfect Matching: A matching where every node in the graph is connected to exactly one edge.

• Offline Global Optimization:

  • The goal is to find a maximum matching (the largest possible set of edges) for a given bipartite graph.

  • A polynomial-time offline algorithm exists based on augmenting paths, established by Hopcroft & Karp in 1973.

• Online Graph Matching Problem:

  • Initially, the algorithm is given the set of "boys."

  • In each subsequent round, the choices (edges) of one "girl" are revealed.

  • The algorithm must immediately decide to either pair the girl with an available eligible boy or not pair her at all.

  • Practical Application: Assigning tasks to servers in a data center where tasks arrive over time.

• The Greedy Algorithm for Online Matching:

  • Algorithm: When a new girl arrives, pair her with any eligible boy who is not yet matched.

  • If no eligible unmatched boys exist, the girl remains unpaired.

Performance Analysis of the Greedy Algorithm

• Competitive Ratio Definition:

  • For a specific input $I$, let $M_{\text{greedy}}$ be the matching produced by the greedy algorithm and $M_{\text{opt}}$ be the optimal matching.

  • The competitive ratio is the minimum across all possible inputs $I$ of the ratio: $\frac{|M_{\text{greedy}}|}{|M_{\text{opt}}|}$.

• Proving the Greedy Competitive Ratio ($1/2$):

  • Consider a case where $M_{\text{greedy}} \neq M_{\text{opt}}$.

  • Let $G$ be the set of girls matched in $M_{\text{opt}}$ but not in $M_{\text{greedy}}$.

  • Let $B$ be the set of boys adjacent to the girls in $G$ in the optimal matching.

  • Every boy in $B$ must already be matched in $M_{\text{greedy}}$. If any boy in $B$ were unmatched, the greedy algorithm would have matched them when the corresponding girl from $G$ arrived.

  • Consequently, the number of matched boys in the greedy solution must be at least the size of $B$, so $|M_{\text{greedy}}| \ge |B|$.

  • Since the optimal algorithm matched girls in $G$ exactly to boys in $B$, we know $|G| \le |B|$.

  • Thus, we have the inequality: $|G| \le |B| \le |M_{\text{greedy}}|$.

  • The total number of matches in the optimal set can be expressed as those matched by greedy plus those girls greedy missed: $|M_{\text{opt}}| \le |M_{\text{greedy}}| + |G|$.

  • Substituting the inequality $|G| \le |M_{\text{greedy}}|$ gives $|M_{\text{opt}}| \le 2|M_{\text{greedy}}|$.

  • Therefore, the competitive ratio is $\frac{|M_{\text{greedy}}|}{|M_{\text{opt}}|} \ge \frac{1}{2}$.

History and Models of Web Advertising

• Banner Ads (1995–2001):

  • Websites charged using the CPM (Cost Per Mille) rate, where "mille" is Latin for thousand.

  • Example: Paying $X for every 1,000 impressions.

  • Modeled after traditional media like TV and magazines.

  • Characterized by low click-through rates (CTR) and low Return on Investment (ROI).

• Performance-based Advertising (2000–Present):

  • Introduced by Overture (~2000) and adopted by Google (AdWords, ~2002).

  • Advertisers bid on search keywords.

  • The highest bidder's ad is shown, but the advertiser is only charged if the ad is clicked.

• The AdWords Problem:

  • A stream of queries ($q_1, q_2, \dots$) arrives.

  • Inputs: A set of bids per query, CTR for each advertiser-query pair, an advertiser budget (e.g., monthly), and a limit on ads shown per query.

  • Goal: Maximize search engine revenue by picking the best subset of ads for each query under budget and display constraints.

  • Innovative Metric: Instead of raw bids, search engines use "Expected Revenue per Click," calculated as $\text{Bid} \times \text{CTR}$.

• Complications in AdWords:

  • Budget: Advertisers have daily/monthly caps. Once reached, their ads cannot be shown.

  • CTR Uncertainty: The probability of a click is unknown initially. This presents an "Exploration vs. Exploitation" trade-off.

Online Ad Allocation Algorithms

• Greedy Approach:

  • Pick any advertiser who has bid on the query and has a remaining budget.

  • In a simplified setting (equal budgets, same click probability, 1 ad per query), the competitive ratio is $1/2$.

  • Worst-Case Scenario: Two advertisers $A$ and $B$, both with budget $4$. $A$ bids on $x$. $B$ bids on $x$ and $y$. If the query stream is $x, x, x, x, y, y, y, y$, and greedy assigns all $x$'s to $B$, then $B$ is out of money when $y$ arrives. Greedy gets $4$ matches while Optimal (assigning $x$ to $A$ and $y$ to $B$) gets $8$.

• BALANCE Algorithm (Mehta, Saberi, and Vazirani):

  • Logic: For each query, select the advertiser with the largest unspent budget among those who bid on the query.

  • Example Outcome: For the query stream $x, x, x, x, y, y, y, y$, BALANCE would alternate between $A$ and $B$ for content $x$, ensuring both have budget left for $y$.

  • For two advertisers, the competitive ratio is improved to $3/4$.

Multi-armed Bandits (MAB)

• Stateless Reinforcement Learning:

  • An agent interacts with an environment by taking actions ($a$) and receiving rewards ($r$).

  • Notation:

    • Set of arms: $\{A_k\}$.

    • Stochastic reward for arm $k$: $r_k$.

    • Mean reward of arm $k$: $E[r_k] = \mu_k$.

  • Application: Clinical trials, where arms represent different medical treatments.

• Cumulative Regret:

  • Let $\mu^* = \max_a \mu_a$ be the expected reward of the best arm.

  • For a sequence of arms pulled $i_1, i_2, \dots, i_T$, the Total Regret ($R_T$) is the difference between the optimal expected reward and the actual rewards obtained:         $R_T = T\mu^* - \sum_{t=1}^T E[\mu_{i_t}]$

  • Goal: Minimize regret or find a policy where $\frac{R_T}{T} \rightarrow 0$ as $T \rightarrow \infty$.

• Standard Bandit Algorithms:

  • Greedy: Estimates average reward and always picks the current best. It suffers from insufficient exploration and can converge to a suboptimal arm (e.g., if it gets an early reward of $0$ from a high-probability arm).

  • Epsilon-Greedy ($\epsilon$-greedy):

    • With probability $\epsilon_t$, pick an arm at random (exploration).

    • With probability $1-\epsilon_t$, pick the arm with the highest empirical reward (exploitation).

    • Optimal decay: $\epsilon_t = O(1/t)$.

    • Issue: Explicitly separates exploration and exploitation, leading to suboptimal choices during exploration phases.

Bayesian Bandits and Thompson Sampling

• Bayesian Philosophy:

  • Maintains a prior belief over the means $\pi(\cdot)$.

  • Updates the belief into a posterior distribution $\pi(\cdot | H_{t-1})$ based on the history of actions and rewards $H_{t-1} = \{a(i), r(i)\}_{i=1}^{t-1}$.

  • Tools: Jeffreys' prior is often used as a starting point.

• Thompson Sampling (TS) Algorithm (1933):

  • For each time step $t$:

    1. Sample a mean $\theta(t)$ from the current posterior distribution for each arm.

    2. Select the arm $a(t)$ with the highest sampled value.

    3. Pull the arm, observe reward $r(t)$, and update the posterior.

  1. TS is remarkably efficient at minimizing cumulative regret compared to frequentist methods like Upper Confidence Bound (UCB).

Specialized Bandit Contexts

• Use Cases:

  • Pinterest: Uses bandits to determine which new pins or ads to show when historical data ("signal") is lacking. Low-scoring pins are filtered out iteratively.

  • A/B Testing: Traditional testing splits traffic (50/50). Bandits optimize the randomization distribution as the experiment progresses (e.g., Bernoulli bandit), shifting traffic to the better variant sooner to reduce opportunity cost.

• Pure Exploration Problems:

  • Best-arm Identification: The goal is not to maximize reward during the process, but to identify the single best option using a fixed budget (e.g., identifying a prevention strategy in compute-intensive epidemiological models).

  • Successive Rejects Algorithm: Divides the budget into $K$ phases. At the end of each phase, the worst-performing arm is rejected.

  • Top-Two Thompson Sampling (TtTs): A variant designed for best-arm identification by resampling to ensure sufficient exploration of the runners-up.

• Epidemic Bandits:

  • Applied to the FluTE simulator (individual-based model of Seattle, ~560,000 individuals).

  • Evaluates 32 policies prioritizing vaccines by age groups (0-4, 5-18, 19-29, 30-64, >65).

  • Outcome distributions are bimodal (fade out vs. established epidemic) and Gaussian when established.

  • Boundary Focused TS (BFTS): An "anytime" exploration algorithm for identifying the top $m$ arms. It uses a posterior over bandit means to focus on the boundary between the top-performing and lower-performing arms.

Examination Content Requirements

• Proof and Derivation List (Partial):

  • Toivonen’s algorithm analysis.

  • Frequent Itemsets: Triangular matrix vs. dictionary memory analysis.

  • PageRank sparse matrix formulation derivation.

  • Reservoir sampling proof.

  • Filtering data streams: Throwing darts analysis.

  • Analysis of greedy bipartite matching ($M_{\text{greedy}}$ vs. $M_{\text{opt}}$).

• Essential Concepts to Explain (Examples):

  • PCY algorithm and memory consumption vs. "A priori."

  • BFR algorithm assumptions (axis-aligned Gaussian clusters) and CURE’s solutions.

  • SVD application for item recommendation.

  • Stochastic Gradient Descent vs. traditional Gradient Descent for big data.

  • Block-update algorithm complexity.

  • PLANET (MapReduce Decision Trees) and memory management.

  • SVM extensions for outliers.

  • Comparison between Thompson Sampling and Top-Two Thompson Sampling.