Search

Symmetric submodular maximization is an important class of combinatorial optimization problems, including MAX-CUT on graphs and hyper-graphs. The state-of-the-art algorithm for the problem over general constraints has an approximation ratio of $0.432$. The algorithm applies the canonical continuous greedy technique that involves a sampling process. It, therefore, suffers from high query complexity and is inherently randomized. In this paper, we present several efficient deterministic algorithms for maximizing a symmetric submodular function under various constraints. Specifically, for the cardinality constraint, we design a deterministic algorithm that attains a $0.432$ ratio and uses $O(kn)$ queries. Previously, the best deterministic algorithm attains a $0.385-\epsilon$ ratio and uses $O\left(kn (\frac{10}{9\epsilon})^{\frac{20}{9\epsilon}-1}\right)$ queries. For the matroid constraint, we design a deterministic algorithm that attains a $1/3-\epsilon$ ratio and uses $O(kn\log \epsilon^{-1})$ queries. Previously, the best deterministic algorithm can also attain $1/3-\epsilon$ ratio but it uses much larger $O(\epsilon^{-1}n^4)$ queries. For the packing constraints with a large width, we design a deterministic algorithm that attains a $0.432-\epsilon$ ratio and uses $O(n^2)$ queries. To the best of our knowledge, there is no deterministic algorithm for the constraint previously. The last algorithm can be adapted to attain a $0.432$ ratio for single knapsack constraint using $O(n^4)$ queries. Previously, the best deterministic algorithm attains a $0.316-\epsilon$ ratio and uses $\widetilde{O}(n^3)$ queries.

We focus on the problem of placing two facilities along a linear space to serve a group of agents. Each agent is committed to minimizing the distance between her location and the closest facility. A mechanism is an algorithm that maps the reported agent locations to the facility locations. We are interested in mechanisms without money that are deterministic, strategy-proof, and provide a bounded approximation ratio for social cost. It is a fundamental problem to characterize the family of strategy-proof mechanisms with a bounded approximation ratio. Fotakis and Tzamos already demonstrated that the deterministic strategy-proof mechanisms for the 2-facility game problem are mechanisms with a unique dictator and the leftmost-rightmost mechanism. In this paper, we first present a more refined characterization of the first family. We then reveal three new classes of strategy-proof mechanisms that show the intricacy of structure within this family. This helps us get a more complete picture of the characterization of the 2-facility game problem, and may also have value in understanding and solving more general facility allocation game problems. Besides, based on our refined characterization, we surprisingly find that prediction cannot effectively improve the performance of the mechanism in the two-facility game problem, while this methodology to overcome bad approximation ratio works in many other mechanism design problems. We show that if we require that the mechanism admits a bounded approximation ratio when the prediction is arbitrarily bad, then at the same time, the mechanism can never achieve sublinear approximation ratios even with perfect prediction.

We investigate the entanglement harvesting phenomenon for static detectors that locally interact with massless scalar fields in the cosmic string spacetime, which, though locally flat, features a conical structure defined by a deficit angle. Specifically, we analyze three detector alignments relative to the string: parallel and orthogonal alignments with detectors on the same side of the string, and an orthogonal alignment with detectors on opposite sides of the string. For the alignments on the same side of the string, we observe that the cosmic string's presence can either aid or hinder entanglement harvesting, affecting both the extent of entanglement harvested and the achievable range of interdetector separation. This effect depends on the distance between the detectors and the string and differs markedly from scenarios in a locally flat spacetime with a reflecting boundary, where the boundary invariably extends the harvesting-achievable range. Conversely, for the alignment with detectors on opposite sides of the string, we find that detectors consistently harvest more entanglement than those in a flat spacetime devoid of a cosmic string. This starkly contrasts the behavior observed with detectors on the same side. Interestingly, the presence of a cosmic string expands the harvesting-achievable range for detectors in orthogonal alignment only when near the string, whereas it invariably reduces the achievable range for detectors in parallel alignment., Comment: 32 pages, 12 figures

