Efficient Multinomial Logistic Bandit via Frequent Directions

• URL: http://arxiv.org/abs/2606.11968v1
• Date: Wed, 10 Jun 2026 11:47:27 GMT
• Title: Efficient Multinomial Logistic Bandit via Frequent Directions
• Abstract summary: A representative UCB-type algorithm, OFUL-MLogB, achieves a regret bound of $tildemathcalO(KdsqrtT)$, but still requires $mathcalO(K3d3)$ time and $mathcalO(K2d2)$ space per round.<n>We propose EOFD-MLogB, which integrates frequent directions matrix sketching into OFUL-MLogB.
• Score: 36.600560776380874
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies efficient online algorithms for multinomial logistic bandits (MLogB), where the feedback distribution over $K+1$ outcomes follows a multinomial logistic model of $d$-dimensional action vectors. A representative UCB-type algorithm, OFUL-MLogB, achieves a regret bound of $\tilde{\mathcal{O}}(Kd\sqrt{T})$, but still requires $\mathcal{O}(K^3d^3)$ time and $\mathcal{O}(K^2d^2)$ space per round due to parameter estimation and optimistic reward construction, which is prohibitive in high-dimensional settings. To address this limitation, we propose EOFD-MLogB, which integrates frequent directions matrix sketching into OFUL-MLogB. By maintaining a low-rank SVD sketch of the accumulated Hessian, constrained online Newton updates in parameter estimation and $Kd \times K$ spectral-norm computations in the reward bonus are reduced to one-dimensional root-finding tasks and $K \times K$ eigenvalue computations, respectively. This yields dominant per-round time complexity $\mathcal{O}(Kd(m+K)^2)$ and space complexity $\mathcal{O}(Kd(m+K))$, where $m \ll d$ is the sketch size. We further prove a regret bound of $\tilde{\mathcal{O}}(Δ_T(Kd\lnΔ_T+m)\sqrt{T})$, where the sketching error factor $Δ_T$ is controlled by the $m$-truncated spectral tail of the Hessian. Thus, when the Hessian is approximately low-rank, the regret is close to that of OFUL-MLogB. Experiments validate the computational efficiency and competitive performance.

Related papers

• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Enjoying Non-linearity in Multinomial Logistic Bandits [56.28491566735463]
  We consider the multinomial logistic bandit problem, a variant of where a learner interacts with an environment by selecting actions to maximize expected rewards.<n>We extend recent work on understanding the impact of the non-linearity of the logistic model to the multinomial setting and propose an efficient algorithm.<n>Our method yields a problem-dependent regret bound of order $ smashwidetildemathcalO( R d sqrtKT/kappa_*) $, where $R$ is the norm of the vector of rewards and $K$
  arXiv  Detail & Related papers  (2025-07-07T08:18:25Z)
• Displacement-Sparse Neural Optimal Transport [6.968698312185846]
  Optimal transport (OT) aims to find a map $T$ that transports mass from one probability measure to another while minimizing a cost function.<n>Neural OT solvers have gained popularity in high dimensional biological applications such as drug perturbation.<n>We propose an intuitive and theoretically grounded approach to learning emphdisplacement-sparse maps within neural OT solvers.
  arXiv  Detail & Related papers  (2025-02-03T23:44:17Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Online Newton Method for Bandit Convex Optimisation [28.66596225688161]
  We introduce a computationally efficient algorithm for zeroth-order bandit convex optimisation. We prove that in the adversarial setting its regret is at most $d3.5 sqrtn mathrmpolylog(n, d)$ with high probability where $d$ is the time horizon. In the setting the bound improves to $M d2 sqrtn mathrmpolylog(n, d)$ where $M in [d-1/2, d-1 / 4]$ is
  arXiv  Detail & Related papers  (2024-06-10T17:44:11Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  We propose the first computationally efficient horizon-free algorithm for linear mixture MDPs. Our algorithm adapts a weighted least square estimator for the unknown transitional dynamic. This also improves upon the best-known algorithms in this setting when $sigma_k2$'s are known.
  arXiv  Detail & Related papers  (2022-05-23T17:59:18Z)
• Perturbation Analysis of Randomized SVD and its Applications to Statistics [8.731676546744353]
  RSVD is a class of computationally efficient algorithms for computing the truncated SVD of large data matrices.<n>In this paper we derive upper bounds for the $ell$ and $ell_2,infty$ distances between the exact left singular vectors $widehatmathbfU$ of $widehatmathbfM$.<n>We apply our theoretical results to settings where $widehatmathbfM$ is an additive perturbation of some unobserved signal matrix $mathbfM$.
  arXiv  Detail & Related papers  (2022-03-19T07:26:45Z)
• Nonparametric Learning of Two-Layer ReLU Residual Units [22.870658194212744]
  We describe an algorithm that learns two-layer residual units with rectified linear unit (ReLU) activation. We design layer-wise objectives as functionals whose analytic minimizers express the exact ground-truth network in terms of its parameters and nonlinearities. We prove the statistical strong consistency of our algorithm, and demonstrate the robustness and sample efficiency of our algorithm by experiments.
  arXiv  Detail & Related papers  (2020-08-17T22:11:26Z)
• Variational Orthogonal Features [29.636483122130027]
  We show that for certain priors, features can be defined that remove the $mathcalO(M3)$ cost of computing a minibatch estimate of an evidence lower bound (ELBO) We present a construction of features for any stationary prior kernel that allow for computation of an unbiased estimator to the ELBO using $T$ Monte Carlo samples in $mathcalO(tildeNT+M2T)$ and in $mathcalO(tildeNT+MT)$ with an additional approximation.
  arXiv  Detail & Related papers  (2020-06-23T17:18:07Z)
• Robust Interference Management for SISO Systems with Multiple Over-the-Air Computations [16.52374405363812]
  We consider the over-the-air computation of sums over a shared complex-valued MAC. Finding appropriate Tx-Rx scaling factors balance between a low error in the computation of $s_n$ and the interference induced by it.
  arXiv  Detail & Related papers  (2020-04-21T11:15:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.