OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Pricing (and Assortment) under a Static Calendar
Venue: arXiv cs.DS 2020
Year: 2020

This work is motivated by our collaboration with a large consumer packaged goods (CPG) company. We have found that while the company appreciates the advantages of dynamic pricing, they deem it operationally much easier to plan out a static price calendar in advance. We investigate the efficacy of static control policies for revenue management problems whose optimal solution is inherently dynamic. In these problems, a firm has limited inventory to sell over a finite time horizon, over which heterogeneous customers stochastically arrive. We consider both pricing and assortment controls, and derive simple static policies in the form of a price calendar or a planned sequence of assortments, respectively. In the assortment planning problem, we also differentiate between the static vs. dynamic substitution models of customer demand. We show that our policies are within 1-1/e (approximately 0.63) of the optimum under stationary (IID) demand, and 1/2 of the optimum under non-stationary demand, with both guarantees approaching 1 if the starting inventories are large. We adapt the technique of prophet inequalities from optimal stopping theory to pricing and assortment problems, and our results are relative to the linear programming relaxation. Under the special case of IID single-item pricing, our results improve the understanding of irregular and discrete demand curves, by showing that a static calendar can be (1-1/e)-approximate if the prices are sorted high-to-low. Finally, we demonstrate on both data from the CPG company and synthetic data from the literature that our simple price and assortment calendars are effective.
Greedy Frank-Wolfe Algorithm for Exemplar Selection
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we consider the problem of selecting representatives from a data set for arbitrary supervised/unsupervised learning tasks. We identify a subset $S$ of a data set $A$ such that 1) the size of $S$ is much smaller than $A$ and 2) $S$ efficiently describes the entire data set, in a way formalized via convex optimization. In order to generate $|S| = k$ exemplars, our kernelizable algorithm, Frank-Wolfe Sparse Representation (FWSR), only needs to execute $\approx k$ iterations with a per-iteration cost that is quadratic in the size of $A$. This is in contrast to other state of the art methods which need to execute until convergence with each iteration costing an extra factor of $d$ (dimension of the data). Moreover, we also provide a proof of linear convergence for our method. We support our results with empirical experiments; we test our algorithm against current methods in three different experimental setups on four different data sets. FWSR outperforms other exemplar finding methods both in speed and accuracy in almost all scenarios.
Differentiation and Passivity for Control of Brayton-Moser Systems
Venue: arXiv cs.SY 2020
Year: 2020

This paper deals with a class of Resistive-Inductive-Capacitive (RLC) circuits and switched RLC (s-RLC) circuits modeled in Brayton Moser framework. For this class of systems, new passivity properties using a Krasovskii's type Lyapunov function as storage function are presented. Consequently, the supply-rate is a function of the system states, inputs and their first time-derivatives. Moreover, after showing the integrability property of the port-variables, two simple control methodologies called output shaping and input shaping are proposed for regulating the voltage in RLC and s-RLC circuits. Global asymptotic convergence to the desired operating point is theoretically proved for both proposed control methodologies. Moreover, robustness with respect to load uncertainty is ensured by the input shaping methodology. The applicability of the proposed methodologies is illustrated by designing voltage controllers for DC-DC converters and DC networks.
Towards a Near Universal Time Series Data Mining Tool: Introducing the Matrix Profile
Venue: arXiv cs.LG 2020
Year: 2020

The last decade has seen a flurry of research on all-pairs-similarity-search (or, self-join) for text, DNA, and a handful of other datatypes, and these systems have been applied to many diverse data mining problems. Surprisingly, however, little progress has been made on addressing this problem for time series subsequences. In this thesis, we have introduced a near universal time series data mining tool called matrix profile which solves the all-pairs-similarity-search problem and caches the output in an easy-to-access fashion. The proposed algorithm is not only parameter-free, exact and scalable, but also applicable for both single and multidimensional time series. By building time series data mining methods on top of matrix profile, many time series data mining tasks (e.g., motif discovery, discord discovery, shapelet discovery, semantic segmentation, and clustering) can be efficiently solved. Because the same matrix profile can be shared by a diverse set of time series data mining methods, matrix profile is versatile and computed-once-use-many-times data structure. We demonstrate the utility of matrix profile for many time series data mining problems, including motif discovery, discord discovery, weakly labeled time series classification, and representation learning on domains as diverse as seismology, entomology, music processing, bioinformatics, human activity monitoring, electrical power-demand monitoring, and medicine. We hope the matrix profile is not the end but the beginning of many more time series data mining projects.
Distribution-Preserving Steganography Based on Text-to-Speech Generative Models
Venue: arXiv cs.MM 2020
Year: 2020