Projected Gradient Ascent (PGA) is the most commonly used optimization scheme in machine learning and operations research areas. Nevertheless, numerous studies and examples have shown that the PGA methods may fail to achieve the tight approximation ratio for continuous DR-submodular maximization problems. To address this challenge, we present a boosting technique in this paper, which can efficiently improve the approximation guarantee of the standard PGA to \emph{optimal} with only small modifications on the objective function. The fundamental idea of our boosting technique is to exploit non-oblivious search to derive a novel auxiliary function $F$, whose stationary points are excellent approximations to the global maximum of the original DR-submodular objective $f$. Specifically, when $f$ is monotone and $\gamma$-weakly DR-submodular, we propose an auxiliary function $F$ whose stationary points can provide a better $(1-e^{-\gamma})$-approximation than the $(\gamma^2/(1+\gamma^2))$-approximation guaranteed by the stationary points of $f$ itself. Similarly, for the non-monotone case, we devise another auxiliary function $F$ whose stationary points can achieve an optimal $\frac{1-\min_{\boldsymbol{x}\in\mathcal{C}}\|\boldsymbol{x}\|_{\infty}}{4}$-approximation guarantee where $\mathcal{C}$ is a convex constraint set. In contrast, the stationary points of the original non-monotone DR-submodular function can be arbitrarily bad~\citep{chen2023continuous}. Furthermore, we demonstrate the scalability of our boosting technique on four problems. In all of these four problems, our resulting variants of boosting PGA algorithm beat the previous standard PGA in several aspects such as approximation ratio and efficiency. Finally, we corroborate our theoretical findings with numerical experiments, which demonstrate the effectiveness of our boosting PGA methods., Comment: 74 pages, 6 figures and 9 tables. An extended version of Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function (ICML 2022)

Building robots that can automate labor-intensive tasks has long been the core motivation behind the advancements in computer vision and the robotics community. Recent interest in leveraging 3D algorithms, particularly neural fields, has led to advancements in robot perception and physical understanding in manipulation scenarios. However, the real world's complexity poses significant challenges. To tackle these challenges, we present Robo360, a dataset that features robotic manipulation with a dense view coverage, which enables high-quality 3D neural representation learning, and a diverse set of objects with various physical and optical properties and facilitates research in various object manipulation and physical world modeling tasks. We confirm the effectiveness of our dataset using existing dynamic NeRF and evaluate its potential in learning multi-view policies. We hope that Robo360 can open new research directions yet to be explored at the intersection of understanding the physical world in 3D and robot control.

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. Streaming algorithms for submodule maximization have gained attention in recent years, allowing for real-time processing of large data sets by looking at each piece of data only once. However, most of the state-of-the-art algorithms are subject to monotone cardinality constraint. There remain non-negligible gaps with respect to approximation ratios between cardinality and other constraints like $d$-knapsack in non-monotone submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the cardinality constraint, we provide a deterministic $1/6-\epsilon$ approximation algorithm with $O(\frac{k\log k}{\epsilon})$ memory and sublinear query time, while the previous best algorithm is randomized with a $0.1921$ approximation ratio. To the best of our knowledge, this is the first deterministic streaming algorithm for the cardinality constraint. For the $d$-knapsack constraint, we provide a deterministic $\frac{1}{4(d+1)}-\epsilon$ approximation algorithm with $O(\frac{b\log b}{\epsilon})$ memory and $O(\frac{\log b}{\epsilon})$ query time per element. To the best of our knowledge, there is currently no streaming algorithm for this constraint.

Familiarity with audiences plays a significant role in shaping individual performance and experience across various activities in everyday life. This study delves into the impact of familiarity with non-playable character (NPC) audiences on player performance and experience in virtual reality (VR) exergames. By manipulating of NPC appearance (face and body shape) and voice familiarity, we explored their effect on game performance, experience, and exertion. The findings reveal that familiar NPC audiences have a positive impact on performance, creating a more enjoyable gaming experience, and leading players to perceive less exertion. Moreover, individuals with higher levels of self-consciousness exhibit heightened sensitivity to the familiarity with NPC audiences. Our results shed light on the role of familiar NPC audiences in enhancing player experiences and provide insights for designing more engaging and personalized VR exergame environments., Comment: 10 pages, 5 figures, IEEE International Symposium on Mixed and Augmented Reality (ISMAR) 2023

