Search

How much credit (or blame) should an action taken in a state get for a future reward? This is the fundamental temporal credit assignment problem in Reinforcement Learning (RL). One of the earliest and still most widely used heuristics is to assign this credit based on a scalar coefficient, $\lambda$ (treated as a hyperparameter), raised to the power of the time interval between the state-action and the reward. In this empirical paper, we explore heuristics based on more general pairwise weightings that are functions of the state in which the action was taken, the state at the time of the reward, as well as the time interval between the two. Of course it isn't clear what these pairwise weight functions should be, and because they are too complex to be treated as hyperparameters we develop a metagradient procedure for learning these weight functions during the usual RL training of a policy. Our empirical work shows that it is often possible to learn these pairwise weight functions during learning of the policy to achieve better performance than competing approaches., Comment: AAAI 2022. The first two authors contributed equally

We formulate, analyze and solve the problem of best arm identification with fairness constraints on subpopulations (BAICS). Standard best arm identification problems aim at selecting an arm that has the largest expected reward where the expectation is taken over the entire population. The BAICS problem requires that an selected arm must be fair to all subpopulations (e.g., different ethnic groups, age groups, or customer types) by satisfying constraints that the expected reward conditional on every subpopulation needs to be larger than some thresholds. The BAICS problem aims at correctly identify, with high confidence, the arm with the largest expected reward from all arms that satisfy subpopulation constraints. We analyze the complexity of the BAICS problem by proving a best achievable lower bound on the sample complexity with closed-form representation. We then design an algorithm and prove that the algorithm's sample complexity matches with the lower bound in terms of order. A brief account of numerical experiments are conducted to illustrate the theoretical findings.

Plasticity, the ability of a neural network to quickly change its predictions in response to new information, is essential for the adaptability and robustness of deep reinforcement learning systems. Deep neural networks are known to lose plasticity over the course of training even in relatively simple learning problems, but the mechanisms driving this phenomenon are still poorly understood. This paper conducts a systematic empirical analysis into plasticity loss, with the goal of understanding the phenomenon mechanistically in order to guide the future development of targeted solutions. We find that loss of plasticity is deeply connected to changes in the curvature of the loss landscape, but that it typically occurs in the absence of saturated units or divergent gradient norms. Based on this insight, we identify a number of parameterization and optimization design choices which enable networks to better preserve plasticity over the course of training. We validate the utility of these findings in larger-scale learning problems by applying the best-performing intervention, layer normalization, to a deep RL agent trained on the Arcade Learning Environment., Accepted to ICML 2023

We study a game between liquidity provider and liquidity taker agents interacting in an over-the-counter market, for which the typical example is foreign exchange. We show how a suitable design of parameterized families of reward functions coupled with associated shared policy learning constitutes an efficient solution to this problem. Precisely, we show that our deep-reinforcement-learning-driven agents learn emergent behaviors relative to a wide spectrum of incentives encompassing profit-and-loss, optimal execution and market share, by playing against each other. In particular, we find that liquidity providers naturally learn to balance hedging and skewing as a function of their incentives, where the latter refers to setting their buy and sell prices asymmetrically as a function of their inventory. We further introduce a novel RL-based calibration algorithm which we found performed well at imposing constraints on the game equilibrium, both on toy and real market data.

Constructing asymptotically valid confidence intervals through a valid central limit theorem is crucial for A/B tests, where a classical goal is to statistically assert whether a treatment plan is significantly better than a control plan. In some emerging applications for online platforms, the treatment plan is not a single plan, but instead encompasses an infinite continuum of plans indexed by a continuous treatment parameter. As such, the experimenter not only needs to provide valid statistical inference, but also desires to effectively and adaptively find the optimal choice of value for the treatment parameter to use for the treatment plan. However, we find that classical optimization algorithms, despite of their fast convergence rates under convexity assumptions, do not come with a central limit theorem that can be used to construct asymptotically valid confidence intervals. We fix this issue by providing a new optimization algorithm that on one hand maintains the same fast convergence rate and on the other hand permits the establishment of a valid central limit theorem. We discuss practical implementations of the proposed algorithm and conduct numerical experiments to illustrate the theoretical findings.

