Pinboard (shivak)

Graphlets: a Spectral Perspective for Graph Limits

shivak — 2012-08-18T21:55:45+00:00

Testing properties of graphs and functions

shivak — 2012-08-18T21:54:30+00:00

Distributed GraphLab: A Framework for Machine Learning in the Cloud

shivak — 2012-05-03T18:16:05+00:00

A Singly-Exponential Time Algorithm for Computing Nonnegative Rank

shivak — 2012-05-03T18:09:13+00:00

An Entropic Proof of Chang's Inequality

shivak — 2012-05-03T18:04:16+00:00

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.

A Geometric Approach to Sample Compression

shivak — 2012-05-03T18:03:48+00:00

"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."

Symbolic Variable Elimination for Discrete and Continuous Graphical Models

shivak — 2012-05-01T22:05:05+00:00

Reminds me of the face lattice.

Adaptive Restart for Accelerated Gradient Schemes

shivak — 2012-04-27T16:37:08+00:00

Minimax Option Pricing Meets Black-Scholes in the Limit

shivak — 2012-04-27T15:58:34+00:00

Regret in Online Combinatorial Optimization

shivak — 2012-04-24T22:12:18+00:00

Contextual Bandit Learning with Predictable Rewards

shivak — 2012-04-24T21:44:39+00:00

"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."

On the Distribution of the Fourier Spectrum of Halfspaces

shivak — 2012-04-24T21:41:41+00:00

"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."

Graphical Models for Bandit Problems

shivak — 2012-04-24T21:40:51+00:00

"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."

Trace Lasso: a trace norm regularization for correlated designs

shivak — 2012-04-24T21:39:26+00:00

Reinterpreting familiar norms.

Learning DNF Expressions from Fourier Spectrum

shivak — 2012-04-24T21:35:41+00:00

"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."

On the Equivalence between Herding and Conditional Gradient Algorithms

shivak — 2012-04-24T21:28:51+00:00

"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."

A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions

shivak — 2012-04-24T21:26:55+00:00

"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."

The Kernelized Stochastic Batch Perceptron

shivak — 2012-04-24T21:25:33+00:00

"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."

The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy

shivak — 2012-04-24T21:22:48+00:00

Estimating Unknown Sparsity in Compressed Sensing

shivak — 2012-04-24T21:19:06+00:00

"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<

Efficient Protocols for Distributed Classification and Optimization

shivak — 2012-04-24T21:18:21+00:00

Improved small-set expansion from higher eigenvalues

shivak — 2012-04-24T21:16:43+00:00

Nice, David.

Making Polynomials Robust to Noise

shivak — 2012-04-19T17:00:39+00:00

Learning Topic Models - Going beyond SVD

shivak — 2012-04-19T17:00:06+00:00

Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits

shivak — 2012-04-19T16:59:10+00:00

Distributed Learning, Communication Complexity and Privacy

shivak — 2012-04-19T16:58:22+00:00

Relax and Localize: From Value to Algorithms

shivak — 2012-04-04T22:29:44+00:00

Local sequential Rademacher complexities.

Algebraic Geometric Comparison of Probability Distributions

shivak — 2012-04-03T00:16:46+00:00

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

Equality Set Projection: A new algorithm for the projection of polytopes in halfspace representation

shivak — 2012-04-01T19:03:29+00:00

Estimates for the concentration functions of weighted sums of independent random variables

shivak — 2012-03-30T21:56:56+00:00

A new look at shifting regret

shivak — 2012-02-26T06:05:07+00:00

"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."

Finding the most biased coin with fewest flips

shivak — 2012-02-26T06:00:27+00:00

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

A PTAS for Computing the Supremum of Gaussian Processes

shivak — 2012-02-26T05:41:21+00:00

On measure concentration of vector valued maps

shivak — 2012-02-12T05:32:54+00:00

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

Inductive types in homotopy type theory

shivak — 2012-02-08T22:27:54+00:00

Nice, Kristina.

Beyond Logarithmic Bounds in Online Learning

shivak — 2012-02-08T00:47:20+00:00

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.

Subgradient methods for huge-scale optimization problems

shivak — 2012-02-04T21:45:48+00:00

