cssi/SciSciGPT-SciSciNet huggingface dataset:
Aligned Image Sets and the Generalized Degrees of Freedom of Symmetric MIMO Interference Channel With Partial CSIT

The generalized degrees of freedom of the two-user symmetric multiple input multiple output interference channel are characterized as a function of the channel strength levels and the level of channel state information at the transmitters. In this symmetric setting, each transmitter is equipped with $M$ antennas, each receiver is equipped with $N$ antennas, and both cross links have the same strength parameter $\alpha $ and the same channel uncertainty parameter $\beta $ . The main challenge resides in the proof of the outer bound which is accomplished by a generalization of the aligned image sets approach.
Quantifying operational constraints of low-latency telerobotics for planetary surface operations

NASA's Space Launch System (SLS) and Orion crew vehicle will launch humans to cislunar space in the early 2020s to begin the new era of space exploration. NASA plans to use the Orion crew vehicle to transport humans between Earth and cislunar space where there will be a stationed habitat known as the “Deep Space Gateway” (DSG). The proximity to the lunar surface allows for direct communication between the DSG and surface assets, which enables low-latency telerobotic exploration. While this exploration method is promising, the operational constraints must be fully explored on Earth before being utilized on space exploration missions. This paper identifies two constraints on space exploration using low-latency surface telerobotics and attempts to quantify these constraints. One constraint associated with low-latency surface telerobotics is the bandwidth available between the orbiting command station and the ground assets. The bandwidth available will vary during operation. As a result, it is critical to quantify the operational video conditions required for effective exploration. We designed an experiment to quantify the threshold frame rate required for effective exploration. The experiment simulated geological exploration via low-latency surface telerobotics using a modified commercial-off-the-shelf (COTS) rover in a lunar analog environment. The results from this experiment indicate that humans should operate above a threshold frame rate of 5 frames per second. In a separate, but similar experiment, we introduced a 2.6 second delay in the video system. This delay recreated the latency conditions present when operating rovers on the lunar farside from an Earth-based command station. This time delay was compared to low-latency conditions for teleoperation at the DSG (≤0.4 seconds). The results from this experiment show a 150% increase in exploration time when the latency is increased to 2.6 seconds. This indicates that such a delay significantly complicates real-time exploration strategies.
Safety-Aware Apprenticeship Learning

Apprenticeship learning (AL) is a kind of Learning from Demonstration techniques where the reward function of a Markov Decision Process (MDP) is unknown to the learning agent and the agent has to derive a good policy by observing an expert’s demonstrations. In this paper, we study the problem of how to make AL algorithms inherently safe while still meeting its learning objective. We consider a setting where the unknown reward function is assumed to be a linear combination of a set of state features, and the safety property is specified in Probabilistic Computation Tree Logic (PCTL). By embedding probabilistic model checking inside AL, we propose a novel counterexample-guided approach that can ensure safety while retaining performance of the learnt policy. We demonstrate the effectiveness of our approach on several challenging AL scenarios where safety is essential.
A Geometric Analysis of the AWGN Channel With a $(\sigma , \rho )$ -Power Constraint

In this paper, we consider the additive white Gaussian noise (AWGN) channel with a power constraint called the $(\sigma , \rho )$ -power constraint, which is motivated by energy harvesting communication systems. Given a codeword, the constraint imposes a limit of $\sigma + k \rho $ on the total power of any $k\geq 1$ consecutive transmitted symbols. Such a channel has infinite memory and evaluating its exact capacity is a difficult task. Consequently, we establish an $n$ -letter capacity expression and seek bounds for the same. We obtain a lower bound on capacity by considering the volume of $ {\mathcal{ S}}_{n}(\sigma , \rho ) \subseteq \mathbb {R}^{n}$ , which is the set of all length $n$ sequences satisfying the $(\sigma , \rho )$ -power constraints. For a noise power of $\nu $ , we obtain an upper bound on capacity by considering the volume of $ {\mathcal{ S}}_{n}(\sigma , \rho ) \oplus B_{n}(\sqrt {n\nu })$ , which is the Minkowski sum of $ {\mathcal{ S}}_{n}(\sigma , \rho )$ and the $n$ -dimensional Euclidean ball of radius $\sqrt {n\nu }$ . We analyze this bound using a result from convex geometry known as Steiner’s formula, which gives the volume of this Minkowski sum in terms of the intrinsic volumes of $ {\mathcal{ S}}_{n}(\sigma , \rho )$ . We show that as the dimension $n$ increases, the logarithm of the sequence of intrinsic volumes of $\{ {\mathcal{ S}}_{n}(\sigma , \rho )\}$ converges to a limit function under an appropriate scaling. The upper bound on capacity is then expressed in terms of this limit function. We derive the asymptotic capacity in the low- and high-noise regime for the $(\sigma , \rho )$ -power constrained AWGN channel, with strengthened results for the special case of $\sigma = 0$ , which is the amplitude constrained AWGN channel.
Stochastic Pooling for Regularization of Deep Convolutional Neural Networks

