PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Generalized Linear Bandits: Online Computation and Hashing

Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, Rebecca Willett

arXiv:1706.00136v3stat.MLcs.LG

TL;DR

Existing GLBs face scaling issues with both the time horizon and the number of arms. The paper proposes GLOC and hash-amenable algorithms, including QGLOC; its approximate inner-product method also reduces hash-key computation overhead. QGLOC improves the regret scaling over GLOC-TS, while the hash-amenable regret guarantees have an optimization-error caveat.

  • Problem

    Existing GLB algorithms have space and per-round time that grow with the time horizon, and time complexity linear in the number of arms.

    Source: §1 · p. 2

  • Method

    GLOC converts an online learner’s regret bound into a GLB algorithm, while GLOC-TS and QGLOC use hash-amenable arm selection and sampling-based approximate inner products reduce hash-key overhead.

    Source: §1 · pp. 2–3

  • Results

    QGLOC’s regret scales with d^5/4, improving on GLOC-TS’s d^3/2 scaling, and the proposed inner-product method has lower variance than prior methods for normally distributed vectors.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The framework applies to any online learner with low online regret, and QGLOC offers a hash-amenable option with improved dimension dependence over GLOC-TS.

    Source: §1 · pp. 2–3

    The regret bounds for QGLOC and GLOC-TS do not hold when hashing introduces error in solving the arm-selection criteria.

    Source: §4 · p. 8

Abstract

from arXiv · show

Generalized Linear Bandits (GLBs), a natural extension of the stochastic linear bandits, has been popular and successful in recent years. However, existing GLBs scale poorly with the number of rounds and the number of arms, limiting their utility in practice. This paper proposes new, scalable solutions to the GLB problem in two respects. First, unlike existing GLBs, whose per-time-step space and time complexity grow at least linearly with time $t$, we propose a new algorithm that performs online computations to enjoy a constant space and time complexity. At its heart is a novel Generalized Linear extension of the Online-to-confidence-set Conversion (GLOC method) that takes \emph{any} online learning algorithm and turns it into a GLB algorithm. As a special case, we apply GLOC to the online Newton step algorithm, which results in a low-regret GLB algorithm with much lower time and memory complexity than prior work. Second, for the case where the number $N$ of arms is very large, we propose new algorithms in which each next arm is selected via an inner product search. Such methods can be implemented via hashing algorithms (i.e., "hash-amenable") and result in a time complexity sublinear in $N$. While a Thompson sampling extension of GLOC is hash-amenable, its regret bound for $d$-dimensional arm sets scales with $d^{3/2}$, whereas GLOC's regret bound scales with $d$. Towards closing this gap, we propose a new hash-amenable algorithm whose regret bound scales with $d^{5/4}$. Finally, we propose a fast approximate hash-key computation (inner product) with a better accuracy than the state-of-the-art, which can be of independent interest. We conclude the paper with preliminary experimental results confirming the merits of our methods.

1 Introduction

Existing generalized linear bandit (GLB) algorithms scale poorly with the time horizon and number of arms. The paper introduces GLOC for online computation and hash-amenable methods, including QGLOC, to address these bottlenecks.

1 Introduction

  • Existing GLBs require storing past arms and rewards and solving batch maximum-likelihood problems, making their space and per-round time grow at least linearly with time.A prior time-scalable solution is limited to Bernoulli rewards with a logistic link; it does not provide a generic GLB solution.Source: §1 · p. 2
  • For GLBs with many arms, linear-time arm selection is impractical in applications such as recommendation and interactive retrieval.Hashing can support sublinear search when the arm-selection objective is expressible as a distance or inner product.Source: §1 · p. 2
  • GLOC converts any online learner with low online regret into a GLB algorithm with low GLB regret, using a confidence set and optimism for arm selection.Applying GLOC to online Newton step yields a practical algorithm with regret nearly matching existing, less efficient GLB algorithms.Source: §1 · p. 2
  • GLOC-TS is hash-amenable, but its regret scales as d^3/2, compared with d for GLOC; QGLOC improves the hash-amenable scaling to d^5/4.GLOC itself is not hash-amenable because its arm-selection criterion is nonlinear.Source: §1 · pp. 2–3
  • The proposed sampling-based approximate inner-product method reduces hash-key computation overhead and has lower variance than methods from for normally distributed vectors.It also has thinner estimation-error tails, implying better concentration.Source: §1 · p. 3