Sparse subgradients.

A new point of hardness for unique games

shivak — 2012-02-04T05:25:36+00:00

Nice, John.

The phase transition in random graphs - a simple proof

shivak — 2012-02-02T05:42:13+00:00

Hooray for DFS.

Matrix Concentration Inequalities via the Method of Exchangeable Pairs

shivak — 2012-01-29T19:28:58+00:00

"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."

Variations on the Berry-Esseen theorem

shivak — 2012-01-26T21:59:41+00:00

"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."

Approximation Algorithms for Reliable Stochastic Combinatorial Optimization

shivak — 2012-01-22T04:07:07+00:00

Confluent Persistence Revisited

shivak — 2012-01-11T07:59:33+00:00

Fast Distributed Gradient Methods

shivak — 2012-01-10T19:43:46+00:00

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.

On a conjecture concerning the sum of independent Rademacher random variables

shivak — 2012-01-10T17:53:03+00:00

"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..."

Central Binomial Tail Bounds

shivak — 2012-01-10T17:51:05+00:00

"An alternate form for the binomial tail is presented, which leads to a variety of bounds for the central tail. A few can be weakened into the corresponding Chernoff and Slud bounds, which not only demonstrates the quality of the presented bounds, but also provides alternate proofs for the classical bounds."

A Scalable Bootstrap for Massive Data

shivak — 2012-01-10T17:48:02+00:00

"...we introduce the Bag of Little Bootstraps (BLB), a new procedure which incorporates features of both the bootstrap and subsampling to obtain a robust, computationally efficient means of assessing the quality of estimators. BLB is well suited to modern parallel and distributed computing architectures and furthermore retains the generic applicability and statistical efficiency of the bootstrap."

A Simpler Approach to Matrix Completion

shivak — 2012-01-10T17:44:15+00:00

"This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low-rank matrix...The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory."

Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified

shivak — 2012-01-10T17:40:08+00:00

The Complexity of Statistical Algorithms

shivak — 2012-01-10T17:38:32+00:00

I didn't especially care for the 1st draft of this paper, but now it's fortified with Vitaly Feldman.

High-Confidence Predictions under Adversarial Uncertainty

shivak — 2012-01-10T17:26:12+00:00

ITCS 2011 best paper

Sparse Algorithms are not Stable: A No-free-lunch Theorem

shivak — 2012-01-10T17:00:02+00:00

"We show that these two properties are fundamentally at odds with each other: a sparse algorithm cannot be stable and vice versa."

Computing without memory

shivak — 2011-11-28T06:33:10+00:00

Cute! "In this paper, we generalise the famous algorithm for swapping the contents of two variables without using a buffer. We introduce a novel combinatorial framework for procedural programming languages, where programs are only allowed to update one variable at a time. We first consider programs which do not have any additional memory. We prove that any function of all the variables can be computed this way in a number of updates which grows linearly with the number of variables. Similarly, any linear function can be computed using a linear number of linear instructions. We then derive the exact number of instructions required to compute any manipulation of variables. Second, we show that allowing programs to use additional memory is also incorporated in our framework. We quantify the gains obtained by using additional memory. This leads to shorter programs and allows to use only binary instructions, which is not sufficient in general when no memory is used."

Falsification and future performance

shivak — 2011-11-28T06:31:29+00:00

"We information-theoretically reformulate two measures of capacity from statistical learning theory: empirical VC-entropy and empirical Rademacher complexity. We show these capacity measures count the number of hypotheses about a dataset that a learning algorithm falsifies when it finds the classifier in its repertoire minimizing empirical risk. It then follows from that the future performance of predictors on unseen data is controlled in part by how many hypotheses the learner falsifies. As a corollary we show that empirical VC-entropy quantifies the message length of the true hypothesis in the optimal code of a particular probability distribution, the so-called actual repertoire."

Subsampling Mathematical Relaxations and Average-case Complexity

shivak — 2011-11-27T23:26:13+00:00

One may subsample the canonical LP and SDP relaxations of CSPs, among others.

On the Fundamental Limits of Adaptive Sensing

shivak — 2011-11-22T06:00:21+00:00

