Barak and Brakerski demonstrate the versatility of fully homorphic encryption.

Chang's lemma is a useful tool in additive combinatorics and the analysis of Boolean functions. Here we give an elementary proof using entropy. The constant we obtain is tight, and we give a slight improvement in the case where the variables are highly biased.

"Two promising ways forward are: embedding maximal classes into maximum classes with at most a polynomial increase to VC dimension, and compression via operating on geometric representations. This paper presents positive results on the latter approach and a first negative result on the former, through a systematic investigation of finite maximum classes."

Reminds me of the face lattice.

"Linear predictors are scale-insensitive — the prediction does not change when the weight vector defining the predictor is scaled up or down. This implies that direct regularization of the performance of a linear predictor with a scale sensitive regularizer (such as a norm of the weight vector) is meaningless. Linear predictors are typically learned by introducing a scale-sensitive surrogate loss function such as the hinge loss of an SVM. However, no convex surrogate loss function can be consistent in general — in finite dimension SVMs are not consistent. Here we generalize probit loss and ramp loss to the latent-structural setting and show that both of these loss functions are consistent in arbitrary dimension for an arbitrary bounded task loss. Empirical experience with probit loss and ramp loss will be briefly discussed."

"Several widely-used textbooks lead the reader to believe that solving a linear system of equations Ax = b by multiplying the vector b by a computed inverse inv(A) is inaccurate. Virtually all other textbooks on numerical analysis and numerical linear algebra advise against using computed inverses without stating whether this is accurate or not. In fact, under reasonable assumptions on how the inverse is computed, x = inv(A)*b is as accurate as the solution computed by the best backward-stable solvers. This fact is not new, but obviously obscure. We review the literature on the accuracy of this computation and present a self-contained numerical analysis of it."

"Contextual bandit learning is a reinforcement learning problem where the learner repeatedly receives a set of features (context), takes an action and receives a reward based on the action and context. We consider this problem under a realizability assumption: there exists a function in a (known) function class, always capable of predicting the expected reward, given the action and context. Under this assumption, we show three things. We present a new algorithm---Regressor Elimination--- with a regret similar to the agnostic setting (i.e. in the absence of realizability assumption). We prove a new lower bound showing no algorithm can achieve superior performance in the worst case even with the realizability assumption. However, we do show that for any set of policies (mapping contexts to actions), there is a distribution over rewards (given context) such that our new algorithm has constant regret unlike the previous approaches."

"Bourgain showed that any noise stable Boolean function $f$ can be well-approximated by a junta. In this note we give an exponential sharpening of the parameters of Bourgain's result under the additional assumption that $f$ is a halfspace."

"We introduce a rich class of graphical models for multi-armed bandit problems that permit both the state or context space and the action space to be very large, yet succinctly specify the payoffs for any context-action pair. Our main result is an algorithm for such models whose regret is bounded by the number of parameters and whose running time depends only on the treewidth of the graph substructure induced by the action space."

Reinterpreting familiar norms.

"We give a new, simple algorithm for approximating any polynomial-size DNF expression from its "heavy" low-degree Fourier coefficients alone. Our algorithm greatly simplifies the proof of learnability of DNF expressions over smoothed product distributions."

"We show that the herding procedure of Welling (2009) takes exactly the form of a standard convex optimization algorithm--namely a conditional gradient algorithm minimizing a quadratic moment discrepancy. This link enables us to invoke convergence results from convex optimization and to consider faster alternatives for the task of approximating integrals in a reproducing kernel Hilbert space. We study the behavior of the different variants through numerical simulations. The experiments indicate that while we can improve over herding on the task of approximating integrals, the original herding algorithm tends to approach more often the maximum entropy distribution, shedding more light on the learning bias behind herding."

"We prove a structural result for degree-$d$ polynomials. In particular, we show that any degree-$d$ polynomial, $p$ can be approximated by another polynomial, $p_0$, which can be decomposed as some function of polynomials $q_1,...,q_m$ with $q_i$ normalized and $m=O_d(1)$, so that if $X$ is a Gaussian random variable, the probability distribution on $(q_1(X),...,q_m(X))$ does not have too much mass in any small box.
Using this result, we prove improved versions of a number of results about polynomial threshold functions, including producing better pseudorandom generators, obtaining a better invariance principle, and proving improved bounds on noise sensitivity."