In this paper we estimate the planar Tur\'an number $\mathrm{ex}_\mathcal{P}(n,H)$ of some graphs $H$, i.e., the maximum number of edges in a planar graph $G$ of $n$ vertices not containing $H$ as a subgraph. We give a new, short proof when $H=C_5$, and study the cases when $G$ is bipartite or triangle-free and $H$ is a short even cycle. The proofs are mostly new applications or variants of the "contribution method" introduced by Ghosh, Gy\H{o}ri, Martin, Paulos and Xiao in arXiv:2004.14094.

Aims/Introduction Body aging is a universal biological process. With aging, cells undergo a series of physiological changes. The main feature is cell proliferation decline, although the cells still have normal functions. Pancreatic β‐cells are no exception. However, the physiological senescence of β‐cells, and the resulting function and transcriptome changes have rarely attracted attention. The specific senescence phenotype of β‐cells remains unknown. Materials and Methods Pancreatic samples from three female C57BL/6 mice with aged 2.5 months (young) mice and 20 months (old) were digested to a single‐cell suspension and analyzed, with 10× Genomics single‐cell ribonucleic acid sequencing, β‐cells were determined by biosynthesis analysis, and differences between old and young mice were identified. Results A total of 47 differential genes with significant and statistical significance were screened in β‐cells (fold change >1.5, P, Transcription factors play an important role in facilitating transitions between pancreatic cells. The comprehensive datasets of aging‐related genes, transcription factors and pathways, and in almost all pancreatic cell types were provided. This study could serve as new therapies that attenuate aging and alleviate aging‐related diseases with further research.

Understanding the impact of the most effective policies or treatments on a response variable of interest is desirable in many empirical works in economics, statistics and other disciplines. Due to the widespread winner's curse phenomenon, conventional statistical inference assuming that the top policies are chosen independent of the random sample may lead to overly optimistic evaluations of the best policies. In recent years, given the increased availability of large datasets, such an issue can be further complicated when researchers include many covariates to estimate the policy or treatment effects in an attempt to control for potential confounders. In this manuscript, to simultaneously address the above-mentioned issues, we propose a resampling-based procedure that not only lifts the winner's curse in evaluating the best policies observed in a random sample, but also is robust to the presence of many covariates. The proposed inference procedure yields accurate point estimates and valid frequentist confidence intervals that achieve the exact nominal level as the sample size goes to infinity for multiple best policy effect sizes. We illustrate the finite-sample performance of our approach through Monte Carlo experiments and two empirical studies, evaluating the most effective policies in charitable giving and the most beneficial group of workers in the National Supported Work program., Accepted by The Journal of Econometrics

It is known that every strong tournament has directed cycles of any length, and thereby strong subtournaments of any size. In this note, we prove that they also can share a common vertex which is a king of all of them. This common vertex can be any king in the whole tournament. Further, the Hamiltonian cycles in them can be recursively constructed by inserting an additional vertex to one directed edge.

Exosomes are a new way of the communication between the tumor cell and macrophage in the micro-environment. The macrophage can be induced to different phenotypes according to the different tumors. In the present study, long-chain noncoding RNA HOTAIR (lncRNA HOTAIR) was highly expressed in LSCC and exosomes. The pathway of exosomal lncRNA HOTAIR inducing macrophage to M2 polarization in the LSCC was investigated. The carcinoma tissues and adjacent tissues were collected from 104 LSCC cases, and the positive relationship between CD163-/CD206-M2 macrophage infiltration and clinical phase, lymph node spreading and pathological phase in LSCC was observed. To examine the role of exosomal lncRNA HOTAIR, macrophages were co-cultured with LSCC-exosomes of high lncRNA HOTAIR expression or transferred with HOTAIR mimics. It was suggested that exosomal lncRNA HOTAIR can induce macrophages to M2 polarization by PI3K/p-AKT/AKT signaling pathway. Furthermore, exo-treated M2 macrophages facilitate the migration, proliferation, and EMT of LSCC.

Planning with a learned model is arguably a key component of intelligence. There are several challenges in realizing such a component in large-scale reinforcement learning (RL) problems. One such challenge is dealing effectively with continuous action spaces when using tree-search planning (e.g., it is not feasible to consider every action even at just the root node of the tree). In this paper we present a method for selecting affordances useful for planning -- for learning which small number of actions/options from a continuous space of actions/options to consider in the tree-expansion process during planning. We consider affordances that are goal-and-state-conditional mappings to actions/options as well as unconditional affordances that simply select actions/options available in all states. Our selection method is gradient based: we compute gradients through the planning procedure to update the parameters of the function that represents affordances. Our empirical work shows that it is feasible to learn to select both primitive-action and option affordances, and that simultaneously learning to select affordances and planning with a learned value-equivalent model can outperform model-free RL.

We study the stochastic multi-armed bandit problem and design new policies that enjoy both worst-case optimality for expected regret and light-tailed risk for regret distribution. Starting from the two-armed bandit setting with time horizon $T$, we propose a simple policy and prove that the policy (i) enjoys the worst-case optimality for the expected regret at order $O(\sqrt{T\ln T})$ and (ii) has the worst-case tail probability of incurring a linear regret decay at an exponential rate $\exp(-\Omega(\sqrt{T}))$, a rate that we prove to be best achievable for all worst-case optimal policies. Briefly, our proposed policy achieves a delicate balance between doing more exploration at the beginning of the time horizon and doing more exploitation when approaching the end, compared to the standard Successive Elimination policy and Upper Confidence Bound policy. We then improve the policy design and analysis to work for the general $K$-armed bandit setting. Specifically, the worst-case probability of incurring a regret larger than any $x>0$ is upper bounded by $\exp(-\Omega(x/\sqrt{KT}))$. We then enhance the policy design to accommodate the "any-time" setting where $T$ is not known a priori, and prove equivalently desired policy performances as compared to the "fixed-time" setting with known $T$. A brief account of numerical experiments is conducted to illustrate the theoretical findings. We conclude by extending our proposed policy design to the general stochastic linear bandit setting and proving that the policy leads to both worst-case optimality in terms of expected regret order and light-tailed risk on the regret distribution., Comment: Preliminary version appeared in NeurIPS 2022

We formulate selecting the best optimizing system (SBOS) problems and provide solutions for those problems. In an SBOS problem, a finite number of systems are contenders. Inside each system, a continuous decision variable affects the system's expected performance. An SBOS problem compares different systems based on their expected performances under their own optimally chosen decision to select the best, without advance knowledge of expected performances of the systems nor the optimizing decision inside each system. We design easy-to-implement algorithms that adaptively chooses a system and a choice of decision to evaluate the noisy system performance, sequentially eliminates inferior systems, and eventually recommends a system as the best after spending a user-specified budget. The proposed algorithms integrate the stochastic gradient descent method and the sequential elimination method to simultaneously exploit the structure inside each system and make comparisons across systems. For the proposed algorithms, we prove exponential rates of convergence to zero for the probability of false selection, as the budget grows to infinity. We conduct three numerical examples that represent three practical cases of SBOS problems. Our proposed algorithms demonstrate consistent and stronger performances in terms of the probability of false selection over benchmark algorithms under a range of problem settings and sampling budgets., Comment: Code in https://github.com/nian-si/SelectOptSys

Additional file 1.

In an influential paper, Courtois and Semal (1984) establish that when $G$ is an irreducible substochastic matrix for which $\sum_{n=0}^{\infty}G^n

Reinforcement learning (RL) is a machine learning paradigm concerned with how an agent learns to predict and control its own experience stream so as to maximize long-term cumulative reward. In the past decade, deep reinforcement learning (DeepRL), a subfield that aims to combine the sequential decision-making techniques in RL with the powerful non-linear function approximation tools offered by deep learning, has seen great success such as defeating human champions in the ancient board game Go and achieving expert-level performance in complex strategy games like Dota $2$ and Starcraft. It has also had an impact on real-world applications. Examples include robot control, stratospheric balloon navigation, and controlling nuclear fusion plasma. This thesis aims to further advance DeepRL techniques. Concretely, this thesis makes contributions in the following four directions: 1) In reward design, we develop a novel meta-learning algorithm for learning reward functions that facilitate policy optimization. Our algorithm improves the performance of policy-gradient methods and outperforms handcrafted heuristic reward functions. In a follow-up study, we show that the learned reward functions can capture knowledge about long-term exploration and exploitation and can generalize to different RL algorithms and changes in the environment dynamics. 2) In temporal credit assignment, we explore methods based on pairwise weights that are functions of the state in which the action was taken, the state in which the reward was received, and the time elapsed in between. We develop a metagradient algorithm for adapting these weights during policy learning. Our experiments show that our method achieves better performance than competing approaches. 3) In state representation learning, we investigate using random deep action-conditional prediction tasks as auxiliary tasks to help agents learn better state representations. Our experiments show that random deep action-conditional predictions can often yield better performance than handcrafted auxiliary tasks. 4) In model learning and planning, we develop a new method for learning value-equivalent models, a class of models that demonstrates strong empirical performance lately, that generalizes existing methods. Our experiments show that our method can improve both the model prediction accuracy and the control performance of the downstream planning procedure.