2 Preliminaries

The preliminaries establish the paper’s generalized linear model setting and assumptions for rewards and arms.

2 Preliminaries

  • A generalized linear model represents a reward through an exponential-family distribution whose natural parameter is x⊤θ∗.The inverse link µ gives the conditional mean, and canonical GLMs have a strictly convex negative log likelihood.Source: §2 · p. 3
  • The GLB setting assumes a bounded unknown parameter, bounded arm norms, and a known inverse link; performance is measured by expected cumulative regret.The arm set may be infinite, though the paper focuses on finite arm sets for hashing.Source: §2 · pp. 3–4
  • The paper also considers non-canonical GLMs when µ is Lipschitz, continuously differentiable, and has derivative bounded below by a positive constant.Under these conditions, the integral m is strongly convex; the probit model is given as an example.Source: §2 · p. 4

3 Generalized Linear Bandits with Online Computation

GLOC turns online learning regret guarantees into confidence sets for GLBs, allowing online rather than batch computation. With ONS-GLM, it yields a data-dependent regret bound while retaining the framework’s generality.

3 Generalized Linear Bandits with Online Computation

  • GLOC feeds each observed loss to an online learner and uses its parameter predictions and regret bound to construct a confidence set for θ∗.It selects arms optimistically from that set, replacing batch computations over the full history with an online learner as a co-routine.Source: §3 · p. 4
  • A tighter online-learning regret bound can reduce the confidence-set radius and tends to reduce bandit regret in practice.The paper derives a tight data-dependent online regret bound tailored to GLMs for this purpose.Source: §3 · p. 5
  • ONS-GLM uses the strong convexity of m rather than loss exp-concavity, and its regret bound grows logarithmically with time.The bound is data-dependent; combining it with GLOC gives a corresponding confidence set and regret bound.Source: §3 · pp. 5–6
  • GLOC’s confidence set does not use the next available prediction θt+1; a tighter set using it is specific to ONS-GLM and loses generality.The paper reports the same regret order as Zhang et al. [41] for Bernoulli GLMs, while noting that their time-scalable method is restricted to that setting.Source: §3 · p. 6

4 Hash-Amenable Generalized Linear Bandits

For very large arm sets, the section develops hash-compatible GLB methods that select arms through inner-product search. QGLOC improves the regret scaling of hash-amenable GLOC-TS, while approximate hashing can invalidate their stated regret bounds.

Thompson Sampling

  • GLOC-TS’s regret scales with d^(3/2), as expected from linear TS analysis [4], exceeding GLOC’s d scaling; the authors note this harms shown-item relevance in interactive retrieval or product recommendation.GLOC-TS’s time complexity scales with d, compared with d^2 for QGLOC, but its regret bound is worse by a d^(1/4) factor.Source: §4 · pp. 7–8

Quadratic GLOC

  • QGLOC makes arm selection hash-amenable by using a quadratic objective in x that can be written as an inner product.Its objective, plus c0β^3/4m_t−1, is a tight upper bound on GLOC’s objective.Source: §4 · p. 7
  • QGLOC’s regret bound is a d^1/4-factor improvement over GLOC-TS’s; GLOC-TS has a d^1/4-factor worse regret bound than QGLOC, with no absolute exponent specified in these passages.The regret guarantee does not break down when adjusting c0, which balances exploitation and exploration.Source: §4 · p. 8

Time and Space Complexity

  • The hashing construction gives sublinear-in-N search, with time and space dependencies on T of log log(T) and log(T), respectively.GLOC-TS’s search time scales with d, while QGLOC’s scales with d^2.Source: §4 · p. 8

Discussion

  • The stated regret bounds for QGLOC and GLOC-TS no longer hold when hashing introduces approximation error.A separate fixed-budget QGLOC result handles hashing error but has space complexity linear in T.Source: §4 · p. 8

5 Approximate Inner Product Computations with L1 Sampling

L1 sampling estimates inner products to reduce the projection cost of hashing. The paper reports improved concentration behavior and, for normally distributed vectors, lower variance than L2 sampling.

L1 sampling

  • L1 sampling constructs an unbiased estimate of q⊤a, and averaging m samples reduces inner-product computation time to O(mUk).This replaces the O(d′Uk) computation described for direct hash-key inner products.Source: §5 · p. 9

