We investigate a Bayesian $k$-armed bandit problem in the \emph{many-armed} regime, where $k \geq \sqrt{T}$ and $T$ represents the time horizon. Initially, and aligned with recent literature on many-armed bandit problems, we observe that subsampling plays a key role in designing optimal algorithms; the conventional UCB algorithm is sub-optimal, whereas a subsampled UCB (SS-UCB), which selects $\Theta(\sqrt{T})$ arms for execution under the UCB framework, achieves rate-optimality. However, despite SS-UCB's theoretical promise of optimal regret, it empirically underperforms compared to a greedy algorithm that consistently chooses the empirically best arm. This observation extends to contextual settings through simulations with real-world data. Our findings suggest a new form of \emph{free exploration} beneficial to greedy algorithms in the many-armed context, fundamentally linked to a tail event concerning the prior distribution of arm rewards. This finding diverges from the notion of free exploration, which relates to covariate variation, as recently discussed in contextual bandit literature. Expanding upon these insights, we establish that the subsampled greedy approach not only achieves rate-optimality for Bernoulli bandits within the many-armed regime but also attains sublinear regret across broader distributions. Collectively, our research indicates that in the many-armed regime, practitioners might find greater value in adopting greedy algorithms.
相關內容
We study local filters for the Lipschitz property of real-valued functions $f: V \to [0,r]$, where the Lipschitz property is defined with respect to an arbitrary undirected graph $G=(V,E)$. We give nearly optimal local Lipschitz filters both with respect to $\ell_1$-distance and $\ell_0$-distance. Previous work only considered unbounded-range functions over $[n]^d$. Jha and Raskhodnikova (SICOMP `13) gave an algorithm for such functions with lookup complexity exponential in $d$, which Awasthi et al. (ACM Trans. Comput. Theory) showed was necessary in this setting. We demonstrate that important applications of local Lipschitz filters can be accomplished with filters for functions with bounded-range. For functions $f: [n]^d\to [0,r]$, we circumvent the lower bound and achieve running time $(d^r\log n)^{O(\log r)}$ for the $\ell_1$-respecting filter and $d^{O(r)}\text{polylog } n$ for the $\ell_0$-respecting filter. Our local filters provide a novel Lipschitz extension that can be implemented locally. Furthermore, we show that our algorithms have nearly optimal dependence on $r$ for the domain $\{0,1\}^d$. In addition, our lower bound resolves an open question of Awasthi et al., removing one of the conditions necessary for their lower bound for general range. We prove our lower bound via a reduction from distribution-free Lipschitz testing and a new technique for proving hardness for adaptive algorithms. We provide two applications of our local filters to arbitrary real-valued functions. In the first application, we use them in conjunction with the Laplace mechanism for differential privacy and noisy binary search to provide mechanisms for privately releasing outputs of black-box functions, even in the presence of malicious clients. In the second application, we use our local filters to obtain the first nontrivial tolerant tester for the Lipschitz property.
Folklore in complexity theory suspects that circuit lower bounds against $\mathbf{NC}^1$ or $\mathbf{P}/\operatorname{poly}$, currently out of reach, are a necessary step towards proving strong proof complexity lower bounds for systems like Frege or Extended Frege. Establishing such a connection formally, however, is already daunting, as it would imply the breakthrough separation $\mathbf{NEXP} \not\subseteq \mathbf{P}/\operatorname{poly}$, as recently observed by Pich and Santhanam (2023). We show such a connection conditionally for the Implicit Extended Frege proof system ($\mathsf{iEF}$) introduced by Kraj\'i\v{c}ek (The Journal of Symbolic Logic, 2004), capable of formalizing most of contemporary complexity theory. In particular, we show that if $\mathsf{iEF}$ proves efficiently the standard derandomization assumption that a concrete Boolean function is hard on average for subexponential-size circuits, then any superpolynomial lower bound on the length of $\mathsf{iEF}$ proofs implies $\#\mathbf{P} \not\subseteq \mathbf{FP}/\operatorname{poly}$ (which would in turn imply, for example, $\mathbf{PSPACE} \not\subseteq \mathbf{P}/\operatorname{poly}$). Our proof exploits the formalization inside $\mathsf{iEF}$ of the soundness of the sum-check protocol of Lund, Fortnow, Karloff, and Nisan (Journal of the ACM, 1992). This has consequences for the self-provability of circuit upper bounds in $\mathsf{iEF}$. Interestingly, further improving our result seems to require progress in constructing interactive proof systems with more efficient provers.
We build a finite volume scheme for the scalar conservation law $\partial_t u + \partial_x (H(x, u)) = 0$ with bounded initial condition for a wide class of flux function $H$, convex with respect to the second variable. The main idea for the construction of the scheme is to use the theory of discontinuous flux. We prove that the resulting approximating sequence converges boundedly almost everywhere on $\mathopen]0, +\infty\mathclose[$ to the entropy solution.
We present a flexible, deterministic numerical method for computing left-tail rare events of sums of non-negative, independent random variables. The method is based on iterative numerical integration of linear convolutions by means of Newtons-Cotes rules. The periodicity properties of convoluted densities combined with the Trapezoidal rule are exploited to produce a robust and efficient method, and the method is flexible in the sense that it can be applied to all kinds of non-negative continuous RVs. We present an error analysis and study the benefits of utilizing Newton-Cotes rules versus the fast Fourier transform (FFT) for numerical integration, showing that although there can be efficiency-benefits to using FFT, Newton-Cotes rules tend to preserve the relative error better, and indeed do so at an acceptable computational cost. Numerical studies on problems with both known and unknown rare-event probabilities showcase the method's performance and support our theoretical findings.
Assume that an $N$-bit sequence $S$ of $k$ numbers encoded as Elias gamma codes is given as input. We present space-efficient algorithms for sorting, dense ranking and competitive ranking on $S$ in the word RAM model with word size $\Omega(\log N)$ bits. Our algorithms run in $O(k + \frac{N}{\log N})$ time and use $O(N)$ bits. The sorting algorithm returns the given numbers in sorted order, stored within a bit-vector of $N$ bits, whereas our ranking algorithms construct data structures that allow us subsequently to return the dense/competitive rank of each number $x$ in $S$ in constant time. For numbers $x \in \mathbb{N}$ with $x > N$ we require the position $p_x$ of $x$ as the input for our dense-/competitive-rank data structure. As an application of our algorithms above we give an algorithm for tree isomorphism, which runs in $O(n)$ time and uses $O(n)$ bits on $n$-node trees. Finally, we generalize our result for tree isomorphism to forests and outerplanar graphs, while maintaining a space-usage of $O(n)$ bits. The previous best linear-time algorithms for trees, forests and outerplanar graph isomorphism all use $\Theta(n \log n)$ bits.
For a graph $G$, a subset $S\subseteq V(G)$ is called a resolving set of $G$ if, for any two vertices $u,v\in V(G)$, there exists a vertex $w\in S$ such that $d(w,u)\neq d(w,v)$. The Metric Dimension problem takes as input a graph $G$ on $n$ vertices and a positive integer $k$, and asks whether there exists a resolving set of size at most $k$. In another metric-based graph problem, Geodetic Set, the input is a graph $G$ and an integer $k$, and the objective is to determine whether there exists a subset $S\subseteq V(G)$ of size at most $k$ such that, for any vertex $u \in V(G)$, there are two vertices $s_1, s_2 \in S$ such that $u$ lies on a shortest path from $s_1$ to $s_2$. These two classical problems turn out to be intractable with respect to the natural parameter, i.e., the solution size, as well as most structural parameters, including the feedback vertex set number and pathwidth. Some of the very few existing tractable results state that they are both FPT with respect to the vertex cover number $vc$. More precisely, we observe that both problems admit an FPT algorithm running in time $2^{\mathcal{O}(vc^2)}\cdot n^{\mathcal{O}(1)}$, and a kernelization algorithm that outputs a kernel with $2^{\mathcal{O}(vc)}$ vertices. We prove that unless the Exponential Time Hypothesis fails, Metric Dimension and Geodetic Set, even on graphs of bounded diameter, neither admit an FPT algorithm running in time $2^{o(vc^2)}\cdot n^{\mathcal(1)}$, nor a kernelization algorithm that reduces the solution size and outputs a kernel with $2^{o(vc)}$ vertices. The versatility of our technique enables us to apply it to both these problems. We only know of one other problem in the literature that admits such a tight lower bound. Similarly, the list of known problems with exponential lower bounds on the number of vertices in kernelized instances is very short.
Event-based sensors, distinguished by their high temporal resolution of 1 $\mathrm{\mu}\text{s}$ and a dynamic range of 120 $\text{dB}$, stand out as ideal tools for deployment in fast-paced settings like vehicles and drones. Traditional object detection techniques that utilize Artificial Neural Networks (ANNs) face challenges due to the sparse and asynchronous nature of the events these sensors capture. In contrast, Spiking Neural Networks (SNNs) offer a promising alternative, providing a temporal representation that is inherently aligned with event-based data. This paper explores the unique membrane potential dynamics of SNNs and their ability to modulate sparse events. We introduce an innovative spike-triggered adaptive threshold mechanism designed for stable training. Building on these insights, we present a specialized spiking feature pyramid network (SpikeFPN) optimized for automotive event-based object detection. Comprehensive evaluations demonstrate that SpikeFPN surpasses both traditional SNNs and advanced ANNs enhanced with attention mechanisms. Evidently, SpikeFPN achieves a mean Average Precision (mAP) of 0.477 on the GEN1 Automotive Detection (GAD) benchmark dataset, marking significant increases over the selected SNN baselines. Moreover, the efficient design of SpikeFPN ensures robust performance while optimizing computational resources, attributed to its innate sparse computation capabilities.
Solving a linear system $Ax=b$ is a fundamental scientific computing primitive for which numerous solvers and preconditioners have been developed. These come with parameters whose optimal values depend on the system being solved and are often impossible or too expensive to identify; thus in practice sub-optimal heuristics are used. We consider the common setting in which many related linear systems need to be solved, e.g. during a single numerical simulation. In this scenario, can we sequentially choose parameters that attain a near-optimal overall number of iterations, without extra matrix computations? We answer in the affirmative for Successive Over-Relaxation (SOR), a standard solver whose parameter $\omega$ has a strong impact on its runtime. For this method, we prove that a bandit online learning algorithm--using only the number of iterations as feedback--can select parameters for a sequence of instances such that the overall cost approaches that of the best fixed $\omega$ as the sequence length increases. Furthermore, when given additional structural information, we show that a contextual bandit method asymptotically achieves the performance of the instance-optimal policy, which selects the best $\omega$ for each instance. Our work provides the first learning-theoretic treatment of high-precision linear system solvers and the first end-to-end guarantees for data-driven scientific computing, demonstrating theoretically the potential to speed up numerical methods using well-understood learning algorithms.
Recently, \citeauthor*{akbari2021locality}~(ICALP 2023) studied the locality of graph problems in distributed, sequential, dynamic, and online settings from a {unified} point of view. They designed a novel $O(\log n)$-locality deterministic algorithm for proper 3-coloring bipartite graphs in the $\mathsf{Online}$-$\mathsf{LOCAL}$ model. In this work, we establish the optimality of the algorithm by showing a \textit{tight} deterministic $\Omega(\log n)$ locality lower bound, which holds even on grids. To complement this result, we have the following additional results: \begin{enumerate} \item We show a higher and {tight} $\Omega(\sqrt{n})$ lower bound for 3-coloring toroidal and cylindrical grids. \item Considering the generalization of $3$-coloring bipartite graphs to $(k+1)$-coloring $k$-partite graphs, %where $k \geq 2$ is a constant, we show that the problem also has $O(\log n)$ locality when the input is a $k$-partite graph that admits a \emph{locally inferable unique coloring}. This special class of $k$-partite graphs covers several fundamental graph classes such as $k$-trees and triangular grids. Moreover, for this special class of graphs, we show a {tight} $\Omega(\log n)$ locality lower bound. \item For general $k$-partite graphs with $k \geq 3$, we prove that the problem of $(2k-2)$-coloring $k$-partite graphs exhibits a locality of $\Omega(n)$ in the $\onlineLOCAL$ model, matching the round complexity of the same problem in the $\LOCAL$ model recently shown by \citeauthor*{coiteux2023no}~(STOC 2024). Consequently, the problem of $(k+1)$-coloring $k$-partite graphs admits a locality lower bound of $\Omega(n)$ when $k\geq 3$, contrasting sharply with the $\Theta(\log n)$ locality for the case of $k=2$. \end{enumerate}
Posterior sampling, i.e., exponential mechanism to sample from the posterior distribution, provides $\varepsilon$-pure differential privacy (DP) guarantees and does not suffer from potentially unbounded privacy breach introduced by $(\varepsilon,\delta)$-approximate DP. In practice, however, one needs to apply approximate sampling methods such as Markov chain Monte Carlo (MCMC), thus re-introducing the unappealing $\delta$-approximation error into the privacy guarantees. To bridge this gap, we propose the Approximate SAample Perturbation (abbr. ASAP) algorithm which perturbs an MCMC sample with noise proportional to its Wasserstein-infinity ($W_\infty$) distance from a reference distribution that satisfies pure DP or pure Gaussian DP (i.e., $\delta=0$). We then leverage a Metropolis-Hastings algorithm to generate the sample and prove that the algorithm converges in $W_\infty$ distance. We show that by combining our new techniques with a localization step, we obtain the first nearly linear-time algorithm that achieves the optimal rates in the DP-ERM problem with strongly convex and smooth losses.
小貼士
登錄享
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191