Nonsmooth nonconvex optimization problems broadly emerge in machine learning and business decision making, whereas two core challenges impede the development of efficient solution methods with finite-time convergence guarantee: the lack of computationally tractable optimality criterion and the lack of computationally powerful oracles. The contributions of this paper are two-fold. First, we establish the relationship between the celebrated Goldstein subdifferential~\citep{Goldstein-1977-Optimization} and uniform smoothing, thereby providing the basis and intuition for the design of gradient-free methods that guarantee the finite-time convergence to a set of Goldstein stationary points. Second, we propose the gradient-free method (GFM) and stochastic GFM for solving a class of nonsmooth nonconvex optimization problems and prove that both of them can return a $(\delta,\epsilon)$-Goldstein stationary point of a Lipschitz function $f$ at an expected convergence rate at $O(d^{3/2}\delta^{-1}\epsilon^{-4})$ where $d$ is the problem dimension. Two-phase versions of GFM and SGFM are also proposed and proven to achieve improved large-deviation results. Finally, we demonstrate the effectiveness of 2-SGFM on training ReLU neural networks with the \textsc{Minst} dataset., Comment: Accepted by NeurIPS 2022; 32 pages, 18 figures; Fix a confusing part in the proof of Theorem 3.1: we use Bertsekas [1973, Proposition 2.3] rather than Bertsekas [1973, Proposition 2.4] here and do not assume the convexity of the function f