Comparison with L2 sampling

  • L1’s estimation-error failure probability decays exponentially in m, unlike L2’s polynomial decay.The paper also reports that L2 has thicker tails than L1 in a 1000-dimensional example with m = 5 and 20K samples.Source: §5 · p. 9
  • For Gaussian vectors with d = 200, average variance is 0.99 for L2 sampling and 0.63 for L1 sampling.The paper notes that L1 need not have lower variance in all settings.Source: §5 · p. 9

6 Experiments

Experiments compare GLB algorithms under logit and probit rewards and test hash-amenable variants. The reported results show similar performance under logit, higher OL2M regret under probit, and a moderate regret increase from hashing.

Hash-Amenable GLBs

  • Figure 1 reports equal estimator variances but thicker L2 tails, while after 100 dimensions L1 mostly induces smaller variance than L2.The latter comparison is based on 1000 trials.Source: Figure 1 · p. 9

GLB Algorithms

  • Under logit, all three methods performed similarly; under probit, OL2M had higher regret and variance than GLOC and UCB-GLM, with a significant UCB-GLM–OL2M regret difference at t=3000.The comparison appears in Figure 2(a–b).Source: Figure 2 · p. 10, §6 · p. 10
  • The GLB comparison used random unit-sphere arms (d=10) over 40 trials through T=3000, testing logit and probit rewards.The arm set was fixed across rounds.Source: §6 · p. 10

Hash-Amenable GLBs

  • Hashing increased regret for QGLOC and GLOC-TS only moderately when evaluating their objectives on 1% of 100,000 arms.Figure 2(c) summarizes the comparison at T=5000.Source: §6 · p. 10, Figure 2 · p. 10

7 Future Work

The conclusion identifies extending the reward models and narrowing the regret gap between hash-amenable algorithms as future directions.

7 Future Work

  • The authors propose extending GLM rewards to single index models so that the function µ need not be known in advance under mild assumptions.They also identify closing the regret-bound gap between QGLOC and GLOC without losing hash-amenability as an open direction.Source: §7 · p. 10
  • A possible first step toward hash-amenable GLB regret of O(d^?T) is to design hashing that approximately solves (7).The supplied passage states the target as O(d…T) but does not preserve the exponent.Source: §7 · p. 11

A Proof of Theorem 1

These supplementary proofs derive confidence sets and regret guarantees using online regret bounds, strong convexity, and concentration arguments. They also give a tighter ONS confidence set and details for GLOC-TS and QGLOC.

A Proof of Theorem 1

  • Theorem 1’s proof generalizes online-to-confidence-set conversion from squared loss to negative log likelihood, using strong convexity and martingale concentration.The strong-convexity argument turns the online regret bound into a quadratic constraint on θ∗.Source: A Proof of Theorem 1 · p. 14

A.1 Proof of Lemma 2

B Proof of Theorem 2

C Proof of Theorem 3

  • Theorem 3’s proof uses strong convexity and the ONS update analysis, treating bounded and sub-Gaussian noise cases.The bounded-noise case is identified separately from the sub-Gaussian-noise argument.Source: C Proof of Theorem 3 · pp. 17–18

D Proof of Corollaries 1 and 2

E A Tighter Confidence Set

  • Directly analyzing the online learner gives a tighter confidence set for ONS, and CONS+ depends on the current reward y_t.The generic confidence set can use any online learner with a known regret bound; the earlier CONS_t depends only on past rewards.Source: E A Tighter Confidence Set · p. 19

F Details on GLOC-TS

  • GLOC-TS samples a Gaussian perturbation to select an arm; its fixed-budget regret theorem can be made anytime by adjusting the failure rate..Source: F Details on GLOC-TS · pp. 20–21

G QGLOC without r

  • The alternative QGLOC definition of m requires another hash search, doubling time complexity, so the paper retains its main-text definition..Source: G QGLOC without r · p. 21

H Proof of Theorem 5

The proof bounds QGLOC’s instantaneous regret by combining a cap with three terms, then establishes the cumulative bound. The following discussion explains how c0 tunes exploration and exploitation without losing the regret guarantee.

H Proof of Theorem 5

  • The proof bounds instantaneous regret by min{2LS, L(A1+A2+A3)} and also splits this into three capped terms.For bounded noise, the regret bound’s log^2(T) factor can be replaced by log^(5/4)(T).Source: H Proof of Theorem 5 · pp. 23–24

