Pricing Identical Items

Social goods are goods that grant value not only to their owners but also to the owners’ surroundings, be it their families, friends or office mates. The benefit a non-owner derives from the good is affected by many factors, including the type of the good, its availability, and the social status of the non-owner. Depending on the magnitude of the benefit and on the price of the good, a potential buyer might stay away from purchasing the good, hoping to free ride on others’ purchases. A revenue-maximizing seller who sells social goods must take these considerations into account when setting prices for the good. The literature on optimal pricing has advanced considerably over the last decade, but little is known about optimal pricing schemes for selling social goods. In this paper, we conduct a systematic study of revenue-maximizing pricing schemes for social goods: we introduce a Bayesian model for this scenario, and devise nearly-optimal pricing schemes for various types of externalities, both for simultaneous sales and for sequential sales.

On the Solution of Linear Programming Problems in the Age of Big Data

The Big Data phenomenon has spawned large-scale linear programming problems. In many cases, these problems are non-stationary. In this paper, we describe a new scalable algorithm called NSLP for solving high-dimensional, non-stationary linear programming problems on modern cluster computing systems. The algorithm consists of two phases: Quest and Targeting. The Quest phase calculates a solution of the system of inequalities defining the constraint system of the linear programming problem under the condition of dynamic changes in input data. To this end, the apparatus of Fejer mappings is used. The Targeting phase forms a special system of points having the shape of an n-dimensional axisymmetric cross. The cross moves in the n-dimensional space in such a way that the solution of the linear programming problem is located all the time in an ‘-vicinity of the central point of the cross.

Persistence Diagrams with Linear Machine Learning Models

Persistence diagrams have been widely recognized as a compact descriptor for characterizing multiscale topological features in data. When many datasets are available, statistical features embedded in those persistence diagrams can be extracted by applying machine learnings. In particular, the ability for explicitly analyzing the inverse in the original data space from those statistical features of persistence diagrams is significantly important for practical applications. In this paper, we propose a unified method for the inverse analysis by combining linear machine learning models with persistence images. The method is applied to point clouds and cubical sets, showing the ability of the statistical inverse analysis and its advantages.

Restricted Causal Inference Algorithm

This paper proposes a new algorithm for recovery of belief network structure from data handling hidden variables. It consists essentially in an extension of the CI algorithm of Spirtes et al. by restricting the number of conditional dependencies checked up to k variables and in an extension of the original CI by additional steps transforming so called partial including path graph into a belief network. Its correctness is demonstrated.

Lasso Meets Horseshoe

The goal of our paper is to survey and contrast the major advances in two of the most commonly used high-dimensional techniques, namely, the Lasso and horseshoe regularization methodologies. Lasso is a gold standard for best subset selection of predictors while the horseshoe is a state-of-the-art Bayesian estimator for sparse signals. Lasso is scalable and fast using convex optimization whilst the horseshoe is a non-convex penalty. Our novel perspective focuses on three aspects, (i) efficiency and scalability of computation and (ii) methodological development and performance and (iii) theoretical optimality in high dimensional inference for the Gaussian sparse model and beyond.

RE-PACRR: A Context and Density-Aware Neural Information Retrieval Model

Ad-hoc retrieval models can benefit from considering different patterns in the interactions between a query and a document, effectively assessing the relevance of a document for a given user query. Factors to be considered in this interaction include (i) the matching of unigrams and ngrams, (ii) the proximity of the matched query terms, (iii) their position in the document, and (iv) how the different relevance signals are combined over different query terms. While previous work has successfully modeled some of these factors, not all aspects have been fully explored. In this work, we close this gap by proposing different neural components and incorporating them into a single architecture, leading to a novel neural IR model called RE-PACRR. Extensive comparisons with established models on TREC Web Track data confirm that the proposed model yields promising search results.

Rule-Mining based classification: a benchmark study

This study proposed an exhaustive stable/reproducible rule-mining algorithm combined to a classifier to generate both accurate and interpretable models. Our method first extracts rules (i.e., a conjunction of conditions about the values of a small number of input features) with our exhaustive rule-mining algorithm, then constructs a new feature space based on the most relevant rules called ‘local features’ and finally, builds a local predictive model by training a standard classifier on the new local feature space. This local feature space is easy interpretable by providing a human-understandable explanation under the explicit form of rules. Furthermore, our local predictive approach is as powerful as global classical ones like logistic regression (LR), support vector machine (SVM) and rules based methods like random forest (RF) and gradient boosted tree (GBT).

Optimization Methods for Supervised Machine Learning: From Linear Models to Deep Learning