"We prove that the advantages offered by clever adaptive strategies and sophisticated estimation procedures---no matter how intractable---over classical compressed acquisition/recovery schemes are, in general, minimal."

A Discrepancy based Approach to Integer Programming

shivak — 2011-11-22T05:36:59+00:00

Dimension reduction by random hyperplane tesselations

shivak — 2011-11-19T02:50:10+00:00

"Given a subset K of the unit Euclidean sphere, we estimate the minimal number m = m(K) of hyperplanes that generate a uniform tessellation of K, in the sense that the fraction of the hyperplanes separating any pair x,y in K is nearly proportional to the Euclidean distance between x and y. Random hyperplanes prove to be almost ideal for this problem; they achieve the almost optimal bound m = O(w(K)^2) where w(K) is the Gaussian mean width of K."

Lifts of convex sets and cone factorizations

shivak — 2011-11-17T20:28:20+00:00

"In this paper we address the basic geometric question of when a given convex set is the image under a linear map of an affine slice of a given closed convex cone. Such a representation or 'lift' of the convex set is especially useful if the cone admits an efficient algorithm for linear optimization over its affine slices."

New Concentration Inequalities for Suprema of Empirical Processes

shivak — 2011-11-16T02:07:55+00:00

Estimated VC dimension for risk bounds

shivak — 2011-11-16T02:06:30+00:00

It's been a while since I visited VC-land, but: VC dimension is expressly a distribution-independent concept which is known to be computationally hard to estimate. Those interested in distribution-specific bounds are probably more interested in VC entropy. IIRC VC entropy concentrates around its expectation. (Edit: they want to use unbounded losses.)

Adaptive Regret Minimization in Bounded-Memory Games

shivak — 2011-11-15T04:30:59+00:00

Noncommutative Bennett and Rosenthal Inequalities

shivak — 2011-11-13T05:08:27+00:00

Deviation inequalities for "quantum" probability.

The Bernstein-Orlicz norm and deviation inequalities

shivak — 2011-11-11T05:03:35+00:00

"We introduce two new concepts designed for the study of empirical processes. First, we introduce a new Orlicz norm which we call the Bernstein-Orlicz norm. This new norm interpolates sub-Gaussian and sub-exponential tail behavior. In particular, we show how this norm can be used to simplify the derivation of deviation inequalities for suprema of collections of random variables. Secondly, we introduce chaining and generic chaining along a tree. These simplify the well-known concepts of chaining and generic chaining. The supremum of the empirical process is then studied as a special case. We show that chaining along a tree can be done using entropy with bracketing. Finally, we establish a deviation inequality for the empirical process for the unbounded case."

Robust Interactive Learning

shivak — 2011-11-09T18:25:50+00:00

"In each query, the algorithm proposes a label and a subset of the unlabeled examples, and asks the oracle to point to one of these examples whose true label agrees with the speciﬁed label, if any exist. This is a strict generalization of the traditional model of active learning by label requests." This is the model that Avrim Blum casually proposed to me in his class two years ago.

Improved Smoothed Analysis of Multiobjective Optimization

shivak — 2011-11-09T18:22:22+00:00

Slightly tighter analysis of Moitra & O'Donnell. More importantly: bounds higher moments.

Approximate Stochastic Subgradient Estimation Training for Support Vector Machines

shivak — 2011-11-04T18:25:53+00:00

"...we use Vapnik’s original SVM formulation without modifying the objective to be strongly convex." It's strongly convex in the hyperplane but only convex in the offset. But what's wrong with adding a dummy feature?

Active Testing

shivak — 2011-11-04T18:13:46+00:00

Uses the active learning model to achieve property testing goals.

Computing a Nonnegative Matrix Factorization -- Provably

shivak — 2011-11-04T18:12:22+00:00

"Vavasis proved that this problem is NP-complete...We give a polynomial-time algorithm for exact and approximate NMF for every constant $r$...We give an algorithm that runs in time polynomial in $n$, $m$ and $r$ under the separablity condition identified by Donoho and Stodden in 2003."

PAC-Bayesian Inequalities for Martingales

shivak — 2011-11-01T02:05:57+00:00

And http://arxiv.org/abs/1110.6755 .