Let the crown $C_{13}$ be the linear $3$-graph on $9$ vertices $\{a,b,c,d,e,f,g,h,i\}$ with edges $$E = \{\{a,b,c\}, \{a, d,e\}, \{b, f, g\}, \{c, h,i\}\}.$$ Proving a conjecture of Gy\'arf\'as et. al., we show that for any crown-free linear $3$-graph $G$ on $n$ vertices, its number of edges satisfy $$\lvert E(G) \rvert \leq \frac{3(n - s)}{2}$$ where $s$ is the number of vertices in $G$ with degree at least $6$. This result, combined with previous work, essentially completes the determination of linear Tur\'an number for linear $3$-graphs with at most $4$ edges., Comment: 5 pages, 1 figures. Correct Typos, and add acknowledgement to Professor Gyarfas

Our main contribution in this work is an empirical finding that random General Value Functions (GVFs), i.e., deep action-conditional predictions -- random both in what feature of observations they predict as well as in the sequence of actions the predictions are conditioned upon -- form good auxiliary tasks for reinforcement learning (RL) problems. In particular, we show that random deep action-conditional predictions when used as auxiliary tasks yield state representations that produce control performance competitive with state-of-the-art hand-crafted auxiliary tasks like value prediction, pixel control, and CURL in both Atari and DeepMind Lab tasks. In another set of experiments we stop the gradients from the RL part of the network to the state representation learning part of the network and show, perhaps surprisingly, that the auxiliary tasks alone are sufficient to learn state representations good enough to outperform an end-to-end trained actor-critic baseline. We opensourced our code at https://github.com/Hwhitetooth/random_gvfs., NeurIPS 2021

Let the crown $C_{13}$ be the linear $3$-graph on $9$ vertices $\{a,b,c,d,e,f,g,h,i\}$ with edges $$E = \{\{a,b,c\}, \{a, d,e\}, \{b, f, g\}, \{c, h,i\}\}.$$ Proving a conjecture of Gy��rf��s et. al., we show that for any crown-free linear $3$-graph $G$ on $n$ vertices, its number of edges satisfy $$\lvert E(G) \rvert \leq \frac{3(n - s)}{2}$$ where $s$ is the number of vertices in $G$ with degree at least $6$. This result, combined with previous work, essentially completes the determination of linear Tur��n number for linear $3$-graphs with at most $4$ edges., 5 pages, 1 figures. Correct Typos, and add acknowledgement to Professor Gyarfas

