In this article, we investigate the joint task offload for Device-to-Device (D2D) communications with energy harvesting and power control requirements. Utilizing D2D communication for data offloading effectively decreases the load on cellular Base Stations (BSs). Thus, we investigate the challenge of optimizing connection density in D2D networks with multiple connections and investigate scenarios involving delays and energy harvesting, aiming for simultaneous transmissions and efficient resource utilization accordingly. The BS assigns each device a task, and the under-resourced devices aim to build a connection with one helper and offload part of the task. This scheduling policy includes optimal task assignment and practical helper choice. We formulate this problem as finding a semi-matching over a bipartite graph derived from multiple connections and distinct constraints, i.e., power budget and time constraint. Furthermore, we compared our proposed solution, Energy Harvesting Task Offloading Semi-Matching (EHTO-SM), with predefined baselines. Numerical results confirm that the proposed task allocation scheme provides users with high-quality services and demonstrates the effectiveness and dynamic resource adaptability in multiuser settings in various scenarios.

Platooning within autonomous vehicles has proven effective in addressing driver shortages and reducing fuel consumption. However, as platooning lengths increase, traditional C-V2X (cellular vehicle-to-everything) architectures are susceptible to end-to-end (E2E) latency increases. This is due to the necessity of relaying information through multiple hops from the leader vehicle to the last vehicle. To address this problem, this paper proposes a hybrid communication architecture and evaluates its end-to-end (E2E) delay through simulation in a multi-platoon scenario that integrates light fidelity (LiFi) and C-V2X. The proposed architecture introduces multiple-leader vehicles equipped with outdoor LiFi communication nodes in platoons to achieve high-speed and low-delay communication between leader vehicles, thereby reducing E2E delay.

Recently, Narrowband Internet of Things (NB-IoT) systems gained a significant focus as a promising direction for massive connectivity issues in forthcoming wireless communication systems. Thus, this paper investigates the challenge of maximizing connection density in NB-IoT networks, considering a downlink Non-Orthogonal Multiple Access (NOMA) scenario for simultaneous transmissions and efficient resource utilization. The base station assigns each device to one of the accessible Physical Resource Blocks (PRBs). This scheduling policy includes effective device clustering and optimal NOMA power assignment. We formulate this problem as finding semi-matching over a bipartite graph derived from multiple PRBs and distinct constraints, i.e., power budget, admitted PRB, interference, and quality of service constraints. Furthermore, we compared our solutions NOMA-Semi Matching 1 (NOMA-SM1) and NOMA-Semi Matching 2 (NOMA-SM2) with previous solutions. Numerical Simulations confirm that the proposed semi-matching aided approaches attain a better theoretical bound and superior performance.

As vehicular communication networks embrace metaverse beyond 5G/6G systems, the rich content update via the least interfered subchannel of the optimal frequency band in a hybrid band vehicle to everything (V2X) setting emerges as a challenging optimization problem. We model this problem as a tradeoff between multi-band VR/AR devices attempting to perform metaverse scenes and environmental updates to metaverse roadside units (MRSUs) while minimizing energy consumption. Due to the computational hardness of this optimization, we formulate an opportunistic band selection problem using a multi-armed bandit (MAB) that provides a good quality solution in real-time without computationally burdening the already stretched augmented/virtual reality (AR/VR) units acting as transmitting nodes. The opportunistic use of scheduling rich content updates at traffic signals and stand-still scenarios maps well with the formulated bandit problem. We propose a Dual-Objective Minimax Optimal Stochastic Strategy (DOMOSS) as a natural solution to this problem. Through extensive computer-based simulations, we demonstrate the effectiveness of our proposal in contrast to baselines and comparable solutions. We also verify the quality of our solution and the convergence of the proposed strategy.

Recently emerging WiGig systems experience limited coverage and signal strength fluctuations due to strict line-of-sight (LoS) connectivity requirements. In this paper, we address these shortcomings of WiGig communication by exploiting two emerging technologies in tandem, namely the reconfigurable intelligent surface (RIS) and unmanned aerial vehicles (UAVs). In ultra-dense traffic sites (referred to as hotspots) where WiGig nodes or User Devices (UDs) experience complex propagation and non-line-of-sight (non-LoS) environment, we envision the deployment of a UAV-mounted RIS system to complement the WiGig base station (WGBS) to deliver services to the UDs. However, commercially available UAVs have limited energy (i.e., constrained flight time). Therefore, the trajectory of our considered UAV needs to be locally estimated to enable it to serve multiple hotspots while minimizing its energy consumption within the WGBS coverage boundaries. Since this tradeoff problem is computationally expensive for the resource-constrained UAV, we argue that sequential learning can be a lightweight yet effective solution to locally solve the problem with a low impact on the available energy on the UAV. We formally formulate this problem as a contextual multi-armed bandit (CMAB) game. Then, we develop the linear randomized upper confidence bound (Lin-RUCB) algorithm to solve the problem effectively. We regard the UAV as the bandit learner, which attempts to maximize its attainable rate (i.e., the reward) by serving distinct hotspots in its trajectory that we treat as the arms of the considered bandit. The context is defined as the hotspots’ locations provided using GPS (global positioning system) service and the reward history of each hotspot. Our proposal accounts for the energy expenditure of the UAV in moving from one hotspot to another within its battery charge lifetime. We evaluate the performance of our proposal via extensive simulations that exhibit the superiority of our proposed Lin-RUCB algorithm over benchmarking methods.

