We propose methods to estimate the β-mixing coefficients of a real-valued geometrically ergodic Markov process from a single sample-pathX0,X1, . . .,Xn−1. Under standard smoothness conditions on the densities, namely, that the joint density of the pair (X0,Xm) for each m lies in a Besov spaceB1s,∞(R2) for some knowns> 0, we obtain a rate of convergence of orderO(log(n)n-[s]/(2[s]+2)) for the expected error of our estimator in this case; we use [s] to denote the integer part of the decompositions= [s] + }s{ ofs∈ (0, ∞) into an integer term and a strictly positive remainder term }s{ ∈ (0, 1]. We complement this result with a high-probability bound on the estimation error, and further obtain analogues of these bounds in the case where the state-space is finite. Naturally no density assumptions are required in this setting; the expected error rate is shown to be of orderO(log(n)n−1/2). The theoretical results are complemented with empirical evaluations.

A more general formulation of the linear bandit problem is considered to allow for dependencies over time. Specifically, it is assumed that there exists an unknown$\mathbb {R}^{d}$-valued stationary$\varphi $-mixing sequence of parameters$(\theta _{t}, \; t \in \mathbb {N})$which gives rise to payoffs. This instance of the problem can be viewed as a generalization of both the classical linear bandits with iid noise, and the finite-armed restless bandits. In light of the well-known computational hardness of optimal policies for restless bandits, an approximation is proposed whose error is shown to be controlled by the$\varphi $-dependence between consecutive$\theta _{t}$. An optimistic algorithm, called LinMix-UCB, is proposed for the case where$\theta _{t}$has an exponential mixing rate. The proposed algorithm is shown to incur a sub-linear regret of$\mathcal {O}\left ({{\sqrt {d n\mathop {\mathrm {polylog}} (n) }}}\right)$with respect to an oracle that always plays a multiple of$\mathbb {E}\;\theta _{t}$. The main challenge in this setting is to ensure that the exploration-exploitation strategy is robust against long-range dependencies. The proposed method relies on Berbee’s coupling lemma to carefully select near-independent samples and construct confidence ellipsoids around empirical estimates of$\mathbb {E}\;\theta _{t}$.

We propose strongly consistent estimators of the$\ell _{1}$norm of the sequence of$\alpha $-mixing (respectively$\beta $-mixing) coefficients of a stationary ergodic process. We further provide strongly consistent estimators of individual$\alpha $-mixing (respectively$\beta $-mixing) coefficients for a subclass of stationary$\alpha $-mixing (respectively$\beta $-mixing) processes with summable sequences of mixing coefficients. The estimators are in turn used to develop strongly consistent goodness-of-fit hypothesis tests. In particular, we develop hypothesis tests to determine whether, under the same summability assumption, the$\alpha $-mixing (respectively$\beta $-mixing) coefficients of a process are upper bounded by a given rate function. Moreover, given a sample generated by a (not necessarily mixing) stationary ergodic process, we provide a consistent test to discern the null hypothesis that the$\ell _{1}$norm of the sequence$\boldsymbol {\alpha }$of$\alpha $-mixing coefficients of the process is bounded by a given threshold$\gamma \in [0,\infty$) from the alternative hypothesis that$\left \lVert{ \boldsymbol {\alpha }}\right \rVert > \gamma $. An analogous goodness-of-fit test is proposed for the$\ell _{1}$norm of the sequence of$\beta $-mixing coefficients of a stationary ergodic process. Moreover, the procedure gives rise to an asymptotically consistent test for independence.

We investigate the problem of algorithmic fairness in the case where sensitive and non-sensitive features are available and one aims to generate new, `oblivious', features that closely approximate the non-sensitive features, and are only minimally dependent on the sensitive ones. We study this question in the context of kernel methods. We analyze a relaxed version of the Maximum Mean Discrepancy criterion which does not guarantee full independence but makes the optimization problem tractable. We derive a closed-form solution for this relaxed optimization problem and complement the result with a study of the dependencies between the newly generated features and the sensitive ones. Our key ingredient for generating such oblivious features is a Hilbert-space-valued conditional expectation, which needs to be estimated from data. We propose a plug-in approach and demonstrate how the estimation errors can be controlled. While our techniques help reduce the bias, we would like to point out that no post-processing of any dataset could possibly serve as an alternative to well-designed experiments.

The problem of time-series clustering is considered in the case where each data-point is a sample generated by a piecewise stationary process. While stationary processes comprise one of the most general classes of processes in nonparametric statistics, and in particular, allow for arbitrary long-range dependencies, their key assumption of stationarity remains restrictive for some applications. We address this shortcoming by considering piecewise stationary processes, studied here for the first time in the context of clustering. It turns out that this problem allows for a rather natural definition of consistency of clustering algorithms. Efficient algorithms are proposed which are shown to be asymptotically consistent without any additional assumptions beyond piecewise stationarity. The theoretical results are complemented with experimental evaluations.

The multi-armed restless bandit problem is studied in the case where the pay-off distributions are stationary $\varphi$-mixing. This version of the problem provides a more realistic model for most real-world applications, but cannot be optimally solved in practice, since it is known to be PSPACE-hard. The objective of this paper is to characterize a sub-class of the problem where good approximate solutions can be found using tractable approaches. Specifically, it is shown that under some conditions on the $\varphi$-mixing coefficients, a modified version of UCB can prove effective. The main challenge is that, unlike in the i.i.d. setting, the distributions of the sampled pay-offs may not have the same characteristics as those of the original bandit arms. In particular, the $\varphi$-mixing property does not necessarily carry over. This is overcome by carefully controlling the effect of a sampling policy on the pay-off distributions. Some of the proof techniques developed in this paper can be more generally used in the context of online sampling under dependence. Proposed algorithms are accompanied with corresponding regret analysis.

The problem of clustering is considered for the case where every point is a time series. The time series are either given in one batch (offline setting), or they are allowed to grow with time and new time series can be added along the way (online setting). We propose a natural notion of consistency for this problem, and show that there are simple, computationally efficient algorithms that are asymptotically consistent under extremely weak assumptions on the distributions that generate the data. The notion of consistency is as follows. A clustering algorithm is called consistent if it places two time series into the same cluster if and only if the distribution that generates them is the same. In the considered framework the time series are allowed to be highly dependent, and the dependence can have arbitrary form. If the number of clusters is known, the only assumption we make is that the (marginal) distribution of each time series is stationary ergodic. No parametric, memory or mixing assumptions are made. When the number of clusters is unknown, stronger assumptions are provably necessary, but it is still possible to devise nonparametric algorithms that are consistent under very general conditions. The theoretical findings of this work are illustrated with experiments on both synthetic and real data.

The problem of change point estimation is considered in a general framework where the data are generated by arbitrary unknown stationary ergodic process distributions. This means that the data may have long-range dependencies of an arbitrary form. In this context the consistent estimation of the number of change points is provably impossible. A formulation is proposed which overcomes this obstacle: it is possible to find the correct number of change points at the expense of introducing the additional constraint that the correct number of process distributions that generate the data is provided. This additional parameter has a natural interpretation in many real-world applications. It turns out that in this formulation change point estimation can be reduced to time series clustering. Based on this reduction, an algorithm is proposed that finds the number of change points and locates the changes. This algorithm is shown to be asymptotically consistent. The theoretical results are complemented with empirical evaluations.

The problem of multiple change point estimation is considered for sequences with unknown number of change points. A consistency framework is suggested that is suitable for highly dependent time-series, and an asymptotically consistent algorithm is proposed. In order for the consistency to be established the only assumption required is that the data is generated by stationary ergodic time-series distributions. No modeling, independence or parametric assumptions are made; the data are allowed to be dependent and the dependence can be of arbitrary form. The theoretical results are complemented with experimental evaluations.

This paper proposes a method for designing user interfaces based on ideas rooted in data communication theory. It suggests that a visual user interface should be treated as a multitransmitter, single-receiver communication system, where the total available bandwidth for transmission is limited. The proposed design entails the scaling of visual components that are displayed according to their degree of relevance to the user, or in other words, their probability of selection by the user