📊 statistics

Efficient Multinomial Logistic Bandit via Frequent Directions

This paper proposes EOFD-MLogB, an efficient online algorithm for multinomial logistic bandits that leverages frequent directions matrix sketching to significantly reduce per-round time and space complexity while maintaining a near-optimal regret bound when the Hessian is approximately low-rank.

Original authors: Linzhe He, Yu-Jie Zhang, Sifan Yang, Lijun Zhang

Published 2026-06-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Linzhe He, Yu-Jie Zhang, Sifan Yang, Lijun Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to perfect a new recipe for a dish with K+1 possible flavor outcomes (like "too salty," "perfect," "too sweet," etc.). Every time you serve a dish, you get feedback on which flavor the customer picked. Your goal is to learn the "secret ingredient ratios" (the unknown parameters) that lead to the best outcome as quickly as possible, while minimizing the number of bad dishes you serve along the way.

In the world of machine learning, this is called a Multinomial Logistic Bandit. It's a fancy way of saying: "Make a choice, get a categorical result, learn from it, and repeat."

The Problem: The "Heavy Backpack"

The paper starts by looking at the current best method for solving this problem, called OFUL-MLogB. Think of this method as a chef who keeps a giant, heavy backpack full of every single recipe attempt they've ever made.

How it works: To make the next decision, the chef looks at the entire history of the backpack to calculate the perfect next move.
The Catch: As the number of ingredients (dimensions) and the number of possible flavors (outcomes) grow, this backpack becomes impossibly heavy.
- Time: Calculating the next move takes so long that the chef is essentially frozen in place.
- Space: The backpack is so big it doesn't fit in the kitchen anymore.
- The Result: This method works great for small kitchens but fails miserably in high-dimensional settings (like modern recommendation systems with millions of features).

The Solution: The "Smart Sketchbook"

The authors propose a new method called EOFD-MLogB. Instead of carrying the entire heavy backpack, this chef carries a compact, smart sketchbook.

They use a technique called Frequent Directions (FD). Imagine you are drawing a complex landscape. Instead of drawing every single leaf on every tree (which takes forever), you draw a simplified "sketch" that captures the main shapes and shadows. If the landscape has a lot of repetitive patterns (which the paper argues is often true for these problems), the sketch is almost as good as the real thing but takes up 99% less space.

Here is how the new method changes the game:

The Low-Rank Sketch: Instead of storing the full history, the algorithm maintains a low-rank "skeleton" of the data. It keeps the most important directions (the main flavors) and discards the tiny, noisy details.
Simplifying the Math:
- Old Way: To pick the next action, the chef had to solve a massive, complex 3D puzzle involving thousands of variables.
- New Way: Because of the sketch, the chef only needs to solve a tiny, one-dimensional puzzle (like finding the root of a single equation) and a small $K \times K$ matrix problem.
The Result: The chef can now make decisions much faster and with much less memory, without losing much accuracy.

The Trade-off: "Good Enough" vs. "Perfect"

The paper acknowledges a small trade-off. Because the sketchbook is a simplification, there is a tiny bit of "sketching error."