In statistical learning, many problem formulations have been proposed so far, such as multi-class learning, complementarily labeled learning, multi-label learning, multi-task learning, which provide theoretical models for various real-world tasks. Although they have been extensively studied, the relationship among them has not been fully investigated. In this work, we focus on a particular problem formulation called Multiple-Instance Learning (MIL), and show that various learning problems including all the problems mentioned above with some of new problems can be reduced to MIL with theoretically guaranteed generalization bounds, where the reductions are established under a new reduction scheme we provide as a by-product. The results imply that the MIL-reduction gives a simplified and unified framework for designing and analyzing algorithms for various learning problems. Moreover, we show that the MIL-reduction framework can be kernelized.

Bytecode-level taint tracking discovers suspicious apps on the Android platform; however, malicious apps can bypass it by transferring information via system layers in the Android. A context tainting countermeasure has been devised, but since it employs a list of flow-causing API methods, it will miss flows when unlisted methods are exploited and can also produce false positives. This paper presents a new taint-tracking technique operating value logging and matching based on the flows’ characteristics to detect such flows without relying on lists of API methods. We implemented it into our taint-tracking system called VTDroid and confirmed its effectiveness with our test suite. We also evaluated it with popular apps collected from Google Play. The results show that the precision of VTDroid is 37 points higher than the context tainting.

We consider the expert advice problem with a low rank but noisy loss sequence, where a loss vector $l_{t} \in [-1,1]^N$ in each round $t$ is of the form $l_{t} = U v_{t} + \epsilon_{t}$ for some fixed but unknown $N \times d$ matrix $U$ called the kernel, some $d$-dimensional seed vector $v_{t} \in \mathbb{R}^{d}$, and some additional noisy term $\epsilon_t \in \mathbb{R}^{N}$ whose norm is bounded by $\epsilon$. This is a generalization of the works of Hazan et al. and Barman et al., where the former only treats noiseless loss and the latter assumes that the kernel is known in advance. In this paper, we propose an algorithm, where we re-construct the kernel under the assumptions, that the low rank loss is noised and there is no prior information about kernel. In this algorithm, we approximate the kernel by choosing a set of loss vectors with a high degree of independence from each other, and we give a regret bound of $O(d\sqrt{T}+d^{4/3}(N\epsilon)^{1/3}\sqrt{T})$. Moreover, even if in experiment, the proposed algorithm performs better than Hazan’s algorithm and Hedge algorithm.

We consider a variant of the online semi-definite programming problem: The decision space consists of positive semi-definite matrices with bounded diagonal entries and bounded $\Gamma$-trace norm, which is a generalization of the trace norm defined by a positive definite matrix $\Gamma$. To solve this problem, we propose a follow-the-regularized-leader algorithm with a novel regularizer, which is a generalisation of the log-determinant function parameterized by the matrix $\Gamma$. Then we apply our algorithm to online binary matrix completion (OBMC) with side information and online similarity prediction with side information, and improve mistake bounds by logarithmic factors. In particular, for OBMC our mistake bound is optimal.

We propose a new formulation of multiple-instance learning (MIL), in which a unit of data consists of a set of instances called a bag. The goal is to find a good classifier of bags based on the similarity with a "shapelet" (or pattern), where the similarity of a bag with a shapelet is the maximum similarity of instances in the bag. In previous work, some of the training instances have been chosen as shapelets with no theoretical justification. In our formulation, we use all possible, and thus infinitely many, shapelets, resulting in a richer class of classifiers. We show that the formulation is tractable, that is, it can be reduced through linear programming boosting (LPBoost) to difference of convex (DC) programs of finite (actually polynomial) size. Our theoretical result also gives justification to the heuristics of some previous work. The time complexity of the proposed algorithm highly depends on the size of the set of all instances in the training sample. To apply to the data containing a large number of instances, we also propose a heuristic option of the algorithm without the loss of the theoretical guarantee. Our empirical study demonstrates that our algorithm uniformly works for shapelet learning tasks on time-series classification and various MIL tasks with comparable accuracy to the existing methods. Moreover, we show that the proposed heuristics allow us to achieve the result in reasonable computational time.