The goal of this tutorial is to introduce key models, algorithms, and open questions related to the use of optimization methods for solving problems arising in machine learning. It is written with an INFORMS audience in mind, specifically those readers who are familiar with the basics of optimization algorithms, but less familiar with machine learning. We begin by deriving a formulation of a supervised learning problem and show how it leads to various optimization problems, depending on the context and underlying assumptions. We then discuss some of the distinctive features of these optimization problems, focusing on the examples of logistic regression and the training of deep neural networks. The latter half of the tutorial focuses on optimization algorithms, first for convex logistic regression, for which we discuss the use of first-order methods, the stochastic gradient method, variance reducing stochastic methods, and second-order methods. Finally, we discuss how these approaches can be employed to the training of deep neural networks, emphasizing the difficulties that arise from the complex, nonconvex structure of these models.

On Fairness, Diversity and Randomness in Algorithmic Decision Making

Consider a binary decision making process where a single machine learning classifier replaces a multitude of humans. We raise questions about the resulting loss of diversity in the decision making process. We study the potential benefits of using random classifier ensembles instead of a single classifier in the context of fairness-aware learning and demonstrate various attractive properties: (i) an ensemble of fair classifiers is guaranteed to be fair, for several different measures of fairness, (ii) an ensemble of unfair classifiers can still achieve fair outcomes, and (iii) an ensemble of classifiers can achieve better accuracy-fairness trade-offs than a single classifier. Finally, we introduce notions of distributional fairness to characterize further potential benefits of random classifier ensembles.

Probabilistic Active Learning of Functions in Structural Causal Models

We consider the problem of learning the functions computing children from parents in a Structural Causal Model once the underlying causal graph has been identified. This is in some sense the second step after causal discovery. Taking a probabilistic approach to estimating these functions, we derive a natural myopic active learning scheme that identifies the intervention which is optimally informative about all of the unknown functions jointly, given previously observed data. We test the derived algorithms on simple examples, to demonstrate that they produce a structured exploration policy that significantly improves on unstructured base-lines.

Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes

It is widely observed that deep learning models with learned parameters generalize well, even with much more model parameters than the number of training samples. We systematically investigate the underlying reasons why deep neural networks often generalize well, and reveal the difference between the minima (with the same training error) that generalize well and those they don’t. We show that it is the characteristics the landscape of the loss function that explains the good generalization capability. For the landscape of loss function for deep networks, the volume of basin of attraction of good minima dominates over that of poor minima, which guarantees optimization methods with random initialization to converge to good minima. We theoretically justify our findings through analyzing 2-layer neural networks; and show that the low-complexity solutions have a small norm of Hessian matrix with respect to model parameters. For deeper networks, extensive numerical evidence helps to support our arguments.

Bolt: Accelerated Data Mining with Fast Vector Compression

Vectors of data are at the heart of machine learning and data mining. Recently, vector quantization methods have shown great promise in reducing both the time and space costs of operating on vectors. We introduce a vector quantization algorithm that can compress vectors over 12x faster than existing techniques while also accelerating approximate vector operations such as distance and dot product computations by up to 10x. Because it can encode over 2GB of vectors per second, it makes vector quantization cheap enough to employ in many more circumstances. For example, using our technique to compute approximate dot products in a nested loop can multiply matrices faster than a state-of-the-art BLAS implementation, even when our algorithm must first compress the matrices. In addition to showing the above speedups, we demonstrate that our approach can accelerate nearest neighbor search and maximum inner product search by over 100x compared to floating point operations and up to 10x compared to other vector quantization methods. Our approximate Euclidean distance and dot product computations are not only faster than those of related algorithms with slower encodings, but also faster than Hamming distance computations, which have direct hardware support on the tested platforms. We also assess the errors of our algorithm’s approximate distances and dot products, and find that it is competitive with existing, slower vector quantization algorithms.

Noisy Networks for Exploration

We introduce NoisyNet, a deep reinforcement learning agent with parametric noise added to its weights, and show that the induced stochasticity of the agent’s policy can be used to aid efficient exploration. The parameters of the noise are learned with gradient descent along with the remaining network weights. NoisyNet is straightforward to implement and adds little computational overhead. We find that replacing the conventional exploration heuristics for A3C, DQN and dueling agents (entropy reward and \epsilon-greedy respectively) with NoisyNet yields substantially higher scores for a wide range of Atari games, in some cases advancing the agent from sub to super-human performance.