We explore correlations harvesting by two static detectors locally interacting with vacuum massless scalar fields in the presence of an infinite perfectly reflecting boundary. We study the phenomena of mutual information harvesting and entanglement harvesting for two detector-boundary alignments, i.e., parallel-to-boundary and vertical-to-boundary alignments. Our results show that the presence of the boundary generally inhibits mutual information harvesting relative to that in flat spacetime without any boundaries. In contrast, the boundary may play a doubled-edged role in entanglement harvesting, i.e., inhibiting entanglement harvesting in the near zone of the boundary while assisting it in the far zone of the boundary. Moreover, there exists an optimal detector energy gap difference between two nonidentical detectors that makes such detectors advantageous in correlations harvesting as long as the interdetector separation is large enough. The value of the optimal detector energy gap difference depends on both the interdetector separation and the detector-to-boundary distance. A comparison of the correlations harvesting in two different alignments shows that although correlations harvesting share qualitatively the same properties, they also display quantitative differences in that the detectors in vertical-to-boundary alignment always harvest comparatively more mutual information than the parallel-to-boundary ones, while they harvest comparatively more entanglement only near the boundary., Comment: 32 pages, 14 figures

Group-level emotion recognition (GER) is an inseparable part of human behavior analysis, aiming to recognize an overall emotion in a multi-person scene. However, the existing methods are devoted to combing diverse emotion cues while ignoring the inherent uncertainties under unconstrained environments, such as congestion and occlusion occurring within a group. Additionally, since only group-level labels are available, inconsistent emotion predictions among individuals in one group can confuse the network. In this paper, we propose an uncertainty-aware learning (UAL) method to extract more robust representations for GER. By explicitly modeling the uncertainty of each individual, we utilize stochastic embedding drawn from a Gaussian distribution instead of deterministic point embedding. This representation captures the probabilities of different emotions and generates diverse predictions through this stochasticity during the inference stage. Furthermore, uncertainty-sensitive scores are adaptively assigned as the fusion weights of individuals' face within each group. Moreover, we develop an image enhancement module to enhance the model's robustness against severe noise. The overall three-branch model, encompassing face, object, and scene component, is guided by a proportional-weighted fusion strategy and integrates the proposed uncertainty-aware method to produce the final group-level output. Experimental results demonstrate the effectiveness and generalization ability of our method across three widely used databases., Comment: 11 pages,3 figures

The competitive auction was first proposed by Goldberg, Hartline, and Wright. In their paper, they introduce the competitive analysis framework of online algorithm designing into the traditional revenue-maximizing auction design problem. While the competitive analysis framework only cares about the worst-case bound, a growing body of work in the online algorithm community studies the learning-augmented framework. In this framework, designers are allowed to leverage imperfect machine-learned predictions of unknown information and pursue better theoretical guarantees when the prediction is accurate(consistency). Meanwhile, designers also need to maintain a nearly-optimal worst-case ratio(robustness). In this work, we revisit the competitive auctions in the learning-augmented setting. We leverage the imperfect predictions of the private value of the bidders and design the learning-augmented mechanisms for several competitive auctions with different constraints, including digital good auctions, limited-supply auctions, and general downward-closed permutation environments. For all these auction environments, our mechanisms enjoy $1$-consistency against the strongest benchmark $OPT$, which is impossible to achieve $O(1)$-competitive without predictions. At the same time, our mechanisms also maintain the $O(1)$-robustness against all benchmarks considered in the traditional competitive analysis. Considering the possible inaccuracy of the predictions, we provide a reduction that transforms our learning-augmented mechanisms into an error-tolerant version, which enables the learning-augmented mechanism to ensure satisfactory revenue in scenarios where the prediction error is moderate., Comment: Accepted by EC 2024. Improved the error-tolerant results

We investigate the online bandit learning of the monotone multi-linear DR-submodular functions, designing the algorithm $\mathtt{BanditMLSM}$ that attains $O(T^{2/3}\log T)$ of $(1-1/e)$-regret. Then we reduce submodular bandit with partition matroid constraint and bandit sequential monotone maximization to the online bandit learning of the monotone multi-linear DR-submodular functions, attaining $O(T^{2/3}\log T)$ of $(1-1/e)$-regret in both problems, which improve the existing results. To the best of our knowledge, we are the first to give a sublinear regret algorithm for the submodular bandit with partition matroid constraint. A special case of this problem is studied by Streeter et al.(2009). They prove a $O(T^{4/5})$ $(1-1/e)$-regret upper bound. For the bandit sequential submodular maximization, the existing work proves an $O(T^{2/3})$ regret with a suboptimal $1/2$ approximation ratio (Niazadeh et al. 2021)., Comment: Accepted by ICML 2023