Motivated by emerging applications such as live-streaming e-commerce, promotions and recommendations, we introduce and solve a general class of non-stationary multi-armed bandit problems that have the following two features: (i) the decision maker can pull and collect rewards from up to $K\,(\ge 1)$ out of $N$ different arms in each time period; (ii) the expected reward of an arm immediately drops after it is pulled, and then non-parametrically recovers as the arm's idle time increases. With the objective of maximizing the expected cumulative reward over $T$ time periods, we design a class of ``Purely Periodic Policies'' that jointly set a period to pull each arm. For the proposed policies, we prove performance guarantees for both the offline problem and the online problems. For the offline problem when all model parameters are known, the proposed periodic policy obtains an approximation ratio that is at the order of $1-\mathcal O(1/\sqrt{K})$, which is asymptotically optimal when $K$ grows to infinity. For the online problem when the model parameters are unknown and need to be dynamically learned, we integrate the offline periodic policy with the upper confidence bound procedure to construct on online policy. The proposed online policy is proved to approximately have $\widetilde{\mathcal O}(N\sqrt{T})$ regret against the offline benchmark. Our framework and policy design may shed light on broader offline planning and online learning applications with non-stationary and recovering rewards., Comment: v1 accepted by ICML 2021

Conditional Generative Adversarial Networks are known to be difficult to train, especially when the conditions are continuous and high-dimensional. To partially alleviate this difficulty, we propose a simple generator regularization term on the GAN generator loss in the form of Lipschitz penalty. Thus, when the generator is fed with neighboring conditions in the continuous space, the regularization term will leverage the neighbor information and push the generator to generate samples that have similar conditional distributions for each neighboring condition. We analyze the effect of the proposed regularization term and demonstrate its robust performance on a range of synthetic and real-world tasks.

Optimal transport (OT) distances are increasingly used as loss functions for statistical inference, notably in the learning of generative models or supervised learning. Yet, the behavior of minimum Wasserstein estimators is poorly understood, notably in high-dimensional regimes or under model misspecification. In this work we adopt the viewpoint of projection robust (PR) OT, which seeks to maximize the OT cost between two measures by choosing a $k$-dimensional subspace onto which they can be projected. Our first contribution is to establish several fundamental statistical properties of PR Wasserstein distances, complementing and improving previous literature that has been restricted to one-dimensional and well-specified cases. Next, we propose the integral PR Wasserstein (IPRW) distance as an alternative to the PRW distance, by averaging rather than optimizing on subspaces. Our complexity bounds can help explain why both PRW and IPRW distances outperform Wasserstein distances empirically in high-dimensional inference tasks. Finally, we consider parametric inference using the PRW distance. We provide an asymptotic guarantee of two types of minimum PRW estimators and formulate a central limit theorem for max-sliced Wasserstein estimator under model misspecification. To enable our analysis on PRW with projection dimension larger than one, we devise a novel combination of variational analysis and statistical theory., Accepted by AISTATS 2021; Fix some inaccuracy in the definition and proof; 49 Pages, 41 figures

We propose a framework that integrates classical Monte Carlo simulators and Wasserstein generative adversarial networks to model, estimate, and simulate a broad class of arrival processes with general non-stationary and multi-dimensional random arrival rates. Classical Monte Carlo simulators have advantages at capturing the interpretable "physics" of a stochastic object, whereas neural-network-based simulators have advantages at capturing less-interpretable complicated dependence within a high-dimensional distribution. We propose a doubly stochastic simulator that integrates a stochastic generative neural network and a classical Monte Carlo Poisson simulator, to utilize both advantages. Such integration brings challenges to both theoretical reliability and computational tractability for the estimation of the simulator given real data, where the estimation is done through minimizing the Wasserstein distance between the distribution of the simulation output and the distribution of real data. Regarding theoretical properties, we prove consistency and convergence rate for the estimated simulator under a non-parametric smoothness assumption. Regarding computational efficiency and tractability for the estimation procedure, we address a challenge in gradient evaluation that arise from the discontinuity in the Monte Carlo Poisson simulator. Numerical experiments with synthetic and real data sets are implemented to illustrate the performance of the proposed framework., Comment: We appreciate a lot the comments and suggestions from anonymous reviewers and editors. This is updated version, and with title changed from "Doubly Stochastic Generative Arrivals Modeling" to "A Doubly Stochastic Simulator with Applications in Arrivals Modeling and Simulation"