The Guarantee: The authors prove mathematically that if the data has a certain structure (meaning the "landscape" isn't too chaotic and can be well-approximated by a sketch), the new method's performance (regret) is almost identical to the heavy backpack method.
The Speed: The computational cost drops from being "cubic" (growing very fast) to being "linear" (growing slowly) relative to the dimension size. In plain English: If you double the complexity of the problem, the old method takes 8 times longer, while the new method only takes about twice as long.

The Experiments: The Taste Test

The authors tested their new "sketchbook" chef against the old "backpack" chef on real data (like the MNIST dataset of handwritten digits) and synthetic data.

Speed: The new method was 35% to 80% faster per round.
Performance: The new method made almost as few mistakes as the old method. The "regret" (the number of bad choices made) was very similar, proving that the sketch didn't ruin the quality of the decisions.

Summary

The paper introduces EOFD-MLogB, a faster, lighter version of an existing algorithm for making sequential decisions with multiple outcomes. By replacing a massive, unwieldy data storage system with a clever, compressed "sketch," the new algorithm achieves near-identical accuracy but runs significantly faster and uses far less memory, making it practical for high-dimensional problems where the old method was too slow to be useful.

Technical Summary: Efficient Multinomial Logistic Bandit via Frequent Directions

Problem Statement

The paper addresses the challenge of Multinomial Logistic Bandits (MLogB), a sequential decision-making framework where an agent selects an action $x_t \in \mathbb{R}^d$ and observes a categorical feedback $y_t \in \{0, \dots, K\}$ . The probability distribution of outcomes follows a multinomial logistic model parameterized by an unknown matrix $W^* \in \mathbb{R}^{K \times d}$ . The objective is to minimize cumulative regret, defined as the difference between the expected reward of the optimal action and the action chosen by the agent.

While existing state-of-the-art algorithms like OFUL-MLogB [Zhang and Sugiyama, 2023] achieve near-optimal regret bounds of $\tilde{O}(Kd\sqrt{T})$ , they suffer from prohibitive computational costs in high-dimensional settings. Specifically, OFUL-MLogB relies on maintaining and manipulating a full $Kd \times Kd$ Hessian matrix for parameter estimation (via Online Newton Step) and optimistic reward construction. This results in:

Time Complexity: $O(|A_t|K^3d^2 + K^3d^3)$ per round.
Space Complexity: $O(K^2d^2)$ per round.

These costs render the algorithm impractical for high-dimensional action spaces ( $d$ ) or large outcome sets ( $K$ ).

Methodology: EOFD-MLogB

The authors propose EOFD-MLogB (Efficient Optimism via Frequent Directions), an algorithm that integrates Frequent Directions (FD) matrix sketching into the OFUL-MLogB framework to reduce computational complexity while preserving theoretical guarantees.

1. Spectral Maintenance via Adapted FD

Instead of storing the full Hessian $H_t$ , EOFD-MLogB maintains a low-rank spectral decomposition of a sketched Hessian $Z_t$ :
$Z_t = \lambda I_{Kd} + V_t \Lambda_t V_t^\top$
where $V_t \in \mathbb{R}^{Kd \times m}$ has orthonormal columns, $\Lambda_t \in \mathbb{R}^{m \times m}$ is diagonal, and $m \ll d$ is the sketch size.

Block FD Update: Since the Hessian update in MLogB is a rank- $K$ matrix ( $\nabla^2 \ell_t = \nabla \sigma(W_t x_t) \otimes x_t x_t^\top$ ), the algorithm performs a block FD update. It factorizes the rank- $K$ update into $B_t B_t^\top$ and appends $B_t$ to the current sketch $[V_t \Lambda_t^{1/2}, B_t]$ . An SVD is computed, and the top $m$ singular directions are retained, discarding the rest into a cumulative sketching error term $\rho_{1:t}$ .

2. Efficient Parameter Update

The parameter update in OFUL-MLogB involves a constrained quadratic program (QCQP) over an ellipsoid defined by the Hessian.

Reduction to Root-Finding: By utilizing the spectral form of the surrogate Hessian $\tilde{Z}_t$ , the high-dimensional projection problem is reduced to finding a root $\nu$ of a scalar monotonic function $f(\nu) = S^2$ . This allows the projection to be computed efficiently without full eigen-decomposition, leveraging the Woodbury identity for matrix inversion.

3. Efficient Optimistic Reward Construction

The optimistic bonus in MLogB involves computing high-dimensional spectral norms, specifically $\|H_t^{-1/2}(I_K \otimes x)\|_2$ .

Dimensionality Reduction: The authors prove (Lemma 1) that using the sketched matrix $Z_t$ , this $Kd \times Kd$ spectral norm computation reduces to computing the spectral norm of a $K \times K$ symmetric matrix $A(x)$ . This eliminates the dependency on $d$ in the spectral norm calculation, reducing the cost from $O(K^3d^2)$ to $O(K^3 + K^2m + Kdm)$ .

Key Contributions

Algorithmic Efficiency: EOFD-MLogB achieves a dominant per-round time complexity of $O(Kd(m+K)^2)$ and space complexity of $O(Kd(m+K))$. This represents a significant improvement over the cubic dependence on $d$ in previous methods, making the algorithm scalable to high-dimensional settings.
Theoretical Guarantees: The paper establishes a regret bound of $\tilde{O}(\Delta_T (Kd \ln \Delta_T + m)\sqrt{T})$ $\tilde{O} (Δ_{T} (K d ln Δ_{T} + m) T)$ , where $\Delta_T = 1 + \rho_{1:T}/\lambda$ $Δ_{T} = 1 + ρ_{1 : T} / λ$ is a sketching factor dependent on the cumulative sketching error $\rho_{1:T}$ $ρ_{1 : T}$ .
- The error term $\rho_{1:T}$ is bounded by the $m$ -truncated spectral tail of the cumulative Hessian.
- When the accumulated Hessian is approximately low-rank (i.e., the spectral tail decays rapidly), $\Delta_T \approx 1$ , and the regret bound approaches that of the original OFUL-MLogB.
General Applicability: The spectral reduction techniques (Lemma 1 and Lemma 2) are shown to be applicable to other second-order MLogB algorithms and generalized linear bandits that rely on Hessian-based updates, not just OFUL-MLogB.

Experimental Results

Experiments were conducted on the MNIST dataset (converted to a contextual bandit problem) and synthetic data with high dimensions ( $d=100, 400$ ).

Performance: EOFD-MLogB maintains competitive regret performance, achieving curves comparable to OFUL-MLogB across both multinomial and binary settings.
Efficiency: The proposed method demonstrates substantial speedups. On MNIST, it reduced per-round computation time by approximately 80% while incurring only a ~10% overhead in regret. On synthetic data, time reductions exceeded 35% (multinomial) and 80% (binary).

Significance and Claims

The paper claims that EOFD-MLogB successfully addresses the "prohibitive" full-Hessian costs of existing second-order MLogB algorithms. By leveraging the Frequent Directions sketching technique, the authors demonstrate that it is possible to:

Retain the theoretical benefits of second-order methods (curvature-aware updates and tight confidence sets).
Drastically reduce computational overhead in high-dimensional regimes.
Maintain regret guarantees that are nearly optimal, provided the underlying Hessian structure is approximately low-rank.

The work highlights that while standard sketching techniques (like those used in linear bandits) do not directly apply to the nonlinear MLogB setting due to the lack of closed-form reductions, spectral reductions tailored to the specific structure of the multinomial logistic model can overcome these bottlenecks. The authors note that future work could focus on adaptive selection of the sketch size $m$ and developing conditions to directly control the sketching factor $\Delta_T$ .