Abstract: We introduce a simple and effective method for regularizing large convolutional neural networks. We replace the conventional deterministic pooling operations with a stochastic procedure, randomly picking the activation within each pooling region according to a multinomial distribution, given by the activities within the pooling region. The approach is hyper-parameter free and can be combined with other regularization approaches, such as dropout and data augmentation. We achieve state-of-the-art performance on four image datasets, relative to other approaches that do not utilize data augmentation.
Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approximation

Consider the problem of estimating the Shannon entropy of a distribution over $k$ elements from $n$ independent samples. We show that the minimax mean-square error is within the universal multiplicative constant factors of $\big ({k }/{n \log k}\big )^{2} + {\log ^{2} k}/{n}$ if $n$ exceeds a constant factor of $({k}/{\log k})$ ; otherwise, there exists no consistent estimator. This refines the recent result of Valiant and Valiant that the minimal sample size for consistent entropy estimation scales according to $\Theta ({k}/{\log k})$ . The apparatus of the best polynomial approximation plays a key role in both the construction of optimal estimators and, by a duality argument, the minimax lower bound.
Sequence-to-Sequence Learning as Beam-Search Optimization

Sequence-to-Sequence (seq2seq) modeling has rapidly become an important general-purpose NLP tool that has proven effective for many text-generation and sequence-labeling tasks. Seq2seq builds on deep neural language modeling and inherits its remarkable accuracy in estimating local, next-word distributions. In this work, we introduce a model and beam-search training scheme, based on the work of Daume III and Marcu (2005), that extends seq2seq to learn global sequence scores. This structured approach avoids classical biases associated with local training and unifies the training loss with the test-time usage, while preserving the proven model architecture of seq2seq and its efficient training approach. We show that our system outperforms a highly-optimized attention-based seq2seq system and other baselines on three different sequence to sequence tasks: word ordering, parsing, and machine translation.
Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs

We show how to adjust a very nice coupling argument due to McDiarmid in order to prove/reprove in a novel way results concerning Hamilton cycles in various models of random graph and hypergraphs. In particular, we firstly show that for $k\geq 3$, if $pn^{k-1}/\log n$ tends to infinity, then a random $k$-uniform hypergraph on $n$ vertices, with edge probability $p$, with high probability (w.h.p.) contains a loose Hamilton cycle, provided that $(k-1)|n$. This generalizes results of Frieze, Dudek and Frieze, and reproves a result of Dudek, Frieze, Loh and Speiss. Secondly, we show that there exists $K>0$ such for every $p\geq (K\log n)/n$ the following holds: Let $G_{n,p}$ be a random graph on $n$ vertices with edge probability $p$, and suppose that its edges are being colored with $n$ colors uniformly at random. Then, w.h.p. the resulting graph contains a Hamilton cycle with for which all the colors appear (a rainbow Hamilton cycle). Bal and Frieze proved the latter statement for graphs on an even number of vertices, where for odd $n$ their $p$ was $\omega((\log n)/n)$. Lastly, we show that for $p=(1+o(1))(\log n)/n$, if we randomly color the edge set of a random directed graph $D_{n,p}$ with $(1+o(1))n$ colors, then w.h.p. one can find a rainbow Hamilton cycle where all the edges are directed in the same way.
Competing with the Empirical Risk Minimizer in a Single Pass

In many estimation problems, e.g. linear and logistic regression, we wish to minimize an unknown objective given only unbiased samples of the objective function. Furthermore, we aim to achieve this using as few samples as possible. In the absence of computational constraints, the minimizer of a sample average of observed data ‐ commonly referred to as either the empirical risk minimizer (ERM) or the M -estimator ‐ is widely regarded as the estimation strategy of choice due to its desirable statistical convergence properties. Our goal in this work is to perform as well as the ERM, on every problem, while minimizing the use of computational resources such as running time and space usage. We provide a simple streaming algorithm which, under standard regularity assumptions on the underlying problem, enjoys the following properties: 1. The algorithm can be implemented in linear time with a single pass of the observed data, using space linear in the size of a single sample. 2. The algorithm achieves the same statistical rate of convergence as the empirical risk minimizer on every problem, even considering constant factors. 3. The algorithm’s performance depends on the initial error at a rate that decreases super-polynomially. 4. The algorithm is easily parallelizable. Moreover, we quantify the (finite-sample) rate at which the algorithm becomes competitive with the ERM.
Stability and sparsity in sets of natural numbers