We develop and analyze a set of new sequential simulation-optimization algorithms for large-scale multi-dimensional discrete optimization via simulation problems with a convexity structure. The "large-scale" notion refers to that the decision variable has a large number of values to choose from on each dimension. The proposed algorithms are targeted to identify a solution that is close to the optimal solution given any precision level with any given probability. To achieve this target, utilizing the convexity structure, our algorithm design does not need to scan all the choices of the decision variable, but instead sequentially draws a subset of choices of the decision variable and uses them to "localize" potentially near-optimal solutions to an adaptively shrinking region. To show the power of the localization operation, we first consider one-dimensional large-scale problems. We propose the shrinking uniform sampling algorithm, which is proved to achieve the target with an optimal expected simulation cost under an asymptotic criterion. For multi-dimensional problems, we combine the idea of localization with subgradient information and propose a framework to design stochastic cutting-plane methods and the dimension reduction algorithm, whose expected simulation cost have a low dependence on the scale and the dimension of the problems. The proposed algorithms do not require prior information about the Lipschitz constant of the objective function and the simulation costs are upper bounded by a value that is independent of the Lipschitz constant. Finally, we propose an adaptive algorithm to deal with the unknown noise variance case under the assumption that the randomness of the system is Gaussian. We implement the proposed algorithms on both synthetic and queueing simulation optimization problems, and demonstrate better performances compared to benchmark methods.

The objective of a reinforcement learning agent is to behave so as to maximise the sum of a suitable scalar function of state: the reward. These rewards are typically given and immutable. In this paper, we instead consider the proposition that the reward function itself can be a good locus of learned knowledge. To investigate this, we propose a scalable meta-gradient framework for learning useful intrinsic reward functions across multiple lifetimes of experience. Through several proof-of-concept experiments, we show that it is feasible to learn and capture knowledge about long-term exploration and exploitation into a reward function. Furthermore, we show that unlike policy transfer methods that capture "how" the agent should behave, the learned reward functions can generalise to other kinds of agents and to changes in the dynamics of the environment by capturing "what" the agent should strive to do., ICML 2020. The first two authors contributed equally

Ethereum is an open-source, public, block chain-based distributed computing platform and operating system featuring smart contract functionality. In this paper, we proposed an Ethereum based electronic voting (e-voting) protocol, Ques-Chain, which can ensure the authentication can be done without hurting confidentiality and the anonymity can be protected without problems of scams at the same time. Furthermore, the authors considered the wider usages Ques-Chain can be applied on, pointing out that it is able to process all kinds of messages and can be used in all fields with similar needs.

Ethereum is an open-source, public, blockchain-based distributed computing platform and operating system featuring smart contract functionality. In this paper, we proposed an Ethereum based eletronic voting (e-voting) protocol, Ques-Chain, which can ensure the authentication can be done without hurting confidentiality and the anonymity can be protected without problems of scams at the same time. Furthermore, the authors considered the wider usages Ques-Chain can be applied on, pointing out that it is able to process all kinds of messages and can be used in all fields with similar needs.

The shape, size and position of the defect on the RL(radial and longitudinal) plane of the wood cannot be obtained by conventional wood cross-sectional imaging. To overcome such limitations, A novel imaging method for the internal defects on the RL Plane of the wood was proposed. The propagation velocity of the stress wave is converted into the value of the estimated point on the RL plane of wood and the two-dimensional imaging of the RL plane of wood is realized by using the velocity correction interpolation method. The proposed method and IDW method are quantitatively analyzed using the method of confusion matrix. The imaging results of 5 samples with defects of different shapes show the effectiveness of the proposed method and the defects of RL plane of wood can be reflected.

With the further development of technology, providing technical support for the forecast and development of fashion design trends through artificial intelligence has gradually become a reality. In order to enable users to obtain more accurate design trend materials in a shorter time, this paper presents a ‘searching by image’ model of clothing trends based on the ResNet50 model. Through the targeted collection of data and the rational construction of algorithms, the system can retrieve and output more image materials with relevant design features for the existing image materials for the development of design trends as well as the development and design of styles. By comparing the system with Google’s and Taobao’s ‘searching by image’ system, it is concluded that this system has high efficiency, high accuracy and high correlation.

