Pinboard (shivak)

Cone duality notes by Fukuda

shivak — 2012-10-23T20:27:16+00:00

On False Positives

shivak — 2012-10-15T23:20:25+00:00

"One mature Atlantic Salmon (Salmo salar) participated in the fMRI study. The salmon was approximately 18 inches long, weighed 3.8 lbs, and was not alive at the time of scanning. The task administered to the salmon involved completing an open-ended mentalizing task. The salmon was shown a series of photographs depicting individuals in social situations with a specified emotional valence. The salmon was asked to determine what emotion the individual in the photo must have been experiencing. Stimuli were presented in a block design with each photo presented for 10 seconds followed by 12 seconds of rest. A total of 15 photos were displayed. Total scan time was 5.5 minutes."

kryo.se: iodine (IP-over-DNS, IPv4 over DNS tunnel)

shivak — 2012-09-15T06:17:07+00:00

Better than TUNS.

QIS Workshop in Computer and Natural Sciences 2012

shivak — 2012-09-11T00:08:29+00:00

SUMS OF SQUARES, MOMENT MATRICES AND OPTIMIZATION OVER POLYNOMIALS

shivak — 2012-09-10T21:00:46+00:00

Introduction to concepts and advances in polynomial optimization

shivak — 2012-09-10T19:20:58+00:00

Forthcoming Book "Semidefinite Optimization and Convex Algebraic Geometry"

shivak — 2012-08-28T21:23:58+00:00

Understanding the Limitations of Linear and Semidefinite Programming

shivak — 2012-08-24T00:11:59+00:00

The Mathematical Challenge of Large Networks

shivak — 2012-08-19T05:04:04+00:00

Nice motivation of graph limits as an alternative approximation device to regularity partitions. Basic properties of graphons. Interesting but somewhat opaque calculus of graph(on)s.

Graphlets: A Spectral Perspective for Graph Limits

shivak — 2012-08-19T01:37:36+00:00

An awful talk by a good mathematician.

The similarity distance on graphs and graphons

shivak — 2012-08-18T21:58:28+00:00

Graph limits with particular emphasis on bounding the Szemeredi regularity tower.

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

Very large graphs

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

Gaussian Noise Sensitivity

shivak — 2012-08-18T18:33:26+00:00

Motivates the definition of rotation sensitivity and quickly proves its subadditivity via picture / union bound.

Quasirandom Processes

shivak — 2012-08-18T17:19:59+00:00

Γ-convergence - Wikipedia, the free encyclopedia

shivak — 2012-08-09T06:23:29+00:00

Small Deviation Probabilities: Theory and Applications

shivak — 2012-08-08T01:08:11+00:00

Paleo Gurl's Kitchen: Eggplant Chicken Sandwiches!

shivak — 2012-08-07T04:45:02+00:00

+Olive.

Moroccan Eggplant (Aubergine) Puree Salad - Kahrmus

shivak — 2012-08-07T04:43:10+00:00

Workshop: Provable Bounds in Machine Learning — August 1-2, 2012

shivak — 2012-08-04T00:48:53+00:00

Spectral graph sparsification Part 2: [An O(mlog2 n) algorithm for solving SDD systems]

shivak — 2012-08-03T19:06:58+00:00

Finding Dense Subgraphs

shivak — 2012-07-30T08:40:00+00:00

Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation

shivak — 2012-07-21T01:56:43+00:00

Open Problems in High Dimension Geometry

shivak — 2012-07-21T01:55:44+00:00

Zero Knowledge Proofs and Nuclear Disarmament

shivak — 2012-07-19T05:31:53+00:00

"I'll describe a physical implementation of zero knowledge proofs whose goal is to verify that two physical objects are identical, without revealing any information about them... I will not assume any background in either cryptography or nuclear disarmament."

CSDM: Nearly Optimal Deterministic Algorithms Via M-Ellipsoids

shivak — 2012-07-19T05:29:08+00:00

"Milman's ellipsoids play an important role in modern convex geometry. Here we show that their proofs of existence can be turned into efficient algorithms, and these in turn lead to improved deterministic algorithms for volume estimation of convex bodies, finding the shortest lattice vector under general norms and integer programming"

Entropy-Based Bounds on Dimension Reduction in L_1

shivak — 2012-07-19T05:27:32+00:00

Applications of FT-Mollification

shivak — 2012-07-19T05:24:44+00:00

"In FT-mollification, one smooths a function while maintaining good quantitative control on high-order derivatives. I will describe this approach and show how it can be used to show that bounded independence fools polynomial threshold functions over various distributions (Gaussian, Bernoulli, and p-stable)."

Relativized Separations of Worst-Case and Average-Case Complexities for NP

shivak — 2012-07-18T23:56:43+00:00

polytime approximation problems : UGC :: (sub)exponential time NP complete problems : ETH.

Higher-Order Cheeger Inequalities

shivak — 2012-07-17T17:00:09+00:00

Distributed GraphLab: A Framework for Machine Learning in the Cloud

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

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems

shivak — 2012-05-03T18:15:29+00:00

A Singly-Exponential Time Algorithm for Computing Nonnegative Rank

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

The Swiss Army Knife of Cryptography

shivak — 2012-05-03T18:07:59+00:00

Barak and Brakerski demonstrate the versatility of fully homorphic encryption.

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

Lectures on Discrete and Polyhedral Geometry

shivak — 2012-04-25T20:21:04+00:00

Regret in Online Combinatorial Optimization

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

Generalization Bounds and Consistency for Latent-Structural Probit and Ramp Loss

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

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

How Accurate is inv(A)*b?

shivak — 2012-04-24T21:49:14+00:00

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

Approximate Computation and Implicit Regularization for Very Large-scale Data Analysis

shivak — 2012-04-24T21:36:08+00:00

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

Approximation Algorithms for Network Design: A Survey

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

The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy

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

Suresh describes his distributed learning model

shivak — 2012-04-24T21:20:00+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.

STAT928: Statistical Learning Theory and Sequential Prediction

shivak — 2012-04-21T16:54:10+00:00

Hypercontractivity, Sum-of-Squares Proofs, and their Applications

shivak — 2012-04-19T17:02:27+00:00

EPIT Lectures: Lower Bounds

shivak — 2012-04-19T17:01:51+00:00

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

Why Obama's JOBS Act Couldn't Suck Worse

shivak — 2012-04-12T23:08:48+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