Given a set A ⊆ ℕ, we consider the relationship between stability of the structure (ℤ, + , 0,A) and sparsity of the set A. We first show that a strong enough sparsity assumption on A yields stability of (ℤ, +, 0, A). Specifically, if there is a function f: A → ℝ+ such that supa∈A |a − f(a)| < ∞ and { $$\frac{s}{t}:s,t \in f(A) $$ , t ≤ s} is closed and discrete, then (ℤ, +, 0, A) is superstable (of U-rank ω if A is infinite). Such sets include examples considered by Palacin and Sklinos [19] and Poizat [23], many classical linear recurrence sequences (e.g., the Fibonaccci numbers), and any set in which the limit of ratios of consecutive elements diverges. Finally, we consider sparsity conclusions on sets A ⊆ N, which follow from model theoretic assumptions on (ℤ, +, 0, A). We use a result of Erdős, Nathanson and Sarkozy [8] to show that if (ℤ, +, 0, A) does not define the ordering on ℤ, then the lower asymptotic density of any finitary sumset of A is zero. Finally, in a theorem communicated to us by Goldbring, we use a result of Jin [11] to show that if (ℤ, +, 0,A) is stable, then the upper Banach density of any finitary sumset of A is zero.
FastScan: Robust Low-Complexity Rate Adaptation Algorithm for Video Streaming Over HTTP

This paper proposes and evaluates a novel algorithm for streaming video over HTTP. The problem is formulated as a non-convex optimization problem which is constrained by the predicted available bandwidth, chunk deadlines, available video rates, and buffer occupancy. The objective is to optimize a QoE metric that maintains a tradeoff between maximizing the playback rate of every chunk and ensuring fairness among different chunks for the minimum re-buffering time. We propose FastScan, a low complexity algorithm that solves the problem. The online adaptations for dynamic bandwidth environments are proposed with imperfect available bandwidth prediction. The results of experiments driven by variable bit rate (VBR) encoded video, video platform system (dash.js), and cellular bandwidth traces of a public dataset reveal the robustness of the online version of FastScan algorithm and demonstrate its significant performance improvement as compared to the considered state-of-the-art video streaming algorithms. For example, on an experiment conducted over 100 real cellular available bandwidth traces of a public dataset that spans different available bandwidth regimes, our proposed algorithm (FastScan) achieves the minimum re-buffering (stall) time and the maximum average playback rate in every single trace as compared to Bola, Festive, BBA, RB, FastMPC, and Pensieve algorithms.
NeuroNER: an easy-to-use program for named-entity recognition based on neural networks

Named-entity recognition (NER) aims at identifying entities of interest in a text. Artificial neural networks (ANNs) have recently been shown to outperform existing NER systems. However, ANNs remain challenging to use for non-expert users. In this paper, we present NeuroNER, an easy-to-use named-entity recognition tool based on ANNs. Users can annotate entities using a graphical web-based user interface (BRAT): the annotations are then used to train an ANN, which in turn predict entities’ locations and categories in new texts. NeuroNER makes this annotation-training-prediction flow smooth and accessible to anyone.
Realizations and Factorizations of Positive Definite Kernels

Given a fixed sigma-finite measure space $$\left( X,\mathscr {B},\nu \right) $$ , we shall study an associated family of positive definite kernels K. Their factorizations will be studied with view to their role as covariance kernels of a variety of stochastic processes. In the interesting cases, the given measure $$\nu $$ is infinite, but sigma-finite. We introduce such positive definite kernels $$K\left( \cdot ,\cdot \right) $$ with the two variables from the subclass of the sigma-algebra $$\mathscr {B}$$ whose elements are sets with finite $$\nu $$ measure. Our setting and results are motivated by applications. The latter are covered in the second half of the paper. We first make precise the notions of realizations and factorizations for K, and we give necessary and sufficient conditions for K to have realizations and factorizations in $$L^{2}\left( \nu \right) $$ . Tools in the proofs rely on probability theory and on spectral theory for unbounded operators in Hilbert space. Applications discussed here include the study of reversible Markov processes, and realizations of Gaussian fields, and their Ito-integrals.
The Block Point Process Model for Continuous-time Event-based Dynamic Networks

We consider the problem of analyzing timestamped relational events between a set of entities, such as messages between users of an on-line social network. Such data are often analyzed using static or discrete-time network models, which discard a significant amount of information by aggregating events over time to form network snapshots. In this paper, we introduce a block point process model (BPPM) for continuous-time event-based dynamic networks. The BPPM is inspired by the well-known stochastic block model (SBM) for static networks. We show that networks generated by the BPPM follow an SBM in the limit of a growing number of nodes. We use this property to develop principled and efficient local search and variational inference procedures initialized by regularized spectral clustering. We fit BPPMs with exponential Hawkes processes to analyze several real network data sets, including a Facebook wall post network with over 3,500 nodes and 130,000 events.
Exponential bounds for convergence of entropy rate approximations in hidden Markov models satisfying a path-mergeability condition

Abstract A hidden Markov model (HMM) is said to have path-mergeable states if for any two states i , j there exist a word w and state k such that it is possible to transition from both i and j to k while emitting w . We show that for a finite HMM with path-mergeable states the block estimates of the entropy rate converge exponentially fast. We also show that the path-mergeability property is asymptotically typical in the space of HMM topologies and easily testable.
Haar systems on equivalent groupoids

For second countable locally compact Hausdorff groupoids, the property of possessing a Haar system is preserved by equivalence.
Risk aversion in finite Markov Decision Processes using total cost criteria and average value at risk