"We present a novel approach for training kernel Support Vector Machines, establish learning runtime guarantees for our method that are better then those of any other known kernelized SVM optimization approach, and show that our method works well in practice compared to existing alternatives."

"Although we show that estimation of ||x||_0 is generally intractable in this framework, we consider an alternative measure of sparsity s(x):=frac{|x|_1^2}{|x|_2^2}, which is a sharp lower bound on ||x||_0, and is more amenable to estimation. When $x$ is a non-negative vector, we propose a computationally efficient estimator hat{s}(x), and use non-asymptotic methods to bound the relative error of hat{s}(x) in terms of a finite number of measurements. Remarkably, the quality of estimation is emph{dimension-free}, which ensures that hat{s}(x) is well-suited to the high-dimensional regime where n<<p."

Nice, David.

Local sequential Rademacher complexities.

"... treating the cumulants as elements of the polynomial ring."

"Here we show, with a common, general, and simpler analysis, that weight sharing in fact achieves much more than what it was designed for. We use it to simultaneously prove new shifting regret bounds for online convex optimization on the simplex in terms of the total variation distance as well as new bounds for the related setting of adaptive regret. Finally, we exhibit the first logarithmic shifting bounds for exp-concave loss functions on the simplex."

"The problem is equivalent to nding the best arm in the multi-armed bandit problem using adaptive strategies."

Includes a 'domination' lemma which reduces (sharp) concentration of vector-valued functions to that of the one-dimensional projections.

Nice, Kristina.

Smoothness + exp-concave loss allows online Newton to achieve regret bounded in terms of the "cumulative loss of the best point over the first T steps", which leads to regret no worse than O(log T), and much better if, for example, there's a perfect function.

Sparse subgradients.

Nice, John.

Hooray for DFS.

"This paper derives exponential concentration inequalities and polynomial moment inequalities for the spectral norm of a random matrix. The analysis requires a matrix extension of the scalar concentration theory developed by Sourav Chatterjee using Stein’s method of exchangeable pairs. When applied to a sum of independent random matrices, this approach yields matrix generalizations of the classical inequalities due to Hoeffding, Bernstein, Khintchine, and Rosenthal. The same technique delivers bounds for sums of dependent random matrices and more general matrix-valued functions of dependent random variables."

"We analyze the quality of the gaussian approximation to linear combinations of n independent, identically-distributed random variables with finite fourth moments. It turns out that there exist universal, simple linear combinations that perform better than the sum of the variables."

Approximate version of the Caratheodory theorem. A constructive version would be nice.

I guess I'll be TAing it this semester.

"This talk will illustrate to non-experts the use of geometric methods to design efficient partitioning algorithms for discrete objects or, in some cases, to prove that such algorithms must fail to perform well. These connections show that combinatorial optimization problems are intimately related to classical questions in continuous geometry, and we will describe some recent progress on old questions that translates to the best known results on algorithmic problems of central interest."

Suppose I have a (strongly) convex function F(x) which is a sum of N (strongly) convex functions f_i(x). To optimize F using N networked computers, optimize f_i separately on each machine while averaging in gradients from the neighboring machines. To prove this works, show you are actually solving an optimization problem over N variables x_1,...,x_N in which there is a regularization term enforcing closeness of the x_i.

Cool, but John's claim that it's "provably faster than any future single machine learning algorithm" is obviously wrong; just consider e.g. sublinear time algorithms.

Also:
http://www.youtube.com/watch?v=Xovmlla81L8
http://www.youtube.com/watch?v=BFE4PmEqvgg
http://www.youtube.com/watch?v=eekFM7pxqxc
http://www.youtube.com/watch?v=6ZbrXnOGlG4
http://www.youtube.com/watch?v=teba7aEqR-Y

"It is shown that at least 50% of the probability mass of a sum of independent Rademacher random variables is within one standard deviation from its mean. This lower bound is sharp, it is much better than for instance the bound that can be obtained from application of the Chebishev inequality..."