Search

This study addresses the dynamic spectrum access problem in a wireless sub-network that shares channels with a parent network. We approach the sequential channel allocation problem using a restless multi-armed bandits (RMAB) framework. Our objective is to maximize the expected discounted return over an infinite horizon while minimizing interference to the parent network caused by shared channels with the sub-network. Due to the unavailability of direct observations of the true channel state, we leverage the channel quality indicator (CQI) feedback provided by users. However, the RMAB problem is widely acknowledged as PSPACE-hard even for finite-state models. To overcome this challenge, we propose a closed-form channel index function using an iterative online approximation method to approximate the well-known Whittle index policy, which offers a low-complexity solution for ranking the available channels that has an infinite state space. Through extensive numerical simulation experiments, we demonstrate the superior performance and robustness of our proposed algorithm.

In this paper, we prove a conjecture of the second author by evaluating the determinant $$\det\left[x+\left(\frac{i-j}p\right)+\left(\frac ip\right)y+\left(\frac jp\right)z+\left(\frac{ij}p\right)w\right]_{0\le i,j\le(p-3)/2}$$ for any odd prime $p$, where $(\frac{\cdot}p)$ denotes the Legendre symbol. In particular, the determinant is equal to $x$ when $p\equiv 3\pmod4$., Comment: 16 pages. Make the main result more general

Regularization in modern machine learning is crucial, and it can take various forms in algorithmic design: training set, model family, error function, regularization terms, and optimizations. In particular, the learning rate, which can be interpreted as a temperature-like parameter within the statistical mechanics of learning, plays a crucial role in neural network training. Indeed, many widely adopted training strategies basically just define the decay of the learning rate over time. This process can be interpreted as decreasing a temperature, using either a global learning rate (for the entire model) or a learning rate that varies for each parameter. This paper proposes TempBalance, a straightforward yet effective layer-wise learning rate method. TempBalance is based on Heavy-Tailed Self-Regularization (HT-SR) Theory, an approach which characterizes the implicit self-regularization of different layers in trained models. We demonstrate the efficacy of using HT-SR-motivated metrics to guide the scheduling and balancing of temperature across all network layers during model training, resulting in improved performance during testing. We implement TempBalance on CIFAR10, CIFAR100, SVHN, and TinyImageNet datasets using ResNets, VGGs, and WideResNets with various depths and widths. Our results show that TempBalance significantly outperforms ordinary SGD and carefully-tuned spectral norm regularization. We also show that TempBalance outperforms a number of state-of-the-art optimizers and learning rate schedulers., Comment: NeurIPS 2023 Spotlight, first two authors contributed equally

In this paper, we consider a general observation model for restless multi-armed bandit problems. The operation of the player needs to be based on certain feedback mechanism that is error-prone due to resource constraints or environmental or intrinsic noises. By establishing a general probabilistic model for dynamics of feedback/observation, we formulate the problem as a restless bandit with a countable belief state space starting from an arbitrary initial belief (a priori information). We apply the achievable region method with partial conservation law (PCL) to the infinite-state problem and analyze its indexability and priority index (Whittle index). Finally, we propose an approximation process to transform the problem into which the AG algorithm of Ni\~no-Mora and Bertsimas for finite-state problems can be applied to. Numerical experiments show that our algorithm has an excellent performance.

We study two conjectural identities involving roots of unity and determinants of Hermitian matrices which have been recently proved by using the famous eigenvector-eigenvalue identity for normal matrices. In this note, we extend these identities to a general form by considering the class of circulant matrices suggested by Petrov. Furthermore, we give another proof to Sun's identities independent of the eigenvector-eigenvalue identity, where our strategy is built upon the similarity of an unnecessarily normal matrix to a particular one with integer eigenvalues, derived from the Fourier transform vectors suggested by Petrov.

We introduce the axiomatic definition of the point-derivative for noncommutative algebras and present the counterparts of the ordinary multi-variable chain rule and Clairaut's Theorem in the context of partial point-derivatives.