Based on a result of Makeev, in 2012 Blagojevi\'c and Karasev proposed the following problem: given any positive integers $m$ and $1\leq \ell\leq k$, find the minimum dimension $d=\Delta(m;\ell/k)$ such that for any $m$ mass distributions on $\mathbb{R}^d$, there exist $k$ hyperplanes, any $\ell$ of which equipartition each mass. The $\ell=k$ case is a central question in geometric and topological combinatorics which remains open except for few values of $m$ and $k$. For $\ell< k$ and arbitrary $m$, we establish new upper bounds on $\Delta(m;\ell/k)$ when (1) $\ell=2$ and $k$ is arbitrary and (2) $\ell=3$ and $k=4$. When $\ell=k-1$ and $m+1$ is a power of two these bounds are nearly optimal and are exponentially smaller than the current best upper bounds when $\ell=k$. Similar remarks apply to our upper bounds when the hyperplanes are prescribed to be pairwise orthogonal. Lastly, we provide transversal extensions of our results along the lines recently established by Frick et al.: given $m$ families of compact convex sets in $\mathbb{R}^d$ such that no $2^\ell$ members of any family are pairwise disjoint, we show that every member of each family is pierced by the union of any $\ell$ of some collection of $k$ hyperplanes., Comment: 17 pages. Final version, corrects typos

Reparameterization aims to improve the generalization of deep neural networks by transforming convolutional layers into equivalent multi-branched structures during training. However, there exists a gap in understanding how reparameterization may change and benefit the learning process of neural networks. In this paper, we present a novel spatial gradient scaling method to redistribute learning focus among weights in convolutional networks. We prove that spatial gradient scaling achieves the same learning dynamics as a branched reparameterization yet without introducing structural changes into the network. We further propose an analytical approach that dynamically learns scalings for each convolutional layer based on the spatial characteristics of its input feature map gauged by mutual information. Experiments on CIFAR-10, CIFAR-100, and ImageNet show that without searching for reparameterized structures, our proposed scaling method outperforms the state-of-the-art reparameterization strategies at a lower computational cost., Comment: Published at ICLR 2023. Code available at https://github.com/Ascend-Research/Reparameterization

Understanding and modelling the performance of neural architectures is key to Neural Architecture Search (NAS). Performance predictors have seen widespread use in low-cost NAS and achieve high ranking correlations between predicted and ground truth performance in several NAS benchmarks. However, existing predictors are often designed based on network encodings specific to a predefined search space and are therefore not generalizable to other search spaces or new architecture families. In this paper, we propose a general-purpose neural predictor for NAS that can transfer across search spaces, by representing any given candidate Convolutional Neural Network (CNN) with a Computation Graph (CG) that consists of primitive operators. We further combine our CG network representation with Contrastive Learning (CL) and propose a graph representation learning procedure that leverages the structural information of unlabeled architectures from multiple families to train CG embeddings for our performance predictor. Experimental results on NAS-Bench-101, 201 and 301 demonstrate the efficacy of our scheme as we achieve strong positive Spearman Rank Correlation Coefficient (SRCC) on every search space, outperforming several Zero-Cost Proxies, including Synflow and Jacov, which are also generalizable predictors across search spaces. Moreover, when using our proposed general-purpose predictor in an evolutionary neural architecture search algorithm, we can find high-performance architectures on NAS-Bench-101 and find a MobileNetV3 architecture that attains 79.2% top-1 accuracy on ImageNet., Comment: Accepted to SDM2023; version includes supplementary material; 12 Pages, 3 Figures, 6 Tables

We study the Lamb shift of a two-level atom arising from its coupling to the conformal massless scalar field, which satisfies the Dirichlet boundary conditions, in the Hartle-Hawking vacuum in the BTZ spacetime, and find that the Lamb shift in the BTZ spacetime is structurally similar to that of a uniformly accelerated atom near a perfectly reflecting boundary in (2+1)-dimensional flat spacetime. Our results show that the Lamb shift is suppressed in the BTZ spacetime as compared to that in the flat spacetime as long as the transition wavelength of the atom is much larger than $AdS$ radius of the BTZ spacetime while it can be either suppressed or enhanced if the transition wavelength of the atom is much less than $AdS$ radius. In contrast, the Lamb shift is always suppressed very close to the horizon of the BTZ spacetime and remarkably it reduces to that in the flat spacetime as the horizon is approached although the local temperature blows up there., Comment: 21 pages,2 figures