In this paper we present an algorithm to compute risk averse policies in Markov Decision Processes (MDP) when the total cost criterion is used together with the average value at risk (AVaR) metric. Risk averse policies are needed when large deviations from the expected behavior may have detrimental effects, and conventional MDP algorithms usually ignore this aspect. We provide conditions for the structure of the underlying MDP ensuring that approximations for the exact problem can be derived and solved efficiently. Our findings are novel inasmuch as average value at risk has not previously been considered in association with the total cost criterion. Our method is demonstrated in a rapid deployment scenario, whereby a robot is tasked with the objective of reaching a target location within a temporal deadline where increased speed is associated with increased probability of failure. We demonstrate that the proposed algorithm not only produces a risk averse policy reducing the probability of exceeding the expected temporal deadline, but also provides the statistical distribution of costs, thus offering a valuable analysis tool.
The Fast Convergence of Incremental PCA

We consider a situation in which we see samples Xn ∈ ℝd drawn i.i.d. from some distribution with mean zero and unknown covariance A. We wish to compute the top eigenvector of A in an incremental fashion - with an algorithm that maintains an estimate of the top eigenvector in O(d) space, and incrementally adjusts the estimate with each new data point that arrives. Two classical such schemes are due to Krasulina (1969) and Oja (1983). We give finite-sample convergence rates for both.
Symplectic isometries of stabilizer codes

In this paper, we study the equivalence of quantum stabilizer codes via symplectic isometries of stabilizer codes. We define monomially and symplectically equivalent stabilizer codes and determine ...
Sharp singular Adams inequalities in high order Sobolev spaces

In this paper, we prove a version of weighted inequalities of exponential type for fractional integrals with sharp constants in any domain of finite measure in $\mathbb{R}^{n}$. Using this we prove a sharp singular Adams inequality in high order Sobolev spaces in bounded domain at critical case. Then we prove sharp singular Adams inequalities for high order derivatives on unbounded domains. Our results extend the singular Moser-Trudinger inequalities of first order in \cite{Ad2, R, LR, AdY} to the higher order Sobolev spaces $W^{m,\frac{n}{m}}$ and the results of \cite{RS} on Adams type inequalities in unbounded domains to singular case. Our singular Adams inequality on $W^{2,2}(\mathbb{R}^{4})$ with standard Sobolev norm at the critical case settles a unsolved question remained in \cite{Y}.
Leavitt path algebras with coefficients in a commutative ring

Abstract Given a directed graph E we describe a method for constructing a Leavitt path algebra L R ( E ) whose coefficients are in a commutative unital ring R . We prove versions of the Graded Uniqueness Theorem and Cuntz–Krieger Uniqueness Theorem for these Leavitt path algebras, giving proofs that both generalize and simplify the classical results for Leavitt path algebras over fields. We also analyze the ideal structure of L R ( E ) , and we prove that if K is a field, then L K ( E ) ≅ K ⊗ Z L Z ( E ) .
On hyperinterpolation on the unit ball

Abstract We prove estimates on the Lebesgue constants of the hyperinterpolation operator for functions on the unit ball B d ⊂ R d , with respect to Gegenbauer weight functions, ( 1 − ‖ x ‖ 2 ) μ − 1 / 2 . The relationship between orthogonal polynomials on the sphere and ball is exploited to achieve this result, which provides an improvement on known estimates of the Lebesgue constant for hyperinterpolation operators on B 2 .
Distributed Optimal Transport for the Deployment of Swarms

The analysis and design of scalable distributed algorithms for spatial deployment is an important problem in the area of multi-robot systems. For very large swarms, this can be prescribed via macroscopic objectives on the behavior of the swarm, and accomplished by local sensing and communication between agents. In this paper, we address the problem of distributed optimal transport, with the aim of minimizing the cost of deployment of large swarms. Working with a macroscopic PDE model of swarms given by the continuity equation, we first formulate a general deployment objective, and formulate deployment algorithms as convergent gradient flows. Then, we design and analyze a novel Laplacian-based distributed algorithm and a corresponding weighted gradient flow for optimal transport. We conclude the manuscript with simulations that illustrate our results.
The complex Lorentzian Leech lattice and the bimonster (II)

Let $D$ be the incidence graph of the projective plane over $\FF_3$. The Artin group of the graph $D$ maps onto the bimonster and a complex hyperbolic reflection group $\Gamma$ acting on 13 dimensional complex hyperbolic space $Y$. The generators of the Artin group are mapped to elements of order 2 (resp. 3) in the bimonster (resp. $\Gamma$). Let $Y^{\circ} \subseteq Y$ be the complement of the union of the mirrors of $\Gamma$. Daniel Allcock has conjectured that the orbifold fundamental group of $Y^{\circ}/\Gamma$ surjects onto bimonster. In this article we study the reflection group $\Gamma$. Our main result shows that there is homomorphism from the Artin group of $D$ to the orbifold fundamental group of $Y^{\circ}/\Gamma$, obtained by sending the Artin generators to the generators of monodromy around the mirrors of the generating reflections in $\Gamma$. This answers a question in Allcock's article "A monstrous proposal" and takes a step towards the proof of Allcock's conjecture. The finite group $\op{PGL}(3, \FF_3) \subseteq \Aut(D)$ acts on $Y$ and fixes a complex hyperbolic line pointwise. We show that the restriction of $\Gamma$-invariant meromorphic automorphic forms on $Y$ to the complex hyperbolic line fixed by $\op{PGL}(3, \FF_3)$ gives meromorphic modular forms of level 13.
Numerical triviality and pullbacks

