Kernel logistic regression (KLR) is a classical nonlinear classifier in statistical machine learning. Newton method with quadratic convergence rate can solve KLR problem more effectively than the gradient method. However, an obvious limitation of New
ton method for training large-scale problems is the $O(n^{3})$ time complexity and $O(n^{2})$ space complexity, where $n$ is the number of training instances. In this paper, we employ the multilevel circulant matrix (MCM) approximate kernel matrix to save in storage space and accelerate the solution of the KLR. Combined with the characteristics of MCM and our ingenious design, we propose an MCM approximate Newton iterative method. We first simplify the Newton direction according to the semi-positivity of the kernel matrix and then perform a two-step approximation of the Newton direction by using MCM. Our method reduces the time complexity of each iteration to $O(n log n)$ by using the multidimensional fast Fourier transform (mFFT). In addition, the space complexity can be reduced to $O(n)$ due to the built-in periodicity of MCM. Experimental results on some large-scale binary and multi-classification problems show that our method makes KLR scalable for large-scale problems, with less memory consumption, and converges to test accuracy without sacrifice in a shorter time.
Knowledge Distillation (KD) aims at transferring knowledge from a larger well-optimized teacher network to a smaller learnable student network.Existing KD methods have mainly considered two types of knowledge, namely the individual knowledge and the
relational knowledge. However, these two types of knowledge are usually modeled independently while the inherent correlations between them are largely ignored. It is critical for sufficient student network learning to integrate both individual knowledge and relational knowledge while reserving their inherent correlation. In this paper, we propose to distill the novel holistic knowledge based on an attributed graph constructed among instances. The holistic knowledge is represented as a unified graph-based embedding by aggregating individual knowledge from relational neighborhood samples with graph neural networks, the student network is learned by distilling the holistic knowledge in a contrastive manner. Extensive experiments and ablation studies are conducted on benchmark datasets, the results demonstrate the effectiveness of the proposed method. The code has been published in https://github.com/wyc-ruiker/HKD
The interplay among anisotropic magnetic terms, such as the bond-dependent Kitaev interactions and single-ion anisotropy, plays a key role in stabilizing the finite-temperature ferromagnetism in the two-dimensional compound $rm{CrSiTe_3}$. While the
Heisenberg interaction is predominant in this material, a recent work shows that it is rather sensitive to the compressive strain, leading to a variety of phases, possibly including a sought-after Kitaev quantum spin liquid [C. Xu, textit{et. al.}, Phys. Rev. Lett. textbf{124}, 087205 (2020)]. To further understand these states, we establish the quantum phase diagram of a related bond-directional spin-$3/2$ model by the density-matrix renormalization group method. As the Heisenberg coupling varies from ferromagnetic to antiferromagnetic, three magnetically ordered phases, i.e., a ferromagnetic phase, a $120^circ$ phase and an antiferromagnetic phase, appear consecutively. All the phases are separated by first-order phase transitions, as revealed by the kinks in the ground-state energy and the jumps in the magnetic order parameters. However, no positive evidence of the quantum spin liquid state is found and possible reasons are discussed briefly.
In federated learning (FL), devices contribute to the global training by uploading their local model updates via wireless channels. Due to limited computation and communication resources, device scheduling is crucial to the convergence rate of FL. In
this paper, we propose a joint device scheduling and resource allocation policy to maximize the model accuracy within a given total training time budget for latency constrained wireless FL. A lower bound on the reciprocal of the training performance loss, in terms of the number of training rounds and the number of scheduled devices per round, is derived. Based on the bound, the accuracy maximization problem is solved by decoupling it into two sub-problems. First, given the scheduled devices, the optimal bandwidth allocation suggests allocating more bandwidth to the devices with worse channel conditions or weaker computation capabilities. Then, a greedy device scheduling algorithm is introduced, which in each step selects the device consuming the least updating time obtained by the optimal bandwidth allocation, until the lower bound begins to increase, meaning that scheduling more devices will degrade the model accuracy. Experiments show that the proposed policy outperforms state-of-the-art scheduling policies under extensive settings of data distributions and cell radius.
In a vehicular edge computing (VEC) system, vehicles can share their surplus computation resources to provide cloud computing services. The highly dynamic environment of the vehicular network makes it challenging to guarantee the task offloading dela
y. To this end, we introduce task replication to the VEC system, where the replicas of a task are offloaded to multiple vehicles at the same time, and the task is completed upon the first response among replicas. First, the impact of the number of task replicas on the offloading delay is characterized, and the optimal number of task replicas is approximated in closed-form. Based on the analytical result, we design a learning-based task replication algorithm (LTRA) with combinatorial multi-armed bandit theory, which works in a distributed manner and can automatically adapt itself to the dynamics of the VEC system. A realistic traffic scenario is used to evaluate the delay performance of the proposed algorithm. Results show that, under our simulation settings, LTRA with an optimized number of task replicas can reduce the average offloading delay by over 30% compared to the benchmark without task replication, and at the same time can improve the task completion ratio from 97% to 99.6%.
As 5G and Internet-of-Things (IoT) are deeply integrated into vertical industries such as autonomous driving and industrial robotics, timely status update is crucial for remote monitoring and control. In this regard, Age of Information (AoI) has been
proposed to measure the freshness of status updates. However, it is just a metric changing linearly with time and irrelevant of context-awareness. We propose a context-based metric, named as Urgency of Information (UoI), to measure the nonlinear time-varying importance and the non-uniform context-dependence of the status information. This paper first establishes a theoretical framework for UoI characterization and then provides UoI-optimal status updating and user scheduling schemes in both single-terminal and multi-terminal cases. Specifically, an update-index-based scheme is proposed for a single-terminal system, where the terminal always updates and transmits when its update index is larger than a threshold. For the multi-terminal case, the UoI of the proposed scheduling scheme is proven to be upper-bounded and its decentralized implementation by Carrier Sensing Multiple Access with Collision Avoidance (CSMA/CA) is also provided. In the simulations, the proposed updating and scheduling schemes notably outperform the existing ones such as round robin and AoI-optimal schemes in terms of UoI, error-bound violation and control system stability.
Timely status updating is crucial for future applications that involve remote monitoring and control, such as autonomous driving and Industrial Internet of Things (IIoT). Age of Information (AoI) has been proposed to measure the freshness of status u
pdates. However, it is incapable of capturing critical systematic context information that indicates the time-varying importance of status information, and the dynamic evolution of status. In this paper, we propose a context-based metric, namely the Urgency of Information (UoI), to evaluate the timeliness of status updates. Compared to AoI, the new metric incorporates both time-varying context information and dynamic status evolution, which enables the analysis on context-based adaptive status update schemes, as well as more effective remote monitoring and control. The minimization of average UoI for a status update terminal with an updating frequency constraint is investigated, and an update-index-based adaptive scheme is proposed. Simulation results show that the proposed scheme achieves a near-optimal performance with a low computational complexity.
Beamforming structures with fixed beam codebooks provide economical solutions for millimeter wave (mmWave) communications due to the low hardware cost. However, the training overhead to search for the optimal beamforming configuration is proportional
to the codebook size. To improve the efficiency of beam tracking, we propose a beam tracking scheme based on the channel fingerprint database, which comprises mappings between statistical beamforming gains and user locations. The scheme tracks user movement by utilizing the trained beam configurations and estimating the gains of beam configurations that are not trained. Simulations show that the proposed scheme achieves significant beamforming performance gains over existing beam tracking schemes.
Owing to the increasing need for massive data analysis and model training at the network edge, as well as the rising concerns about the data privacy, a new distributed training framework called federated learning (FL) has emerged. In each iteration o
f FL (called round), the edge devices update local models based on their own data and contribute to the global training by uploading the model updates via wireless channels. Due to the limited spectrum resources, only a portion of the devices can be scheduled in each round. While most of the existing work on scheduling focuses on the convergence of FL w.r.t. rounds, the convergence performance under a total training time budget is not yet explored. In this paper, a joint bandwidth allocation and scheduling problem is formulated to capture the long-term convergence performance of FL, and is solved by being decoupled into two sub-problems. For the bandwidth allocation sub-problem, the derived optimal solution suggests to allocate more bandwidth to the devices with worse channel conditions or weaker computation capabilities. For the device scheduling sub-problem, by revealing the trade-off between the number of rounds required to attain a certain model accuracy and the latency per round, a greedy policy is inspired, that continuously selects the device that consumes the least time in model updating until achieving a good trade-off between the learning efficiency and latency per round. The experiments show that the proposed policy outperforms other state-of-the-art scheduling policies, with the best achievable model accuracy under training time budgets.
Deep Neural Networks (DNNs) have been widely applied in many autonomous systems such as autonomous driving. Recently, DNN testing has been intensively studied to automatically generate adversarial examples, which inject small-magnitude perturbations
into inputs to test DNNs under extreme situations. While existing testing techniques prove to be effective, they mostly focus on generating digital adversarial perturbations (particularly for autonomous driving), e.g., changing image pixels, which may never happen in physical world. There is a critical missing piece in the literature on autonomous driving testing: understanding and exploiting both digital and physical adversarial perturbation generation for impacting steering decisions. In this paper, we present DeepBillboard, a systematic physical-world testing approach targeting at a common and practical driving scenario: drive-by billboards. DeepBillboard is capable of generating a robust and resilient printable adversarial billboard, which works under dynamic changing driving conditions including viewing angle, distance, and lighting. The objective is to maximize the possibility, degree, and duration of the steering-angle errors of an autonomous vehicle driving by the generated adversarial billboard. We have extensively evaluated the efficacy and robustness of DeepBillboard through conducting both digital and physical-world experiments. Results show that DeepBillboard is effective for various steering models and scenes. Furthermore, DeepBillboard is sufficiently robust and resilient for generating physical-world adversarial billboard tests for real-world driving under various weather conditions. To the best of our knowledge, this is the first study demonstrating the possibility of generating realistic and continuous physical-world tests for practical autonomous driving systems.