Steganography is the art and science of hiding secret messages in public communication so that the presence of the secret messages cannot be detected. There are two distribution-preserving steganographic frameworks, one is sampling-based and the other is compression-based. The former requires a perfect sampler which yields data following the same distribution, and the latter needs explicit distribution of generative objects. However, these two conditions are too strict even unrealistic in the traditional data environment, e.g. the distribution of natural images is hard to seize. Fortunately, generative models bring new vitality to distribution-preserving steganography, which can serve as the perfect sampler or provide the explicit distribution of generative media. Take text-to-speech generation task as an example, we propose distribution-preserving steganography based on WaveGlow and WaveNet, which corresponds to the former two categories. Steganalysis experiments and theoretical analysis are conducted to demonstrate that the proposed methods can preserve the distribution.
ITE: A Lightweight Implementation of Stratified Reasoning for Constructive Logical Operators
Venue: arXiv cs.AI 2020
Year: 2020

Constraint Programming (CP) is a powerful declarative programming paradigm where inference and search are interleaved to find feasible and optimal solutions to various type of constraint systems. However, handling logical connectors with constructive information in CP is notoriously difficult. This paper presents If Then Else (ITE), a lightweight implementation of stratified constructive reasoning for logical connectives. Stratification is introduced to cope with the risk of combinatorial explosion of constructing information from nested and combined logical operators. ITE is an open-source library built on top of SICStus Prolog clp(fd), which proposes various operators, including constructive disjunction and negation, constructive implication and conditional. These operators can be used to express global constraints and to benefit from constructive reasoning for more domain pruning during constraint filtering. Even though ITE is not competitive with specialized filtering algorithms available in some global constraints implementations, its expressiveness allows users to easily define well-tuned constraints with powerful deduction capabilities. Our extended experimental results show that ITE is more efficient than available generic approaches that handle logical constraint systems over finite domains.
Policy Regret in Repeated Games
Venue: arXiv cs.LG 2020
Year: 2020

The notion of \emph{policy regret} in online learning is a well defined? performance measure for the common scenario of adaptive adversaries, which more traditional quantities such as external regret do not take into account. We revisit the notion of policy regret and first show that there are online learning settings in which policy regret and external regret are incompatible: any sequence of play that achieves a favorable regret with respect to one definition must do poorly with respect to the other. We then focus on the game-theoretic setting where the adversary is a self-interested agent. In that setting, we show that external regret and policy regret are not in conflict and, in fact, that a wide class of algorithms can ensure a favorable regret with respect to both definitions, so long as the adversary is also using such an algorithm. We also show that the sequence of play of no-policy regret algorithms converges to a \emph{policy equilibrium}, a new notion of equilibrium that we introduce. Relating this back to external regret, we show that coarse correlated equilibria, which no-external regret players converge to, are a strict subset of policy equilibria. Thus, in game-theoretic settings, every sequence of play with no external regret also admits no policy regret, but the converse does not hold.
Formal Limitations on the Measurement of Mutual Information
Venue: arXiv cs.IT 2020
Year: 2020

Measuring mutual information from finite data is difficult. Recent work has considered variational methods maximizing a lower bound. In this paper, we prove that serious statistical limitations are inherent to any method of measuring mutual information. More specifically, we show that any distribution-free high-confidence lower bound on mutual information estimated from N samples cannot be larger than O(ln N ).
Relating complexities for the reflexive study of complex systems
Venue: arXiv cs.CY 2020
Year: 2020

Several approaches and corresponding definitions of complexity have been developed in different fields. Urban systems are the archetype of complex socio-technical systems concerned with these different viewpoints. We suggest in this chapter some links between three types of complexity, namely emergence, computational complexity and informational complexity. We discuss the implication of these links on the necessity of reflexivity to produce a knowledge of the complex, and how this connects to the interdisciplinary of approaches in particular for socio-technical systems. We finally synthesize this positioning as a proposal of an epistemological framework called applied perspectivism, and discuss the implications for the study of urban systems.
An initial attempt of combining visual selective attention with deep reinforcement learning
Venue: arXiv cs.LG 2020
Year: 2020

Visual attention serves as a means of feature selection mechanism in the perceptual system. Motivated by Broadbent's leaky filter model of selective attention, we evaluate how such mechanism could be implemented and affect the learning process of deep reinforcement learning. We visualize and analyze the feature maps of DQN on a toy problem Catch, and propose an approach to combine visual selective attention with deep reinforcement learning. We experiment with optical flow-based attention and A2C on Atari games. Experiment results show that visual selective attention could lead to improvements in terms of sample efficiency on tested games. An intriguing relation between attention and batch normalization is also discovered.
Programs as the Language of Science
Venue: arXiv cs.LO 2020
Year: 2020