This paper introduces a new asymptotic regime for simplifying stochastic models having non-stationary effects, such as those that arise in the presence of time-of-day effects. This regime describes an operating environment within which the arrival process to a service system has an arrival intensity that is fluctuating rapidly. We show that such a service system is well approximated by the corresponding model in which the arrival process is Poisson with a constant arrival rate. In addition to the basic weak convergence theorem, we also establish a first order correction for the distribution of the cumulative number of arrivals over $[0,t]$, as well as the number-in-system process for an infinite-server queue fed by an arrival process having a rapidly changing arrival rate. This new asymptotic regime provides a second regime within which non-stationary stochastic models can be reasonably approximated by a process with stationary dynamics, thereby complementing the previously studied setting within which rates vary slowly in time.

This paper is concerned with the development of rigorous approximations to various expectations associated with Markov chains and processes having non-stationary transition probabilities. Such non-stationary models arise naturally in contexts in which time-of-day effects or seasonality effects need to be incorporated. Our approximations are valid asymptotically in regimes in which the transition probabilities change slowly over time. Specifically, we develop approximations for the expected infinite horizon discounted reward, the expected reward to the hitting time of a set, the expected reward associated with the state occupied by the chain at time $n$, and the expected cumulative reward over an interval $[0,n]$. In each case, the approximation involves a linear system of equations identical in form to that which one would need to solve to compute the corresponding quantity for a Markov model having stationary transition probabilities. In that sense, the theory provides an approximation no harder to compute than in the traditional stationary context. While most of the theory is developed for finite state Markov chains, we also provide generalizations to continuous state Markov chains, and finite state Markov jump processes in continuous time. In the latter context, one of our approximations coincides with the uniform acceleration asymptotic due to Massey and Whitt (1998)., Comment: 29 pages

Deep learning models can take weeks to train on a single GPU-equipped machine, necessitating scaling out DL training to a GPU-cluster. However, current distributed DL implementations can scale poorly due to substantial parameter synchronization over the network, because the high throughput of GPUs allows more data batches to be processed per unit time than CPUs, leading to more frequent network synchronization. We present Poseidon, an efficient communication architecture for distributed DL on GPUs. Poseidon exploits the layered model structures in DL programs to overlap communication and computation, reducing bursty network communication. Moreover, Poseidon uses a hybrid communication scheme that optimizes the number of bytes required to synchronize each layer, according to layer properties and the number of machines. We show that Poseidon is applicable to different DL frameworks by plugging Poseidon into Caffe and TensorFlow. We show that Poseidon enables Caffe and TensorFlow to achieve 15.5x speed-up on 16 single-GPU machines, even with limited bandwidth (10GbE) and the challenging VGG19-22K network for image classification. Moreover, Poseidon-enabled TensorFlow achieves 31.5x speed-up with 32 single-GPU machines on Inception-V3, a 50% improvement over the open-source TensorFlow (20x speed-up)., To appear in 2017 USENIX Annual Technical Conference

Translation of Data analysis algorithms from data analysis language to high-level programming language is hard work when we construct a cloud computing platform for data analysis. It adds implementation difficulty and maintenance cost of constructing the platform. This paper suggests a new method to use the popular data analysis language R directly on constructing a cloud computing platform. By using resource virtualization techniques, computing resource environment is virtualized into R cluster based on given configurations. By allocating different R machines from R cluster to specified data analysis service, we solve the problem that data analysis algorithms implemented in R should be run in single-user mode only and cannot be customized. After verification, this method simplifies the work of translating data analysis algorithms and speeds up the process of constructing a cloud computing platform for data analysis.

Econophysics and econometrics agree that there is a correlation between volume and volatility in a time series. Using empirical data and their distributions, we further investigate this correlation and discover new ways that volatility and volume interact, particularly when the levels of both are high. We find that the distribution of the volume-conditional volatility is well fit by a power-law function with an exponential cutoff. We find that the volume-conditional volatility distribution scales with volume, and collapses these distributions to a single curve. We exploit the characteristics of the volume-volatility scatter plot to find a strong correlation between logarithmic volume and a quantity we define as local maximum volatility (LMV), which indicates the largest volatility observed in a given range of trading volumes. This finding supports our empirical analysis showing that volume is an excellent predictor of the maximum value of volatility for both same-day and near-future time periods. We also use a joint conditional probability that includes both volatility and volume to demonstrate that invoking both allows us to better predict the largest next-day volatility than invoking either one alone.