Linear Bandit Algorithms with Sublinear Time Complexity

• URL: http://arxiv.org/abs/2103.02729v1
• Date: Wed, 3 Mar 2021 22:42:15 GMT
• Title: Linear Bandit Algorithms with Sublinear Time Complexity
• Authors: Shuo Yang, Tongzheng Ren, Sanjay Shakkottai, Eric Price, Inderjit S. Dhillon, Sujay Sanghavi
• Abstract summary: We propose to accelerate existing linear bandit algorithms to achieve per-step time complexity sublinear in the number of arms $K$. We show that our proposed algorithms can achieve $O(K1-alpha(T))$ per-step complexity for some $alpha(T) > 0$ and $widetilde O(stT)$ regret, where $T$ is the time horizon.
• Score: 67.21046514005029
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose to accelerate existing linear bandit algorithms to achieve per-step time complexity sublinear in the number of arms $K$. The key to sublinear complexity is the realization that the arm selection in many linear bandit algorithms reduces to the maximum inner product search (MIPS) problem. Correspondingly, we propose an algorithm that approximately solves the MIPS problem for a sequence of adaptive queries yielding near-linear preprocessing time complexity and sublinear query time complexity. Using the proposed MIPS solver as a sub-routine, we present two bandit algorithms (one based on UCB, and the other based on TS) that achieve sublinear time complexity. We explicitly characterize the tradeoff between the per-step time complexity and regret, and show that our proposed algorithms can achieve $O(K^{1-\alpha(T)})$ per-step complexity for some $\alpha(T) > 0$ and $\widetilde O(\sqrt{T})$ regret, where $T$ is the time horizon. Further, we present the theoretical limit of the tradeoff, which provides a lower bound for the per-step time complexity. We also discuss other choices of approximate MIPS algorithms and other applications to linear bandit problems.

Related papers

• EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
  We present EKM: a novel algorithm for solving this problem exactly with worst-case $Oleft(NK+1right)$ complexity. EKM is developed according to recent advances in transformational programming and generation, using formal program steps. We show that the wall-clock run time of our algorithm matches the worst-case time complexity analysis on synthetic datasets.
  arXiv  Detail & Related papers  (2024-05-16T15:11:37Z)
• Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
  We provide efficient algorithms for the problem of learning large-margin halfspaces. Our results improve upon the algorithms provided by Impagliazzo, Lei, Pitassi, and Sorrell [STOC 2022]
  arXiv  Detail & Related papers  (2024-02-21T15:06:51Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint [16.02833173359407]
  This work introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular over a ground set of size $n$ subject to a knapsack constraint. $mathsfDLA$ is a deterministic algorithm that provides an approximation factor of $6+epsilon$ while $mathsfRLA$ is a randomized algorithm with an approximation factor of $4+epsilon$.
  arXiv  Detail & Related papers  (2023-05-17T15:27:33Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  This work considers a large family of bandit problems where the unknown underlying reward function is non-concave. Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality. We show that the standard optimistic algorithms are sub-optimal by dimension factors.
  arXiv  Detail & Related papers  (2021-07-09T16:04:24Z)
• Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time [16.26380955876814]
  We study the problem of maximizing a non-monotone, non-negative submodular function subject to a matroid constraint. We show that this deterministic ratio can be improved to $frac14$ under $mathcalO(nr)$ time complexity. We then present a more practical algorithm dubbed TwinGreedyFast which achieves $frac14-epsilon$ deterministic ratio in nearly-linear running time.
  arXiv  Detail & Related papers  (2020-10-22T03:52:08Z)
• Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time [16.346069386394703]
  We consider the problem of monotone, submodular over a ground set of size $n$ subject to cardinality constraint $k$. We introduce the first deterministic algorithms with linear time complexity; these algorithms are streaming algorithms. Our single-pass algorithm obtains a constant ratio in $lceil n / c rceil + c$ oracle queries, for any $c ge 1$.
  arXiv  Detail & Related papers  (2020-09-10T16:35:54Z)

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.