Currently it is widely accepted that the language of science is mathematics. This book explores an alternative idea where the future of science is based on the language of algorithms and programs. How such a language can actually be implemented in the sciences is outlined in some detail. We start by constructing a simple formal system where statements are represented as programs and inference is based on computability as opposed to the classical notion of truth value assignments. The focus is on theories where the intrinsic properties and dynamic state of real world objects can be defined in terms of information and subject to laws based on simple deterministic rules and finite state arithmetic. Such models, it is argued, not only offer alternative simulation tools, as opposed to those based on discrete approximations of conventional continuum theories, but in themselves can be regarded as a language that describes the physical laws at a fundamental level. This book does not examine any specific application in detail but rather attempts to lay down a foundation for the validation of such theories by employing the inference scheme based on computability logic.
Distortion Robust Image Classification using Deep Convolutional Neural Network with Discrete Cosine Transform
Venue: arXiv cs.CV 2020
Year: 2020

Convolutional Neural Network is good at image classification. However, it is found to be vulnerable to image quality degradation. Even a small amount of distortion such as noise or blur can severely hamper the performance of these CNN architectures. Most of the work in the literature strives to mitigate this problem simply by fine-tuning a pre-trained CNN on mutually exclusive or a union set of distorted training data. This iterative fine-tuning process with all known types of distortion is exhaustive and the network struggles to handle unseen distortions. In this work, we propose distortion robust DCT-Net, a Discrete Cosine Transform based module integrated into a deep network which is built on top of VGG16. Unlike other works in the literature, DCT-Net is "blind" to the distortion type and level in an image both during training and testing. As a part of the training process, the proposed DCT module discards input information which mostly represents the contribution of high frequencies. The DCT-Net is trained "blindly" only once and applied in generic situation without further retraining. We also extend the idea of traditional dropout and present a training adaptive version of the same. We evaluate our proposed method against Gaussian blur, motion blur, salt and pepper noise, Gaussian noise and speckle noise added to CIFAR-10/100 and ImageNet test sets. Experimental results demonstrate that once trained, DCT-Net not only generalizes well to a variety of unseen image distortions but also outperforms other methods in the literature.
Advice Complexity of Treasure Hunt in Geometric Terrains
Venue: arXiv cs.CG 2020
Year: 2020

Treasure hunt is the task of finding an inert target by a mobile agent in an unknown environment. We consider treasure hunt in geometric terrains with obstacles. Both the terrain and the obstacles are modeled as polygons and both the agent and the treasure are modeled as points. The agent navigates in the terrain, avoiding obstacles, and finds the treasure when there is a segment of length at most 1 between them, unobstructed by the boundary of the terrain or by the obstacles. The cost of finding the treasure is the length of the trajectory of the agent. We investigate the amount of information that the agent needs a priori in order to find the treasure at cost $O(L)$, where $L$ is the length of the shortest path in the terrain from the initial position of the agent to the treasure, avoiding obstacles. Following the paradigm of algorithms with advice, this information is given to the agent in advance as a binary string, by an oracle cooperating with the agent and knowing the whole environment: the terrain, the position of the treasure and the initial position of the agent. Advice complexity of treasure hunt is the minimum length of the advice string (up to multiplicative constants) that enables the agent to find the treasure at cost $O(L)$. We first consider treasure hunt in regular terrains which are defined as convex polygons with convex $c$-fat obstacles, for some constant $c>1$. A polygon is $c$-fat if the ratio of the radius of the smallest disc containing it to the radius of the largest disc contained in it is at most $c$. For the class of regular terrains, we establish the exact advice complexity of treasure hunt. We then show that advice complexity of treasure hunt for the class of arbitrary terrains (even for non-convex polygons without obstacles, and even for those with only horizontal or vertical sides) is exponentially larger than for regular terrains.
A Spanner for the Day After
Venue: arXiv cs.CG 2020
Year: 2020