The liver has a unique blood supply system and plays an important role in the human blood circulatory system. Thus, hemodynamic problems related to the liver serve as an important part in clinical diagnosis and treatment. Although estimating parameters in these hemodynamic models is essential to the study of liver models, due to the limitations of medical measurement methods and constraints of ethics on clinical studies, it is impossible to directly measure the parameters of blood vessels in livers. Furthermore, as an important part of the systemic blood circulation, livers' studies are supposed to be in conjunction with other blood vessels. In this article, we present an innovative method to fix parameters of an individual liver in a human blood circulation using non-invasive clinical measurements. The method consists of a 1-D blood flow model of human arteries and veins, a 0-D model reflecting the peripheral resistance of capillaries and a lumped parameter circuit model for human livers. We apply the finite element method in fluid mechanics of these models to a numerical study, based on non-invasive blood related measures of 33 individuals. The estimated results of human blood vessel characteristic and liver model parameters are verified from the perspective of Stroke Value Variation, which shows the effectiveness of our estimation method.

We consider a class of restless bandit problems that finds a broad application area in reinforcement learning and stochastic optimization. We consider $N$ independent discrete-time Markov processes, each of which had two possible states: 1 and 0 (`good' and `bad'). Only if a process is both in state 1 and observed to be so does reward accrue. The aim is to maximize the expected discounted sum of returns over the infinite horizon subject to a constraint that only $M$ $(

This paper addresses an important class of restless multi-armed bandit (RMAB) problems that finds broad application in operations research, stochastic optimization, and reinforcement learning. There are $N$ independent Markov processes that may be operated, observed and offer rewards. Due to the resource constraint, we can only choose a subset of $M~(M

The purpose of this paper is to introduce the concept of the automatic integration and present a new way of approximating definite integrals using the automatic integration based on an associative algebra with zero divisors.

Based on a class of associative algebras with zero-divisors which are called real-like algebras by us, we introduce a way of defining automatic differentiation and present different ways of doing automatic differentiation to compute the first, the second and the third derivatives of a function exactly and simultaneously., Comment: 23 pages

We present type $\theta$ Stokes' theorem for type $\theta$ $k$-chains which extends the fundamental theorem of calculus in higher dimensions.

We present the basic theory of calculus on dual real numbers, and prove the counterpart of the ordinary fundamental theorem of calculus in the context of dual real numbers., Comment: 14

In this paper, we give new characterizations of algebraic regularity by using differential forms and difference quotients., Comment: 8 pages

Based on a new generalization of Cauchy-Riemann system presented in this paper, we introduce a class of quaternion-valued functions of a quaternionic variable, which are called algebraic regular functions. The set of algebraic regular functions is not only a real associative algebra, but also respect the composition of functions. Using algebraic regular functions as transition maps, we introduce a class of four-manifolds called the regular four-manifolds., Comment: 5 pages

We introduce the concept of a triangular representation of a Lie algebra, give a counterpart of Ado's theorem, and discuss $2$-irreducible triangular modules over a nonreductive Lie algebra.

Flow scheduling tends to be one of the oldest and most stubborn problems in networking. It becomes more crucial in the next generation network, due to fast changing link states and tremendous cost to explore the global structure. In such situation, distributed algorithms often dominate. In this paper, we design a distributed virtual game to solve the flow scheduling problem and then generalize it to situations of unknown environment, where online learning schemes are utilized. In the virtual game, we use incentives to stimulate selfish users to reach a Nash Equilibrium Point which is valid based on the analysis of the `Price of Anarchy'. In the unknown-environment generalization, our ultimate goal is the minimization of cost in the long run. In order to achieve balance between exploration of routing cost and exploitation based on limited information, we model this problem based on Multi-armed Bandit Scenario and combined newly proposed DSEE with the virtual game design. Armed with these powerful tools, we find a totally distributed algorithm to ensure the logarithmic growing of regret with time, which is optimum in classic Multi-armed Bandit Problem. Theoretical proof and simulation results both affirm this claim. To our knowledge, this is the first research to combine multi-armed bandit with distributed flow scheduling., Comment: 10 pages, 3 figures, conference

We introduce representations$^{6-th}$ of Lie algebras, and study the counterparts of the P-B-W Theorem and the Hopf algebra structure for the enveloping algebras of Lie algebras in the context of representations$^{6-th}$ of Lie algebras., Comment: arXiv admin note: text overlap with arXiv:1012.2844

We introduce a class of noncommutative spectra and give the sheaf structure on the class of noncommutative spectra., Comment: arXiv admin note: substantial text overlap with arXiv:1104.3956

We consider the adaptive shortest-path routing problem in wireless networks under unknown and stochastically varying link states. In this problem, we aim to optimize the quality of communication between a source and a destination through adaptive path selection. Due to the randomness and uncertainties in the network dynamics, the quality of each link varies over time according to a stochastic process with unknown distributions. After a path is selected for communication, the aggregated quality of all links on this path (e.g., total path delay) is observed. The quality of each individual link is not observable. We formulate this problem as a multi-armed bandit with dependent arms. We show that by exploiting arm dependencies, a regret polynomial with network size can be achieved while maintaining the optimal logarithmic order with time. This is in sharp contrast with the exponential regret order with network size offered by a direct application of the classic MAB policies that ignore arm dependencies. Furthermore, our results are obtained under a general model of link-quality distributions (including heavy-tailed distributions) and find applications in cognitive radio and ad hoc networks with unknown and dynamic communication environments., Comment: 10 pages, 1 figure

The multi-armed bandit (MAB) problem is a widely studied model in the field of operations research for sequential decision making and reinforcement learning. This paper mainly considers the classical MAB model with the heavy-tailed reward distributions. We introduce the extended robust UCB policy, which is an extension of the pioneering UCB policies proposed by Bubeck et al. [5] and Lattimore [21]. The previous UCB policies require the knowledge of an upper bound on specific moments of reward distributions or a particular moment to exist, which can be hard to acquire or guarantee in practical scenarios. Our extended robust UCB generalizes Lattimore's seminary work (for moments of orders $p=4$ and $q=2$) to arbitrarily chosen $p$ and $q$ as long as the two moments have a known controlled relationship, while still achieving the optimal regret growth order O(log T), thus providing a broadened application area of the UCB policies for the heavy-tailed reward distributions., Comment: 25 pages, 3 figures

We consider a large-scale cyber network with N components (e.g., paths, servers, subnets). Each component is either in a healthy state (0) or an abnormal state (1). Due to random intrusions, the state of each component transits from 0 to 1 over time according to certain stochastic process. At each time, a subset of K (K < N) components are checked and those observed in abnormal states are fixed. The objective is to design the optimal scheduling for intrusion detection such that the long-term network cost incurred by all abnormal components is minimized. We formulate the problem as a special class of Restless Multi-Armed Bandit (RMAB) process. A general RMAB suffers from the curse of dimensionality (PSPACE-hard) and numerical methods are often inapplicable. We show that, for this class of RMAB, Whittle index exists and can be obtained in closed form, leading to a low-complexity implementation of Whittle index policy with a strong performance. For homogeneous components, Whittle index policy is shown to have a simple structure that does not require any prior knowledge on the intrusion processes. Based on this structure, Whittle index policy is further shown to be optimal over a finite time horizon with an arbitrary length. Beyond intrusion detection, these results also find applications in queuing networks with finite-size buffers., Comment: 9 pages, 5 figures

In the Multi-Armed Bandit (MAB) problem, there is a given set of arms with unknown reward models. At each time, a player selects one arm to play, aiming to maximize the total expected reward over a horizon of length T. An approach based on a Deterministic Sequencing of Exploration and Exploitation (DSEE) is developed for constructing sequential arm selection policies. It is shown that for all light-tailed reward distributions, DSEE achieves the optimal logarithmic order of the regret, where regret is defined as the total expected reward loss against the ideal case with known reward models. For heavy-tailed reward distributions, DSEE achieves O(T^1/p) regret when the moments of the reward distributions exist up to the pth order for 12. With the knowledge of an upperbound on a finite moment of the heavy-tailed reward distributions, DSEE offers the optimal logarithmic regret order. The proposed DSEE approach complements existing work on MAB by providing corresponding results for general reward distributions. Furthermore, with a clearly defined tunable parameter-the cardinality of the exploration sequence, the DSEE approach is easily extendable to variations of MAB, including MAB with various objectives, decentralized MAB with multiple players and incomplete reward observations under collisions, MAB with unknown Markov dynamics, and combinatorial MAB with dependent arms that often arise in network optimization problems such as the shortest path, the minimum spanning, and the dominating set problems under unknown random weights., Comment: 22 pages, 2 figures