Abstract Let f : X → Z be a surjective morphism of smooth complex projective varieties with connected fibers. Suppose that L is a pseudo-effective divisor that is f -numerically trivial. We show that there is a divisor D on Z such that L ≡ f ⁎ D .
How the Experts Do It: Assessing and Explaining Agent Behaviors in Real-Time Strategy Games

How should an AI-based explanation system explain an agent's complex behavior to ordinary end users who have no background in AI? Answering this question is an active research area, for if an AI-based explanation system could effectively explain intelligent agents' behavior, it could enable the end users to understand, assess, and appropriately trust (or distrust) the agents attempting to help them. To provide insights into this question, we turned to human expert explainers in the real-time strategy domain --"shoutcasters"-- to understand (1) how they foraged in an evolving strategy game in real time, (2) how they assessed the players' behaviors, and (3) how they constructed pertinent and timely explanations out of their insights and delivered them to their audience. The results provided insights into shoutcasters' foraging strategies for gleaning information necessary to assess and explain the players; a characterization of the types of implicit questions shoutcasters answered; and implications for creating explanations by using the patterns and abstraction levels these human experts revealed.
Robust Multilingual Part-of-Speech Tagging via Adversarial Training

Adversarial training (AT) is a powerful regularization method for neural networks, aiming to achieve robustness to input perturbations. Yet, the specific effects of the robustness obtained from AT are still unclear in the context of natural language processing. In this paper, we propose and analyze a neural POS tagging model that exploits AT. In our experiments on the Penn Treebank WSJ corpus and the Universal Dependencies (UD) dataset (27 languages), we find that AT not only improves the overall tagging accuracy, but also 1) prevents over-fitting well in low resource languages and 2) boosts tagging accuracy for rare / unseen words. We also demonstrate that 3) the improved tagging performance by AT contributes to the downstream task of dependency parsing, and that 4) AT helps the model to learn cleaner word representations. 5) The proposed AT model is generally effective in different sequence labeling tasks. These positive results motivate further use of AT for natural language tasks.
Constructing abstraction hierarchies using a skill-symbol loop

We describe a framework for building abstraction hierarchies whereby an agent alternates skill- and representation-construction phases to construct a sequence of increasingly abstract Markov decision processes. Our formulation builds on recent results showing that the appropriate abstract representation of a problem is specified by the agent's skills. We describe how such a hierarchy can be used for fast planning, and illustrate the construction of an appropriate hierarchy for the Taxi domain.
Imaginary Schur-Weyl duality