We show how to construct $(1+\varepsilon)$-spanner over a set $P$ of $n$ points in $\mathbb{R}^d$ that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters $\vartheta,\varepsilon \in (0,1)$, the computed spanner $G$ has $ O\bigl(\varepsilon^{-c} \vartheta^{-6} n \log n (\log\log n)^6 \bigr) $ edges, where $c= O(d)$. Furthermore, for any $k$, and any deleted set $B \subseteq P$ of $k$ points, the residual graph $G \setminus B$ is $(1+\varepsilon)$-spanner for all the points of $P$ except for $(1+\vartheta)k$ of them. No previous constructions, beyond the trivial clique with $O(n^2)$ edges, were known such that only a tiny additional fraction (i.e., $\vartheta$) lose their distance preserving connectivity. Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one-dimensional construction in a black box fashion.
PointConv: Deep Convolutional Networks on 3D Point Clouds
Venue: arXiv cs.CV 2020
Year: 2020

Unlike images which are represented in regular dense grids, 3D point clouds are irregular and unordered, hence applying convolution on them can be difficult. In this paper, we extend the dynamic filter to a new convolution operation, named PointConv. PointConv can be applied on point clouds to build deep convolutional networks. We treat convolution kernels as nonlinear functions of the local coordinates of 3D points comprised of weight and density functions. With respect to a given point, the weight functions are learned with multi-layer perceptron networks and density functions through kernel density estimation. The most important contribution of this work is a novel reformulation proposed for efficiently computing the weight functions, which allowed us to dramatically scale up the network and significantly improve its performance. The learned convolution kernel can be used to compute translation-invariant and permutation-invariant convolution on any point set in the 3D space. Besides, PointConv can also be used as deconvolution operators to propagate features from a subsampled point cloud back to its original resolution. Experiments on ModelNet40, ShapeNet, and ScanNet show that deep convolutional neural networks built on PointConv are able to achieve state-of-the-art on challenging semantic segmentation benchmarks on 3D point clouds. Besides, our experiments converting CIFAR-10 into a point cloud showed that networks built on PointConv can match the performance of convolutional networks in 2D images of a similar structure.
Taming the latency in multi-user VR 360$^\circ$: A QoE-aware deep learning-aided multicast framework
Venue: arXiv cs.IT 2020
Year: 2020

Immersive virtual reality (VR) applications require ultra-high data rate and low-latency for smooth operation. Hence in this paper, aiming to improve VR experience in multi-user VR wireless video streaming, a deep-learning aided scheme for maximizing the quality of the delivered video chunks with low-latency is proposed. Therein the correlations in the predicted field of view (FoV) and locations of viewers watching 360$^\circ$ HD VR videos are capitalized on to realize a proactive FoV-centric millimeter wave (mmWave) physical-layer multicast transmission. The problem is cast as a frame quality maximization problem subject to tight latency constraints and network stability. The problem is then decoupled into an HD frame request admission and scheduling subproblems and a matching theory game is formulated to solve the scheduling subproblem by associating requests from clusters of users to mmWave small cell base stations (SBSs) for their unicast/multicast transmission. Furthermore, for realistic modeling and simulation purposes, a real VR head-tracking dataset and a deep recurrent neural network (DRNN) based on gated recurrent units (GRUs) are leveraged. Extensive simulation results show how the content-reuse for clusters of users with highly overlapping FoVs brought in by multicasting reduces the VR frame delay in 12\%. This reduction is further boosted by proactiveness that cuts by half the average delays of both reactive unicast and multicast baselines while preserving HD delivery rates above 98\%. Finally, enforcing tight latency bounds shortens the delay-tail as evinced by 13\% lower delays in the 99th percentile.
Contextual and Granular Policy Enforcement in Database-backed Applications
Venue: arXiv cs.CR 2020
Year: 2020

Database-backed applications rely on inlined policy checks to process users' private and confidential data in a policy-compliant manner as traditional database access control mechanisms cannot enforce complex policies. However, application bugs due to missed checks are common in such applications, which result in data breaches. While separating policy from code is a natural solution, many data protection policies specify restrictions based on the context in which data is accessed and how the data is used. Enforcing these restrictions automatically presents significant challenges, as the information needed to determine context requires a tight coupling between policy enforcement and an application's implementation. We present Estrela, a framework for enforcing contextual and granular data access policies. Working from the observation that API endpoints can be associated with salient contextual information in most database-backed applications, Estrela allows developers to specify API-specific restrictions on data access and use. Estrela provides a clean separation between policy specification and the application's implementation, which facilitates easier auditing and maintenance of policies. Policies in Estrela consist of pre-evaluation and post-evaluation conditions, which provide the means to modulate database access before a query is issued, and to impose finer-grained constraints on information release after the evaluation of query, respectively. We build a prototype of Estrela and apply it to retrofit several real world applications (from 1000-80k LOC) to enforce different contextual policies. Our evaluation shows that Estrela can enforce policies with minimal overheads.