I’m still catching up on my backlog of reading everything, but I’ve decided to set some time aside to take a look at a few papers from ArXiV.
- Lecture Notes on Free Probability by Vladislav Kargin, which is 100 pages of notes from a course at Stanford. Pretty self-explanatory, except for the part where I don’t really know free probability. Maybe reading these will help.
- Capturing the Drunk Robber on a Graph by Natasha Komarov and Peter Winkler. This is on a simple pursuit-evasion game in which the robber (evader) is moving according to a random walk. On a graph with
vertices:
the drunk will be caught with probability one, even by a cop who oscillates on an edge, or moves about randomly; indeed, by any cop who isn’t actively trying to lose. The only issue is: how long does it take? The lazy cop will win in expected time at most
(plus lower-order terms), since that is the maximum possible expected hitting time for a random walk on an n-vertex graph [2]; the same bound applies to the random cop [4]. It is easy to see that the greedy cop who merely moves toward the drunk at every step can achieve
; in fact, we will show that the greedy cop cannot in general do better. Our smart cop, however, gets her man in expected time
.
How do you make a smarter cop? In this model the cop can tell where the robber is but has to get there by walking along the graph. Strategies which try to constantly “retarget” are wasteful, so they propose a strategy wherein the cop periodically retargets to eventually meet the robber. I feel like there is a prediction/learning algorithm or idea embedded in here as well.
- Normalized online learning by Stephane Ross, Paul Mineiro, John Langford. Normalization and data pre-processing is the source of many errors and frustrations in machine learning practice. When features are not normalized with respect to each other, procedures like gradient descent can behave poorly. This paper looks at dealing with data normalization in the algorithm itself, making it “unit free” in a sense. It’s the same kind of weights-update rule that we see in online learning but with a few lines changed. They do an adversarial analysis of the algorithm where the adversary gets to scale the features before the learning algorithm gets the data point. In particular, the adversary gets to choose the covariance of the data.
- On the Optimality of Treating Interference as Noise, by Chunhua Geng, Navid Naderializadeh, A. Salman Avestimehr, and Syed A. Jafar. Suppose I have a
-user interference channel with gains
between transmitter
and receiver
. Then if
then treating interference as noise is optimal in terms of generalized degrees of freedom. I don’t really work on this kind of thing, but it’s so appealing from a sense of symmetry. - Online Learning under Delayed Feedback, byPooria Joulani, András György, Csaba Szepesvári. This paper is on forecasting algorithms which receive the feedback (e.g. the error) with a delay. Since I’ve been interested in communication with delayed feedback, this seems like a natural learning analogue. They provide ways of modifying existing algorithms to work with delayed feedback — one such method is to run a bunch of predictors in parallel and update them as the feedback is returned. They also propose methods which use partial monitoring and an approach to UCB for bandit problems in the delayed feedback setting.
-dimensional data points ![\{ \mathbf{x}_i : i \in [n] \}](http://s0.wp.com/latex.php?latex=%5C%7B+%5Cmathbf%7Bx%7D_i+%3A+i+%5Cin+%5Bn%5D+%5C%7D&bg=ffffff&fg=29303b&s=0 "\{ \mathbf{x}_i : i \in [n] \}")
the Lasso tries to fit the model 
by minimizing the 
penalized squared error
.
so the data is ![\{(\mathbf{X}_i, Y_i) : i \in [n] \}](http://s0.wp.com/latex.php?latex=%5C%7B%28%5Cmathbf%7BX%7D_i%2C+Y_i%29+%3A+i+%5Cin+%5Bn%5D+%5C%7D&bg=ffffff&fg=29303b&s=0 "\{(\mathbf{X}_i, Y_i) : i \in [n] \}")
. The assumptions are on the random variables 
is bounded, the variable 
, and 
, where 
and 
are unknown constants. Basically that’s all that’s needed — given a bound on 
, he derives a bound on the mean-squared prediction error.
, can be improved to 
. Most often this involves additional assumptions on the loss functions (which can sometimes get a bit baroque and hard to check). This paper considers constant step-size algorithms but where instead they consider the averaged iterate $\latex \bar{\theta}_n = \sum_{k=0}^{n-1} \theta_k$. I’m trying to slot this in with other things I know about stochastic optimization still, but it’s definitely worth a skim if you’re interested in the topic.
be 
in 
. The convex hull 
of these points is called a Gaussian polytope. This is a random polytope of course, and we can ask various things about their shape : what is the distribution of the number of vertices, or the number of 
-faces? Let 
be the number of 
) is given by![\mathbb{E}[ f_k(P_n)] = \frac{2^d}{\sqrt{d}} \binom{d}{k+1} \beta_{k,d-1}(\pi \ln n)^{(d-1)/2} (1 + o(1))](http://s0.wp.com/latex.php?latex=%5Cmathbb%7BE%7D%5B+f_k%28P_n%29%5D+%3D+%5Cfrac%7B2%5Ed%7D%7B%5Csqrt%7Bd%7D%7D+%5Cbinom%7Bd%7D%7Bk%2B1%7D+%5Cbeta_%7Bk%2Cd-1%7D%28%5Cpi+%5Cln+n%29%5E%7B%28d-1%29%2F2%7D+%281+%2B+o%281%29%29&bg=ffffff&fg=29303b&s=0 "\mathbb{E}[ f_k(P_n)] = \frac{2^d}{\sqrt{d}} \binom{d}{k+1} \beta_{k,d-1}(\pi \ln n)^{(d-1)/2} (1 + o(1))")
,
is the internal angle of a regular 
-simplex at one of its 
such that
. That is, appropriately normalized, the number of faces converges to a constant.
points to define a 
fraction of them will form a real 
, regardless of 
.
and 
is there a term we know that 
where 
and 
are isotropic Gaussian vectors with the same differential entropy as 
and 
with spherically symmetric decreasing densities and show that the differential entropy of their sum lies between the two terms in the regular EPI.
files, 
cache at each user, how should they cache files so as to best allow a broadcaster to share the bandwidth to them? More simply, suppose there are three people who may want to watch one of three different TV shows, and they can buffer the content of one TV show. Since a priori you don’t know which show they want to watch, the idea might be to buffer/cache the first 3rd of each show at each user. They show that this is highly suboptimal. Because the content provider can XOR parts of the content to each user, the caching strategy should not be the same at each user, and the real benefit is the global cache size.