We study imaginary representations of the Khovanov-Lauda-Rouquier algebras of affine Lie type. Irreducible modules for such algebras arise as simple heads of standard modules. In order to define standard modules one needs to have a cuspidal system for a fixed convex preorder. A cuspidal system consists of irreducible cuspidal modules---one for each real positive root for the corresponding affine root system ${\tt X}_l^{(1)}$, as well as irreducible imaginary modules---one for each $l$-multipartition. We study imaginary modules by means of `imaginary Schur-Weyl duality'. We introduce an imaginary analogue of tensor space and the imaginary Schur algebra. We construct a projective generator for the imaginary Schur algebra, which yields a Morita equivalence between the imaginary and the classical Schur algebra. We construct imaginary analogues of Gelfand-Graev representations, Ringel duality and the Jacobi-Trudy formula.
Fully dynamic connectivity in O(log n(log log n)2) amortized expected time

Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a new randomized dynamic connectivity structure with O(log n(log log n)2) amortized expected update time and O(log n/log log log n) query time, which comes within an O((log log n)2) factor of a lower bound due to Pǎtrascu and Demaine. The new structure is based on a dynamic connectivity algorithm proposed by Thorup in an extended abstract at STOC 2000, which left out some important details.
Solutions of multi-component fractional symmetric systems

We study the following elliptic system concerning the fractional Laplacian operator $$\begin{aligned} (- \Delta )^ {s_i} u_i = H_i ( u_1,\ldots ,u_m) \quad \text {in}\ \ \mathbb {R}^n, \end{aligned}$$ when $$0<s_i<1$$ , $$u_i: {\mathbb {R}}^n\rightarrow {\mathbb {R}}$$ and $$H_i$$ belongs to $$C^{1,\gamma }(\mathbb {R}^m)$$ for $$\gamma > \max (0,1-2\min \left\{ s_i \right\} )$$ for $$1\le i \le m$$ . The above system is called symmetric when the matrix $${\mathbb {H}}=(\partial _j H_i(u_1,\ldots ,u_m))_{i,j=1}^m$$ is symmetric. The notion of symmetric systems seems crucial to study this system with a general nonlinearity $$H=(H_i)_{i=1}^m$$ . We establish De Giorgi type results for stable and H-monotone solutions of symmetric systems in lower dimensions that is either $$n=2$$ and $$0<s_i<1$$ or $$n=3$$ and $$1/2 \le \min \{s_i\}<1$$ . The case that $$n=3$$ and at least one of parameters $$s_i$$ belongs to (0, 1 / 2) remains open as well as the case $$n \ge 4$$ . Applying a geometric Poincare inequality, we conclude that gradients of components of solutions are parallel in lower dimensions when the system is coupled. More precisely, we show that the angle between vectors $$\nabla u_i$$ and $$\nabla u_j$$ is exactly $$\arccos \left( {|\partial _j H_i(u)|}/{\partial _j H_i(u)}\right) $$ . In addition, we provide Hamiltonian identities, monotonicity formulae and Liouville theorems. Lastly, we apply some of our main results to a two-component nonlinear Schrodinger system, that is a particular case of the above system, and we prove Liouville theorems and monotonicity formulae.
A variational analysis of stochastic gradient algorithms

Stochastic Gradient Descent (SGD) is an important algorithm in machine learning. With constant learning rates, it is a stochastic process that, after an initial phase of convergence, generates samples from a stationary distribution. We show that SGD with constant rates can be effectively used as an approximate posterior inference algorithm for probabilistic modeling. Specifically, we show how to adjust the tuning parameters of SGD such as to match the resulting stationary distribution to the posterior. This analysis rests on interpreting SGD as a continuoustime stochastic process and then minimizing the Kullback-Leibler divergence between its stationary distribution and the target posterior. (This is in the spirit of variational inference.) In more detail, we model SGD as a multivariate Ornstein-Uhlenbeck process and then use properties of this process to derive the optimal parameters. This theoretical framework also connects SGD to modern scalable inference algorithms; we analyze the recently proposed stochastic gradient Fisher scoring under this perspective. We demonstrate that SGD with properly chosen constant rates gives a new way to optimize hyperparameters in probabilistic models.
Non-Convex Matrix Completion Against a Semi-Random Adversary

Matrix completion is a well-studied problem with many machine learning applications. In practice, the problem is often solved by non-convex optimization algorithms. However, the current theoretical analysis for non-convex algorithms relies heavily on the assumption that every entry is observed with exactly the same probability $p$, which is not realistic in practice. In this paper, we investigate a more realistic semi-random model, where the probability of observing each entry is at least $p$. Even with this mild semi-random perturbation, we can construct counter-examples where existing non-convex algorithms get stuck in bad local optima. In light of the negative results, we propose a pre-processing step that tries to re-weight the semi-random input, so that it becomes "similar" to a random input. We give a nearly-linear time algorithm for this problem, and show that after our pre-processing, all the local minima of the non-convex objective can be used to approximately recover the underlying ground-truth matrix.
The cardinality of sumsets: different summands

Let $h$ be a positive integer and $A, B_1, B_2,\dots, B_h$ be finite sets in a commutative group. We bound $|A+B_1+...+B_h|$ from above in terms of $|A|, |A+B_1|,\dots,|A+B_h|$ and $h$. Extremal examples, which demonstrate that the bound is asymptotically sharp in all the parameters, are furthermore provided.
Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval

We develop procedures, based on minimization of the composition $f(x) = h(c(x))$ of a convex function $h$ and smooth function $c$, for solving random collections of quadratic equalities, applying our methodology to phase retrieval problems. We show that the prox-linear algorithm we develop can solve phase retrieval problems---even with adversarially faulty measurements---with high probability as soon as the number of measurements $m$ is a constant factor larger than the dimension $n$ of the signal to be recovered. The algorithm requires essentially no tuning---it consists of solving a sequence of convex problems---and it is implementable without any particular assumptions on the measurements taken. We provide substantial experiments investigating our methods, indicating the practical effectiveness of the procedures and showing that they succeed with high probability as soon as $m / n \ge 2$ when the signal is real-valued.
Large-scale Classification of Fine-Art Paintings: Learning The Right Metric on The Right Feature

In the past few years, the number of fine-art collections that are dig- itized and publicly available has been growing rapidly. With the availability of such large collections of digitized artworks comes the need to develop multime- dia systems to archive and retrieve this pool of data. Measuring the visual similar- ity between artistic items is an essential step for such multimedia systems, which can benefit more high-level multimedia tasks. In order to model this similarity between paintings, we should extract the appropriate visual features for paintings and find out the best approach to learn the similarity metric based on these fea- tures. We investigate a comprehensive list of visual features and metric learning approaches to learn an optimized similarity measure between paintings. We de- velop a machine that is able to make aesthetic-related semantic-level judgments, such as predicting a painting’s style, genre, and artist, as well as providing simi- larity measures optimized based on the knowledge available in the domain of art historical interpretation. Our experiments show the value of using this similarity measure for the aforementioned prediction tasks.
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems.

Some of the most fundamental and well-studied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a "center" node can reach all other nodes). The natural and important $ST$-variant considers two subsets $S$ and $T$ of the vertex set and lets the $ST$-diameter be the maximum distance between a node in $S$ and a node in $T$, and the $ST$-radius be the minimum distance for a node of $S$ to reach all nodes of $T$. The bichromatic variant is the special case in which $S$ and $T$ partition the vertex set. In this paper we present a comprehensive study of the approximability of $ST$ and Bichromatic Diameter, Radius, and Eccentricities, and variants, in graphs with and without directions and weights. We give the first nontrivial approximation algorithms for most of these problems, including time/accuracy trade-off upper and lower bounds. We show that nearly all of our obtained bounds are tight under the Strong Exponential Time Hypothesis (SETH), or the related Hitting Set Hypothesis. For instance, for Bichromatic Diameter in undirected weighted graphs with $m$ edges, we present an $\tilde{O}(m^{3/2})$ time $5/3$-approximation algorithm, and show that under SETH, neither the running time, nor the approximation factor can be significantly improved while keeping the other unchanged.
Quantification of thermally-driven flows in microsystems using Boltzmann equation in deterministic and stochastic contexts

When the flow is sufficiently rarefied, a temperature gradient, for example, between two walls separated by a few mean free paths, induces a gas flow—an observation attributed to the thermostress convection effects at the microscale. The dynamics of the overall thermostress convection process is governed by the Boltzmann equation—an integrodifferential equation describing the evolution of the molecular distribution function in six-dimensional phase space—which models dilute gas behavior at the molecular level to accurately describe a wide range of flow phenomena. Approaches for solving the full Boltzmann equation with general intermolecular interactions rely on two perspectives: one stochastic in nature often delegated to the direct simulation Monte Carlo (DSMC) method and the others deterministic by virtue. Among the deterministic approaches, the discontinuous Galerkin fast spectral (DGFS) method has been recently introduced for solving the full Boltzmann equation with general collision kernels, including the variable hard/soft sphere models—necessary for simulating flows involving diffusive transport. In this work, the deterministic DGFS method, Bhatnagar-Gross-Krook (BGK), Ellipsoidal statistical BGK (ESBGK), and Shakhov kinetic models, and the widely used stochastic DSMC method, are utilized to assess the thermostress convection process in micro in-plane Knudsen radiometric actuator—a microscale compact low-power pressure sensor utilizing the Knudsen forces. The BGK model underpredicts the heat-flux, shear-stress, and flow speed; the S-model overpredicts; whereas, ESBGK comes close to the DSMC results. On the other hand, both the statistical/DSMC and deterministic/DGFS methods, segregated in perspectives, yet, yield inextricable results, bespeaking the ingenuity of Graeme Bird who laid down the foundation of practical rarefied gas dynamics for microsystems.
Do immigrants import terrorism

Abstract The relationship between immigration and terrorism is an important public policy concern. Using bilateral migration data for 170 countries from 1990 to 2015, we estimate the relationship between levels of immigration and terrorism using an instrumental variables (IV) strategy based on the decades prior stocks of immigrants in destination countries. We specifically investigate rates of immigration from Muslim majority countries and countries involved in armed conflicts. We find no relationship between immigration and terrorism, whether measured by the number of attacks or victims, in destination countries.
A Game Theoretic Approach to Class-wise Selective Rationalization

Selection of input features such as relevant pieces of text has become a common technique of highlighting how complex neural predictors operate. The selection can be optimized post-hoc for trained models or incorporated directly into the method itself (self-explaining). However, an overall selection does not properly capture the multi-faceted nature of useful rationales such as pros and cons for decisions. To this end, we propose a new game theoretic approach to class-dependent rationalization, where the method is specifically trained to highlight evidence supporting alternative conclusions. Each class involves three players set up competitively to find evidence for factual and counterfactual scenarios. We show theoretically in a simplified scenario how the game drives the solution towards meaningful class-dependent rationales. We evaluate the method in single- and multi-aspect sentiment classification tasks and demonstrate that the proposed method is able to identify both factual (justifying the ground truth label) and counterfactual (countering the ground truth label) rationales consistent with human rationalization. The code for our method is publicly available.
Design of a 50MO Transimpedance Amplifier with 0.98fa/vHz Input Inferred Noise in a 0.18µM CMOS Technology

Low noise and low power consumption are key requirements for high performance electrochemical biosensors. Noise performance directly affects the sensorâs ability to detect small amounts of target chemical compounds. These requirements present challenges for the design of frontend circuitry in electrochemical biosensors. These challenges are especially apparent for integrated electrochemical biosensor arrays, as sensor size is limited by tissue cell size and the desire to achieve a cellular scale resolution. This paper presents a low-noise and low-power transimpedance amplifier (TIA) intended for (but not limited to) use as an analog frontend in an electrochemical biosensor. The amplifier was designed on a commercial 0.18µm CMOS process. The overall design achieves a 50Mâ¦ transimpedance gain with 981aA/âHz input inferred noise, 8.06µW power consumption at 0.9V power supply, and occupies an overall silicon area of 0.0074mm2. To our best knowledge, the design presented in this paper achieved the best noise performance and power consumption among transimpedance amplifier designs reported to date.
Input-Output Equivalence of Unitary and Contractive RNNs

Unitary recurrent neural networks (URNNs) have been proposed as a method to overcome the vanishing and exploding gradient problem in modeling data with long-term dependencies. A basic question is how restrictive is the unitary constraint on the possible input-output mappings of such a network? This works shows that for any contractive RNN with ReLU activations, there is a URNN with at most twice the number of hidden states and the identical input-output mapping. Hence, with ReLU activations, URNNs are as expressive as general RNNs. In contrast, for certain smooth activations, it is shown that the input-output mapping of an RNN cannot be matched with a URNN, even with an arbitrary number of states. The theoretical results are supported by experiments on modeling of slowly-varying dynamical systems.
Discovering human transcription factor physical interactions with genetic variants, novel DNA motifs, and repetitive elements using enhanced yeast one-hybrid assays

Identifying transcription factor (TF) binding to noncoding variants, uncharacterized DNA motifs, and repetitive genomic elements has been technically and computationally challenging. Current experimental methods, such as chromatin immunoprecipitation, generally test one TF at a time, and computational motif algorithms often lead to false-positive and -negative predictions. To address these limitations, we developed an experimental approach based on enhanced yeast one-hybrid assays. The first variation of this approach interrogates the binding of >1000 human TFs to repetitive DNA elements, while the second evaluates TF binding to single nucleotide variants, short insertions and deletions (indels), and novel DNA motifs. Using this approach, we detected the binding of 75 TFs, including several nuclear hormone receptors and ETS factors, to the highly repetitive Alu elements. Further, we identified cancer-associated changes in TF binding, including gain of interactions involving ETS TFs and loss of interactions involving KLF TFs to different mutations in the TERT promoter, and gain of a MYB interaction with an 18-bp indel in the TAL1 superenhancer. Additionally, we identified TFs that bind to three uncharacterized DNA motifs identified in DNase footprinting assays. We anticipate that these enhanced yeast one-hybrid approaches will expand our capabilities to study genetic variation and undercharacterized genomic regions.
Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications

Following the groundbreaking algorithm of Moser and Tardos for the Lovasz Local Lemma (LLL), there has been a plethora of results analyzing local search algorithms for various constraint satisfaction problems. The algorithms considered fall into two broad categories: resampling algorithms, analyzed via different algorithmic LLL conditions; and backtracking algorithms, analyzed via entropy compression arguments. This paper introduces a new convergence condition that seamlessly handles resampling, backtracking, and hybrid algorithms, i.e., algorithms that perform both resampling and backtracking steps. Unlike previous work on the LLL, our condition replaces the notion of a dependency or causality graph by quantifying point-to-set correlations between bad events. As a result, our condition simultaneously: (i) captures the most general algorithmic LLL condition known as a special case; (ii) significantly simplifies the analysis of entropy compression applications; (iii) relates backtracking algorithms, which are conceptually very different from resampling algorithms, to the LLL; and most importantly (iv) allows for the analysis of hybrid algorithms, which were outside the scope of previous techniques. We give several applications of our condition, including a new hybrid vertex coloring algorithm that extends the recent breakthrough result of Molloy for coloring triangle-free graphs to arbitrary graphs.
Uniqueness from locality and BCFW shifts

We introduce a BCFW shift that can be used to recursively build the full YangMills tree-level amplitude as a function of polarization vectors. Furthermore, in line with the recent results of [1], we conjecture that the Yang-Mills tree-level scattering amplitude is uniquely fixed by locality and demanding the usual asymptotic behavior under a sufficient number of shifts. Unitarity therefore emerges from locality and constructability. We prove this statement at the leading order in the soft expansion.
Safely Learning to Control the Constrained Linear Quadratic Regulator

We study the constrained linear quadratic regulator with unknown dynamics, addressing the tension between safety and exploration in data-driven control techniques. We present a framework which allows for system identification through persistent excitation, while maintaining safety by guaranteeing the satisfaction of state and input constraints. This framework involves a novel method for synthesizing robust constraint-satisfying feedback controllers, leveraging newly developed tools from system level synthesis. We connect statistical results with cost sub-optimality bounds to give non-asymptotic guarantees on both estimation and controller performance.
Tax avoidance and ex ante cost of capital

This study examines the association between tax avoidance and ex ante cost of equity capital. Based on prior research, we develop two proxies for investors’ expectations of tax avoidance and explore whether deviations from those expectations result in higher ex ante cost of equity capital. We find that the ex ante cost of equity capital increases with tax avoidance that is either below or above investor expectations and that the increase is larger for tax avoidance that exceeds investors’ expectations. We then examine whether firms that alter their future tax avoidance exhibit a lowering of their ex ante cost of equity capital and find that tax avoidance decreases (increases) from the prior year for firms that were above (below) investors’ expectations in the prior year. These results are consistent with the trade-off suggested by the Scholes and Wolfson framework and reinforce the notion that balancing tax benefits and non-tax costs is an important feature of firms’ tax planning.