A Theoretical Analysis of Two-Stage Recommendation for Cold-Start Collaborative Filtering

In this paper, we present a theoretical framework for tackling the cold-start collaborative filtering problem, where unknown targets (items or users) keep coming to the system, and there is a limited number of resources (users or items) that can be allocated and related to them. The solution requires a trade-off between exploitation and exploration as with the limited recommendation opportunities, we need to, on one hand, allocate the most relevant resources right away, but, on the other hand, it is also necessary to allocate resources that are useful for learning the target’s properties in order to recommend more relevant ones in the future. In this paper, we study a simple two-stage recommendation combining a sequential and a batch solution together. We first model the problem with the partially observable Markov decision process (POMDP) and provide an exact solution. Then, through an in-depth analysis over the POMDP value iteration solution, we identify that an exact solution can be abstracted as selecting resources that are not only highly relevant to the target according to the initial-stage information, but also highly correlated, either positively or negatively, with other potential resources for the next stage. With this finding, we propose an approximate solution to ease the intractability of the exact solution. Our initial results on synthetic data and the Movie Lens 100K dataset confirm the performance gains of our theoretical development and analysis.


Top-N Recommender System via Matrix Completion

Top-N recommender systems have been investigated widely both in industry and academia. However, the recommendation quality is far from satisfactory. In this paper, we propose a simple yet promising algorithm. We fill the user-item matrix based on a low-rank assumption and simultaneously keep the original information. To do that, a nonconvex rank relaxation rather than the nuclear norm is adopted to provide a better rank approximation and an efficient optimization strategy is designed. A comprehensive set of experiments on real datasets demonstrates that our method pushes the accuracy of Top-N recommendation to a new level.


Understanding Deep Convolutional Networks

Deep convolutional networks provide state of the art classifications and regressions results over many high-dimensional problems. We review their architecture, which scatters data with a cascade of linear filter weights and non-linearities. A mathematical framework is introduced to analyze their properties. Computations of invariants involve multiscale contractions, the linearization of hierarchical symmetries, and sparse separations. Applications are discussed.


Schur properties of convolutions of gamma random variables

A Consistent Direct Method for Estimating Parameters in Ordinary Differential Equations Models

Sub-Sampled Newton Methods I: Globally Convergent Algorithms

Sub-Sampled Newton Methods II: Local Convergence Rates

On the spectral distributions of distance-k graph of free product graphs

A Diabetes minimal model for Oral Glucose Tolerance Tests

Improved Sampling Techniques for Learning an Imbalanced Data Set

Banach spaces characterization of random vectors with exponential decreasing tails of distribution

Probabilistic evaluation of low-quality DNA profiles

Adaptive Image Denoising by Mixture Adaptation

Recursive Distributed Detection for Composite Hypothesis Testing: Algorithms and Asymptotics

New congruences involving products of two binomial coefficients

Phases in Large Combinatorial Systems

Separating hash families: A Johnson-type bound and new constructions

Continuous-state branching processes in Levy random environments

Coverage-based Neural Machine Translation

Streaming Similarity Self-Join

Time-Efficient Read/Write Register in Crash-prone Asynchronous Message-Passing Systems

A continuous updating weighted least squares estimator of tail dependence in high dimensions

On formal inverse of the Prouhet-Thue-Morse sequence

Vital variables and survival processes

Real zeroes of random polynomials, I: Flip-invariance, Turán’s lemma, and the Newton-Hadamard polygon

Bounds on the Game Transversal Number in Hypergraphs

Real zeroes of random polynomials, II: Descartes’ rule of signs and anti-concentration on the symmetric group

Scalability in Neural Control of Musculoskeletal Robots

Mixture model with multiple allocations for clustering spatially correlated observations in the analysis of ChIP-Seq data

Algebraic Structures and Stochastic Differential Equations driven by Levy processes

Stochastic control, entropic interpolation and gradient flows on Wasserstein product spaces

Sunflowers and $L$-intersecting families

Graded Entailment for Compositional Distributional Semantics

Distribution of joint local and total size and of extension for avalanches in the Brownian force model

Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints

On the capacity functional of the infinite cluster of a Boolean model

Nonbinary tree-based phylogenetic networks

Tight Bounds for Consensus Systems Convergence

Unimodality via alternating gamma vectors

A new result in combinatorial number theory

Parameterized and approximation complexity of the detection pair problem in graphs

Variable projection without smoothness

Cohen-Macaulayness of triangular graphs

Low Space External Memory Construction of the Succinct Permuted Longest Common Prefix Array

Optimal tracking for dynamical systems

Properties of the Dot Product Graph of a Commutative Ring

Maximizing $H$-colorings of connected graphs with fixed minimum degree

Proving Differential Privacy via Probabilistic Couplings

Smooth Kernel Estimation of a Circular Density Function: A Connection to Orthogonal Polynomials on the Unit Circle

Independent sets in polarity graphs

Partial Oxidation of Methane on a Nickel Catalyst: Kinetic Monte-Carlo Simulation Study

Incidence Geometry in a Weyl Chamber II: $SL_n$

Enumeration of Chord Diagrams without Loops and Parallel Chords

Enumeration of 4-regular one-face maps

Understanding Past Population Dynamics: Bayesian Coalescent-Based Modeling with Covariates

The fibres of the Scott map on polygon tilings are the flip equivalence classes