Evaluating neural network performance is critical to deep neural network design but a costly procedure. Neural predictors provide an efficient solution by treating architectures as samples and learning to estimate their performance on a given task. However, existing predictors are task-dependent, predominantly estimating neural network performance on image classification benchmarks. They are also search-space dependent; each predictor is designed to make predictions for a specific architecture search space with predefined topologies and set of operations. In this paper, we propose a novel All-in-One Predictor (AIO-P), which aims to pretrain neural predictors on architecture examples from multiple, separate computer vision (CV) task domains and multiple architecture spaces, and then transfer to unseen downstream CV tasks or neural architectures. We describe our proposed techniques for general graph representation, efficient predictor pretraining and knowledge infusion techniques, as well as methods to transfer to downstream tasks/spaces. Extensive experimental results show that AIO-P can achieve Mean Absolute Error (MAE) and Spearman's Rank Correlation (SRCC) below 1% and above 0.5, respectively, on a breadth of target downstream CV tasks with or without fine-tuning, outperforming a number of baselines. Moreover, AIO-P can directly transfer to new architectures not seen during training, accurately rank them and serve as an effective performance estimator when paired with an algorithm designed to preserve performance while reducing FLOPs., Comment: AAAI 2023 Oral Presentation; version includes supplementary material; 16 Pages, 4 Figures, 22 Tables

Predicting neural architecture performance is a challenging task and is crucial to neural architecture design and search. Existing approaches either rely on neural performance predictors which are limited to modeling architectures in a predefined design space involving specific sets of operators and connection rules, and cannot generalize to unseen architectures, or resort to zero-cost proxies which are not always accurate. In this paper, we propose GENNAPE, a Generalized Neural Architecture Performance Estimator, which is pretrained on open neural architecture benchmarks, and aims to generalize to completely unseen architectures through combined innovations in network representation, contrastive pretraining, and fuzzy clustering-based predictor ensemble. Specifically, GENNAPE represents a given neural network as a Computation Graph (CG) of atomic operations which can model an arbitrary architecture. It first learns a graph encoder via Contrastive Learning to encourage network separation by topological features, and then trains multiple predictor heads, which are soft-aggregated according to the fuzzy membership of a neural network. Experiments show that GENNAPE pretrained on NAS-Bench-101 can achieve superior transferability to 5 different public neural network benchmarks, including NAS-Bench-201, NAS-Bench-301, MobileNet and ResNet families under no or minimum fine-tuning. We further introduce 3 challenging newly labelled neural network benchmarks: HiAML, Inception and Two-Path, which can concentrate in narrow accuracy ranges. Extensive experiments show that GENNAPE can correctly discern high-performance architectures in these families. Finally, when paired with a search algorithm, GENNAPE can find architectures that improve accuracy while reducing FLOPs on three families., Comment: AAAI 2023 Oral Presentation; includes supplementary materials with more details on introduced benchmarks; 14 Pages, 6 Figures, 10 Tables

We make a detailed comparison between entanglement harvesting for uniformly accelerated detectors in vacuum and static ones in a thermal bath at the Unruh temperature and find that, for a small energy gap relative to the Heisenberg energy of the detectors, static detectors in the thermal bath can harvest more entanglement and possess a comparatively larger harvesting-achievable range than the uniformly accelerated ones; however, as the energy gap grows sufficiently large, the uniformly accelerated detectors are instead likely to harvest more entanglement and possess a relatively larger harvesting-achievable range than inertial ones in the thermal bath. In comparison with static detectors in vacuum, there exist phenomena of acceleration-assisted entanglement harvesting but never that of thermal-noise-assisted one. A notably interesting feature is that, although both the amount of entanglement harvested and the harvesting-achievable interdetector separation for static detectors in a thermal bath are always a decreasing function of temperature, they are not always so for uniformly accelerated detectors as acceleration (Unruh temperature) varies, suggesting the existence of the anti-Unruh effect in the entanglement harvesting phenomena of the accelerated detectors., Comment: 18 pages, 5 figures

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic $0.283-o(1)$ approximation algorithm, while the previous best deterministic algorithm only achieves a $1/4$ approximation ratio. For the knapsack constraint, we provide a deterministic $1/4$ approximation algorithm, while the previous best deterministic algorithm only achieves a $1/6$ approximation ratio. For the linear packing constraints with large widths, we provide a deterministic $1/6-\epsilon$ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints., Comment: 25 pages; added a new result about the linear packing constraints