Diffusion Approximations for Load Balancing Mechanisms in Cloud Storage Systems
Graph Convolutional Networks for Molecules
User Activity Detection in Massive Random Access: Compressed Sensing vs. Coded Slotted ALOHA
Positroids Induced by Rational Dyck Paths
Deep factorisation of the stable process III: Radial excursion theory and the point of closest reach
Irregular Repetition Slotted ALOHA over the Rayleigh Block Fading Channel with Capture
A Pseudo-Bayesian Approach to Sign-Compute-Resolve Slotted ALOHA
Scalable Asymptotically-Optimal Multi-Robot Motion Planning
Robust Detection in Leak-Prone Population Protocols
Community Detection on Euclidean Random Graphs
Minimizing Data Distortion of Periodically Reporting IoT Devices with Energy Harvesting
Reliable and Efficient Access for Alarm-initiated and Regular M2M Traffic in IEEE 802.11ah Systems
Zero temperature limit for directed polymers and inviscid limit for stationary solutions of stochastic Burgers equation
A randomized Milstein method for stochastic differential equations with non-differentiable drift coefficients
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching
A crystal-like structure on shifted tableaux
The trivial lower bound for the girth of $S_n$
Towards Bursting Filter Bubble via Contextual Risks and Uncertainties
Phase Retrieval via Randomized Kaczmarz: Theoretical Guarantees
Stochastic Dynamic Optimal Power Flow in Distribution Network with Distributed Renewable Energy and Battery Energy Storage
Canonical form of linear subspaces and coding invariants: the poset metric point of view
Tight Load Balancing via Randomized Local Search
Hypothesis Testing For Densities and High-Dimensional Multinomials: Sharp Local Minimax Rates
Automated Audio Captioning with Recurrent Neural Networks
Fine-Grained Reliability for V2V Communications around Suburban and Urban Intersections
Improvement of training set structure in fusion data cleaning using Time-Domain Global Similarity method
Schubert puzzles and integrability I: invariant trilinear forms
Preference-based performance measures for Time$-$Domain Global Similarity method
$\mathcal{P}$-schemes and Deterministic Polynomial Factoring over Finite Fields
Collaborative-controlled LASSO for Constructing Propensity Score-based Estimators in High-Dimensional Data
Neural Sequence Model Training via $α$-divergence Minimization
Providing Effective Real-time Feedback in Simulation-based Surgical Training
Hamiltonicity is Hard in Thin or Polygonal Grid Graphs, but Easy in Thin Polygonal Grid Graphs
Power domination in maximal planar graphs
On the honeycomb conjecture for Robin Laplacian eigenvalues
A Deep Reinforcement Learning Framework for the Financial Portfolio Management Problem
Compaction of Church Numerals for Higher-Order Compression
Barankin Vector Locally Best Unbiased Estimates
Optimal High-Dimensional Shrinkage Covariance Estimation for Elliptical Distributions, a platform for creation, publication and distribution of semantic annotations
Superpixel-based semantic segmentation trained by statistical process control
Chatbots as Conversational Recommender Systems in Urban Contexts
Tuning and optimization for a variety of many-core architectures without changing a single line of implementation code using the Alpaka library
Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing
Noisy Hamiltonian Monte Carlo for doubly-intractable distributions
From Big Data to Big Displays: High-Performance Visualization at Blue Brain
Tableaux for Policy Synthesis for MDPs with PCTL* Constraints
On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms
On the Complexity of Polytopes in $LI(2)$
Semi-implicit Euler-Maruyama approximation for non-colliding particle systems
Inconsistency of Template Estimation by Minimizing of the Variance/Pre-Variance in the Quotient Space
A comment on Intersecting Families of Permutations
A ROS multi-ontology references services: OWL reasoners and application prototyping issues
Parameterized Complexity of CSP for Infinite Constraint Languages
Breaking ties in collective decision making
Prepaid or Postpaid? That is the question. Novel Methods of Subscription Type Prediction in Mobile Phone Services
Statistical Analysis of Dice CAPTCHA Usability
Regret-based Selection for Sparse Dynamic Portfolios
Computational aspects of robust optimized certainty equivalents
A reliability-based approach for influence maximization using the evidence theory
New Integer Linear Programming Models for the Vertex Coloring Problem
More Turán-Type Theorems for Triangles in Convex Point Sets
Agglomerative Clustering of Growing Squares
Modern Random Access for Satellite Communications
Selfish Network Creation with Non-Uniform Edge Cost
How noise determines the statistics of simple path dependent systems
Joint Optimization of User Association, Data Delivery Rate and Precoding for Cache-Enabled F-RANs
Sums of Palindromes: an Approach via Nested-Word Automata
Storage, Communication, and Load Balancing Trade-off in Distributed Cache Networks
SMC Faster R-CNN: Toward a scene-specialized multi-object detector
Contracting a Planar Graph Efficiently
Improving Session Recommendation with Recurrent Neural Networks by Exploiting Dwell Time
Bridging the Gap between Probabilistic and Deterministic Models: A Simulation Study on a Variational Bayes Predictive Coding Recurrent Neural Network Model
A selectional auto-encoder approach for document image binarization
Higher Order Turán Inequalities for the Partition Function
Stein’s method for normal approximation of linear statistics of beta-ensembles
Line Hermitian Grassmann Codes and their Parameters
A faster dual algorithm for the Euclidean minimum covering ball problem
How biased is your model? Concentration Inequalities, Information and Model Bias
Color-opponent mechanisms for local hue encoding in a hierarchical framework
SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud
A formalization of convex polyhedra based on the simplex method
Lifelong Learning in Costly Feature Spaces
Nuclear penalized multinomial regression with an application to predicting at bat outcomes in baseball
Community Detection by $L_0$-penalized Graph Laplacian
Signal Reconstruction from Interferometric Measurements under Sensing Constraints
Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees
Convergence of the randomized Kaczmarz method for phase retrieval