We consider a job scheduling problem under precedence constraints, a classical problem for a single processor and multiple jobs to be done. The goal is, given processing time of n fixed jobs and precedence constraints over jobs, to find a permutation of n jobs that minimizes the total flow time, i.e., the sum of total wait time and processing times of all jobs, while satisfying the precedence constraints. The problem is an integer program and is NP-hard in general. We propose a decision diagram pi-MDD, for solving the scheduling problem exactly. Our diagram is suitable for solving linear optimization over permutations with precedence constraints. We show the effectiveness of our approach on the experiments on large scale artificial scheduling problems.

We consider a linear regression game in which the covariates are known in advance: at each round, the learner predicts a real-value, the adversary reveals a label, and the learner incurs a squared error loss. The aim is to minimize the regret with respect to linear predictions. For a variety of constraints on the adversary’s labels, we show that the minimax optimal strategy is linear, with a parameter choice that is reminiscent of ordinary least squares (and as easy to compute). The predictions depend on all covariates, past and future, with a particular weighting assigned to future covariates corresponding to the role that they play in the minimax regret. We study two families of label sequences: box constraints (under a covariate compatibility condition), and a weighted 2-norm constraint that emerges naturally from the analysis. The strategy is adaptive in the sense that it requires no knowledge of the constraint set. We obtain an explicit expression for the minimax regret for these games. For the case of uniform box constraints, we show that, with worst case covariate sequences, the regret is O(d\log T), with no dependence on the scaling of the covariates.

We consider an online density estimation problem for the Bradley-Terry model, where each model parameter defines the probability of a match result between any pair in a set of n teams. The problem is hard because the loss function (i.e., the negative log-likelihood function in our problem setting) is not convex. To avoid the non-convexity, we can change parameters so that the loss function becomes convex with respect to the new parameter. But then the radius K of the reparameterized domain may be infinite, where K depends on the outcome sequence. So we put a mild assumption that guarantees that K is finite. We can thus employ standard online convex optimization algorithms, namely OGD and ONS, over the reparameterized domain, and get regret bounds O(n^\frac12(\ln K)\sqrtT) and O(n^\frac32K\ln T), respectively, where T is the horizon of the game. The bounds roughly means that OGD is better when K is large while ONS is better when K is small. But how large can K be? We show that K can be as large as Θ(T^n-1), which implies that the worst case regret bounds of OGD and ONS are O(n^\frac32\sqrtT\ln T) and \tildeO(n^\frac32(T)^n-1), respectively. We then propose a version of Follow the Regularized Leader, whose regret bound is close to the minimum of those of OGD and ONS. In other words, our algorithm is competitive with both for a wide range of values of K. In particular, our algorithm achieves the worst case regret bound O(n^\frac52T^\frac13 \ln T), which is slightly better than OGD with respect to T. In addition, our algorithm works without the knowledge K, which is a practical advantage.

A complexity measure for threshold circuits, called the energy complexity, has been proposed to measure an amount of energy consumed during computation in the brain. Biological neurons need more energy to transmit a "spike" than not to transmit one, and hence the energy complexity of a threshold circuit is defined as the number of gates in the circuit that output "1" during computation. Since the firing activity of neurons in the brain is quite sparse, the following question arises: what Boolean functions can or cannot be computed by threshold circuits with small energy complexity. In the paper, we partially answer the question, that is, we show that there exists a tradeoff among three complexity measures of threshold circuits: the energy complexity, size, and depth. The tradeoff implies an exponential lower bound on the size of constant-depth threshold circuits with small energy complexity for a large class of Boolean functions.

Algorithms for learning feasibly Boolean functions from examples are explored.A class of as a hyp ot, hesis class, it, remains open whether it is properly learnable under distribution free setting. 1

In the framework of PAC-learning model, relationships between learning processes and information compressing processes are investigated.Information compressing processes are formulated as weak Occam algorithms.A weak Occarn algorithm is a deterministic polynomial time aJgorit hm that, when given m examples of unknown function, outputs, with high probability, a representation of a function that is consistent with the examples and belongs to a function class with complexity o(m).It has been shown that a weak Occam algorithm is also a consistent PAC-learning algorithm.In this extended abstract, it is shown that the converse does not hold by giving a PAClearning algorithm that is not a weak Occarn algorithm.and also some natural properties, caUed cowervativene.w and monotonicity, for learning algorithms that might help the converse hold are given.In particular, the conditions that make a conservative PAC-learning algorithm a weak Occam algorithm are given, and it is shown that, under some natural conditions, a monotone PAC-learning algorithm for a hypothesis class can be transformed to a weak Occam algorithm without changing the hypothesis class.