Testing hypothesis of independence between two random elements on a joint alphabet is a fundamental exercise in statistics. Pearson's chi-squared test is an effective test for such a situation when the contingency table is relatively small. General statistical tools are lacking when the contingency data tables are large or sparse. A test based on generalized mutual information is derived and proposed in this article. The new test has two desired theoretical properties. First, the test statistic is asymptotically normal under the hypothesis of independence; consequently it does not require the knowledge of the row and column sizes of the contingency table. Second, the test is consistent and therefore it would detect any form of dependence structure in the general alternative space given a sufficiently large sample. In addition, simulation studies show that the proposed test converges faster than Pearson's chi-squared test when the contingency table is large or sparse.

Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon $T$ suffer $\Omega(\sqrt{T})$ regret. In this paper, we study MAB and SLB with quantum reward oracles and propose quantum algorithms for both models with $O(\mbox{poly}(\log T))$ regrets, exponentially improving the dependence in terms of $T$. To the best of our knowledge, this is the first provable quantum speedup for regrets of bandit problems and in general exploitation in reinforcement learning. Compared to previous literature on quantum exploration algorithms for MAB and reinforcement learning, our quantum input model is simpler and only assumes quantum oracles for each individual arm., Comment: 14+6 pages

We study the adversarial bandit problem with composite anonymous delayed feedback. In this setting, losses of an action are split into $d$ components, spreading over consecutive rounds after the action is chosen. And in each round, the algorithm observes the aggregation of losses that come from the latest $d$ rounds. Previous works focus on oblivious adversarial setting, while we investigate the harder non-oblivious setting. We show non-oblivious setting incurs $\Omega(T)$ pseudo regret even when the loss sequence is bounded memory. However, we propose a wrapper algorithm which enjoys $o(T)$ policy regret on many adversarial bandit problems with the assumption that the loss sequence is bounded memory. Especially, for $K$-armed bandit and bandit convex optimization, we have $\mathcal{O}(T^{2/3})$ policy regret bound. We also prove a matching lower bound for $K$-armed bandit. Our lower bound works even when the loss sequence is oblivious but the delay is non-oblivious. It answers the open problem proposed in \cite{wang2021adaptive}, showing that non-oblivious delay is enough to incur $\tilde{\Omega}(T^{2/3})$ regret., Comment: IJCAI'2022

This article proposes a non-parametric tail classifier to aid tail classification among discrete thick-tail distributions. Theoretical results in this article show that certain distributional tail types can be identified among a sequence of plots based on the tail profile. Such distributional tails include power, sub-exponential, near-exponential, and exponential or thinner decaying tails. The proposed method does not hypothesize the distribution parameters values for classification. The method can be used practically as a preliminary tool to narrow down possible parametric models for refined statistical analysis with the unbiased estimators of the tail profile. Besides, simulation studies suggest that the proposed classification method performs well under various situations.

It has been shown that the vacuum state of a free quantum field is entangled and such vacuum entanglement can be harvested by a pair of initially uncorrelated detectors interacting locally with the vacuum field for a finite time. In this paper, we examine the entanglement harvesting phenomenon of two non-identical inertial detectors with different energy gaps locally interacting with massless scalar fields via a Gaussian switching function. We focus on how entanglement harvesting depends on the energy gap difference from two perspectives: the amount of entanglement harvested and the harvesting-achievable separation between the two detectors. In the sense of the amount of entanglement, we find that as long as the inter-detector separation is not too small with respect to the interaction duration parameter, two non-identical detectors could extract more entanglement from the vacuum state than the identical detectors. There exists an optimal value of the energy gap difference when the inter-detector separation is sufficiently large that renders the harvested entanglement to peak. Regarding the harvesting-achievable separation, we further find that the presence of an energy gap difference generally enlarges the harvesting-achievable separation range. Our results suggest that the non-identical detectors may be advantageous to extracting entanglement from vacuum in certain circumstances as compared to identical detectors., Comment: 16 pages,5 figures