I On c0 of QGLOC

  • The free parameter c0 balances exploitation and exploration, allowing the common practice of favoring exploitation without breaking QGLOC’s regret guarantee.The paper contrasts this with scaling exploration in existing algorithms, which it says lacks theoretical justification and forfeits their guarantee.Source: I On c0 of QGLOC · p. 24

J Details on Hashing

The section develops a hashing-compatible inner-product search for arm selection, where the useful search threshold is not known in advance. Multiple hashings and a binary search yield a high-probability cH-MIPS solution.

J Details on Hashing

  • Hashing retrieves candidates by matching query and arm hash keys, then comparing similarities within the retrieved bucket.The hash keys discretize inner products with shared projection vectors; multiple independent tables reduce the chance of missing similar points.Source: J Details on Hashing · pp. 24–25
  • Hashing guarantees require parameters c and M, but each query has its own useful M, which is not known ahead of time.The section addresses this by covering a range of M values with multiple hashings.Source: J Details on Hashing · p. 25
  • Binary search over the MIPS hashings returns a cH-MIPS solution with high probability.The construction uses a streamlined cH-MIPS hashing based on high-probability bounds for the maximum QGLOC objective.Source: J Details on Hashing · pp. 25–26
  • For d′-dimensional vectors, the stated time and space complexities are O(log(J)N^ρ*log(N)d′) and O(JN^ρ*(N + log(N)d′)), respectively.The hashing parameter ρ* is optimized and less than 1.Source: J Details on Hashing · pp. 26–27

K The Regret Bound of QGLOC under Hashing Approximation Error

The section bounds QGLOC regret when arm selection uses approximate MIPS hashing. Its fixed-budget guarantee matches the regret order of exact maximization, subject to successful hash queries; the proof also highlights unresolved issues for adaptive queries.

K The Regret Bound of QGLOC under Hashing Approximation Error

  • At a fixed horizon T, QGLOC with hashing can achieve the same order of regret as exact maximization, assuming successful cH-MIPS retrievals across all T queries.The stated guarantee holds with probability at least 1 − 3δ under the hashing-success condition.Source: K The Regret Bound of QGLOC under… · p. 27
  • The naive construction uses T independent hashings, yielding the first low-regret GLB algorithm with time sublinear in N, but requires space Ω(T).Each hashing is assigned to one iteration to control the probability of any failed retrieval.Source: K The Regret Bound of QGLOC under… · p. 27
  • Adaptive queries remain a theoretical challenge because earlier hash results can make later queries correlate with the projection vectors.The authors leave resolving this issue for infinitely many possible queries as future work.Source: K The Regret Bound of QGLOC under… · p. 27

K.1 Proof of Theorem 7

  • The proof allocates three δ-probability events to control confidence-set membership, gradient deviation, and the hashing guarantee.Together, these events account for the theorem’s 1 − 3δ probability statement.Source: §K.1 · p. 29

L Proof of Lemma 1

  • The Lemma 1 proof applies Hoeffding’s inequality after establishing that Gk is bounded.This supports a high-probability sampling error bound.Source: L Proof of Lemma 1 · p. 29

M Comparison between L1 and L2 sampling

The section compares L1 and L2 sampling for approximate inner products, finding different tradeoffs in concentration and variance. It also describes the multi-probe hashing configuration used in implementation.

M Comparison between L1 and L2 sampling

  • L2 sampling has better sample-complexity scaling with q, while L1 has better scaling with a and an exponential rather than polynomial concentration bound.The comparison does not establish that L1 or L2 is universally superior.Source: M Comparison between L1 and L2 sampling · p. 30
  • L1 sampling has an exponential concentration bound, while L2 sampling also has an exponential tail but can have arbitrarily poor scaling with q.The L2 scale can become very large when a q_i is small and the corresponding a_i is nonzero; the authors distinguish this from a heavy-tailed distribution.Source: M Comparison between L1 and L2 sampling · pp. 30–31
  • For normally distributed vectors and sufficiently large d, L1 sampling has smaller variance than L2 sampling in most cases.The authors note there is no absolute variance winner across all vectors.Source: M Comparison between L1 and L2 sampling · p. 31

N Hashing Implementation

  • The implementation uses multi-probe hashing to approximate a series of hashings by checking nearby buckets.It uses k = 12 keys and U = 24 tables.Source: N Hashing Implementation · p. 32

Related papers

Loading 1706.00136v3…