We study the online scheduling problem where the machines need to be calibrated before processing any jobs. To calibrate a machine, it will take $\lambda$ time steps as the activation time, and then the machine will remain calibrated status for $T$ time steps. The job can only be processed by the machine that is in calibrated status. Given a set of jobs arriving online, each of the jobs is characterized by a release time, a processing time, and a deadline. We assume that there is an infinite number of machines for usage. The objective is to minimize the total number of calibrations while feasibly scheduling all jobs. For the case that all jobs have unit processing times, we propose an $\mathcal{O}(\lambda)$-competitive algorithm, which is asymptotically optimal. When $\lambda=0$, the problem is degraded to rent minimization, where our algorithm achieves a competitive ratio of $3e+7(\approx 15.16)$ which improves upon the previous results for such problems.

We explore whether acceleration assists entanglement harvesting for a pair of uniformly accelerated detectors in three different acceleration scenarios, i.e., parallel, anti-parallel and mutually perpendicular acceleration, both in the sense of the entanglement harvested and harvesting-achievable separation between the two detectors. Within the framework of entanglement harvesting protocols and the Unruh-DeWitt model of detectors locally interacting with massless scalar fields via a Gaussian switching function with an interaction duration parameter, we find that, in the sense of the entanglement harvested, acceleration is a mixed blessing insofar as it increases the harvested entanglement for a large detector energy gap relative to the interaction duration parameter, whilst inhibiting the entanglement harvested for a small energy gap. Regarding the harvesting-achievable separation range between the detectors, we further find that for very small acceleration and large energy gap, both relative to the duration parameter, acceleration-assisted enhancement can happen in all three acceleration scenarios. This is in sharp contrast to what was argued previously: that the harvesting-achievable range can be enhanced only for anti-parallel acceleration. However, for a not too small acceleration relative to the duration parameter and an energy gap larger than the acceleration, we find that only detectors in parallel acceleration possess a harvesting-achievable range larger than those at rest., Comment: 18 pages, 5 figures

Neural architecture search automates neural network design and has achieved state-of-the-art results in many deep learning applications. While recent literature has focused on designing networks to maximize accuracy, little work has been conducted to understand the compatibility of architecture design spaces to varying hardware. In this paper, we analyze the neural blocks used to build Once-for-All (MobileNetV3), ProxylessNAS and ResNet families, in order to understand their predictive power and inference latency on various devices, including Huawei Kirin 9000 NPU, RTX 2080 Ti, AMD Threadripper 2990WX, and Samsung Note10. We introduce a methodology to quantify the friendliness of neural blocks to hardware and the impact of their placement in a macro network on overall network performance via only end-to-end measurements. Based on extensive profiling results, we derive design insights and apply them to hardware-specific search space reduction. We show that searching in the reduced search space generates better accuracy-latency Pareto frontiers than searching in the original search spaces, customizing architecture search according to the hardware. Moreover, insights derived from measurements lead to notably higher ImageNet top-1 scores on all search spaces investigated., Comment: Accepted as an Applied Research Paper at CIKM 2021; 10 pages, 8 Figures, 2 Tables

We study the online influence maximization (OIM) problem in social networks, where the learner repeatedly chooses seed nodes to generate cascades, observes the cascade feedback, and gradually learns the best seeds that generate the largest cascade in multiple rounds. In the demand of the real world, we work with node-level feedback instead of the common edge-level feedback in the literature. The edge-level feedback reveals all edges that pass through information in a cascade, whereas the node-level feedback only reveals the activated nodes with timestamps. The node-level feedback is arguably more realistic since in practice it is relatively easy to observe who is influenced but very difficult to observe from which relationship (edge) the influence comes. Previously, there is a nearly optimal $\tilde{O}(\sqrt{T})$-regret algorithm for OIM problem under the linear threshold (LT) diffusion model with node-level feedback. It remains unknown whether the same algorithm exists for the independent cascade (IC) diffusion model. In this paper, we resolve this open problem by presenting an $\tilde{O}(\sqrt{T})$-regret algorithm for OIM problem under the IC model with node-level feedback., Comment: The published version of this paper claims there are OIM algorithms with node-level feedback that use standard offline oracles. However, we later found there are severe bugs in our initial algorithms. In this update, we retrieve most of our results by presenting an OIM algoithm that uses pair oracles