Title: Interlacing Families and Bipartite Ramanujan Graphs
Abstract: We will outline the proof that shows the existence of bipartite Ramanujan Graphs of any degree as well as some of mixed degrees. Our approach uses the idea of Bilu and Linial to show that there exists a 2-lift of a given Ramanujan graph which maintains the Ramanujan property. This will include introducing a new technique for establishing the existence of certain combinatorial objects that we call the "Method of Interlacing Polynomials."
This talk is intended to be accessible by a general computer science audience, and represents joint work with Dan Spielman and Nikhil Srivastava.
]]>]]>
Title: Auditing: Active Learning with Outcome-Dependent Query Costs
Abstract: We propose a learning setting in which unlabeled data is free, and the cost of a label depends on its value, which is not known in advance. Specifically, we study binary classification in an extreme case, where the algorithm only pays for negative labels. Our motivation is applications such as fraud detection, in which investigating an honest transaction should be avoided if possible. We term the setting "auditing", and consider the "auditing complexity" of an algorithm. We design auditing algorithms for simple hypothesis classes,
and show that with these algorithms, the auditing complexity can be significantly lower than the active label complexity. We also consider a general competitive approach for auditing,
and demonstrate its potential for linear classification.
Joint work with Anand Sarwate and Nati Srebro from TTI-Chicago
]]>Abstract: Consider a point process in the Euclidean space and a rule defining the edges that exist between its points. This defines a random graph on the point process. A routing algorithm constructs, for all pairs of points, a route between these points, namely a path of this graph connecting them, when possible. Such an algorithm can be global, like in shortest path routing, or local, like in geographic or geometric routing.
This talk will discuss properties of routes which are locally defined on a stationary point process, using the notion of point-shift.
A point-shift maps, in a translation invariant way, each point of a stationary point process Z to some point of Z. The existence of stationary regimes of a routing algorithm is then equivalent to that of probability measures, defined on the space of counting measures with an atom at the origin, which are left invariant by the point-shift f describing the local algorithm. The point-shift probabilities of Z are defined from the action of the semigroup of point-shift translations on the space of Palm probabilities, and more precisely from the compactification of the orbits of this semigroup action. If the point-shift probability is uniquely defined, and if f is continuous with respect to the vague topology, then the point-shift probability of Z provides a solution to the stationary regime question.
Point-shift probabilities are shown to be a strict generalization of Palm probabilities: when the considered point-shift f is bijective, the point-shift-probability of Z boils down to the Palm probability of Z. When it is not bijective, there exist cases where the point-shift-probability of Z is the law of Z under the Palm probability of some stationary thinning Y of Z. But there also exist cases where the point-shift-probability of Z is singular w.r.t. the Palm probability of Z and where, in addition, it cannot be the law of Z under the Palm probability of any stationary point process Y jointly stationary with Z. The talk will give a criterion for the existence of point-shift probabilities of a stationary point process and will discuss uniqueness. The results will be illustrated through several examples.
Joint work with Mir-Omid Haji-Mirsadeghi, Sharif University, Department of Mathematics.
]]>]]>
Abstract: We study a multi-server model with n flexible servers and rn queues, connected through a fixed bipartite graph, where the level of flexibility is captured by the average degree, d(n), of the queues. Applications in content replication in data centers, skill-based routing in call centers, and flexible supply chains are among our main motivations.
We focus on the scaling regime where the system size n tends to infinity, while the overall traffic intensity stays fixed. We show that a large capacity region (robustness) and diminishing queueing delay (performance) are jointly achievable even under very limited flexibility (d(n) << n). In particular, when d(n) >> ln(n), a family of random-graph-based interconnection topologies is (with high probability) capable of stabilizing all admissible arrival rate vectors (under a bounded support assumption), while simultaneously ensuring a diminishing queueing delay, of order ln(n)/d(n), as n tends to infinity. Our analysis is centered around a new class of virtual-queue-based scheduling policies that rely on dynamically constructed partial matchings on the connectivity graph. We also compare different architectures in terms of to what extend the joint objective of capacity and delay is possible.
Based on joint work with John N. Tsitsiklis.
]]>Abstract:
We introduce a framework for proving lower bounds on computational problems over distributions, based on a class of algorithms called statistical algorithms. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution, rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, e.g., moments-based methods, local search, standard iterative methods for convex optimization, MCMC and simulated annealing, are statistical algorithms or have statistical counterparts. Our framework is inspired by and generalizes the statistical query model in learning theory.
Our main application is a nearly optimal lower bound on the complexity of any statistical algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size O(n^(1/2-\delta)) for any constant \delta > 0. Variants of these problems have been assumed to be hard to prove hardness for other problems and for cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.
Joint work with Elena Grigorescu, Lev Reyzin, Santosh Vempala and Ying Xiao
]]>
]]>
Abstract:
The problem of quantifying the amount of information loss due to a random transformation (or a noisy channel) arises in a variety of contexts, such as machine learning, stochastic simulation, error-correcting codes, or computation in circuits with noisy gates, to name just a few. This talk will focus on discrete channels, where both the input and output sets are finite. The noisiness of a discrete channel can be measured by comparing suitable functionals of the input and output distributions. For instance, if we fix a reference input distribution, then the worst-case ratio of output relative entropy (Kullback-Leibler divergence) to input relative entropy for any other input distribution is bounded by one, by the data processing theorem. However, for a fixed reference input distribution, this quantity may be strictly smaller than one, giving so-called strong data processing inequalities (SDPIs). I will show that the problem of determining both the best constant in an SDPI and any input distributions that achieve it can be addressed using logarithmic Sobolev inequalities, which relate input relative entropy to certain measures of input-output correlation. I will also show that SDPIs for Kullback-Leibler divergence arises as a limiting case of a family of SDPIs for Renyi divergence, and discuss the relationship to hypercontraction of Markov operators.
Bio: Maxim Raginsky received the B.S. and M.S. degrees in 2000 and the Ph.D. degree in 2002 from Northwestern University, Evanston, IL, all in electrical engineering. He has held research positions with Northwestern, the University of Illinois at Urbana-Champaign (where he was a Beckman Foundation Fellow from 2004 to 2007), and Duke University. In 2012, he has returned to UIUC, where he is currently an Assistant Professor with the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory. In 2013, Prof. Raginsky has received a Faculty Early Career Development (CAREER) Award from the National Science Foundation. His research interests lie at the intersection of information theory, machine learning, and control.
]]>
Abstract:
We improve the running times of algorithms for least squares regression and low-rank approximation to account for the sparsity of the input matrix. Namely, if nnz (A) denotes the number of non-zero entries of an input matrix A:
All approximations are relative error. Previous algorithms based on fast Johnson-Lindenstrauss transforms took at least ndlog d or nnz(A)*k time. We have implemented our algorithms, and preliminary results suggest the algorithms are competitive in practice.
Joint work with Ken Clarkson.
]]>
Prasad Tetali (Director of Algorithms & Randomness Center (ARC), GaTech)
Objective:
The objective of this workshop is to bring together leaders and researchers from industry and academia to discuss:
(i) challenges, trends, and opportunities in various topics including logistics, supply chain management, display advertisement, and energy efficiency:
(ii) how to address them by leveraging state-of-the-art quantitative methods such as optimization, machine learning, algorithms, and stochastics.
Agenda:
08:45-09:15 Registration
09:15-10:15 Logistics
10:15-10:30 Break
10:30-12:30 Optimization
12:30-01:15 Lunch
01:15-02:45 Energy and Sustainability
02:45-03:15 Break
03:15-04:00 Panel of Discussion
04:00-05:00 Reception
http://robotics.gatech.edu/content/arc-rim-industry-day-2013
]]>
Organizers: Prasad Tetali and Santosh Vempala (GA Tech)
Agenda
April 8: ARC Distinguished Lecture
April 9: ARC Theory Day
Abstract:
Pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare or profit) is a central problem in Algorithmic Mechanism Design.
In this talk I will discuss some particularly simple algorithms that are able to achieve surprisingly strong guarantees for a range of problems of this type. As one example, for the problem of pricing <i>resources</i>, modeled as goods having an increasing marginal extraction cost to the seller, a simple approach of pricing the <i>i</i>th unit of each good at a value equal to the anticipated extraction cost of the <i>2i</i>th unit gives a constant-factor approximation to social welfare for a wide range of cost curves and for arbitrary buyer valuation functions. I will also discuss simple algorithms with good approximation guarantees for revenue, as well as settings having an opposite character to resources, namely having economies of scale or decreasing marginal costs to the seller.
]]>
Abstract:
Freezing is a key part of the clustering phenomenon that is hypothesized by non-rigorous techniques from statistical physics. Indeed, it has been shown that for different kinds of random CSPs (coloring, SAT, xor-sat, and other families), if the constraint-density of a random CSP, F, in our family is greater than r_f then for almost every solution of F, a linear number of variables are frozen, meaning that their colours cannot be changed by a sequence of alterations in which we change o(n) variables at a time, always switching to another solution. If the constraint-density is less than r_f, then almost every solution has o(n) frozen variables.
The understanding of clustering has led to the development of advanced heuristics such as Survey Propagation. It has been suggested that the freezing threshold is a precise algorithmic barrier. There is reason to believe that for densities below r_f the random CSPs can be solved using very simple algorithms, while for densities above r_f one requires more sophisticated techniques in order to deal with frozen clusters.
In this talk we will explain the current state of the art regarding the appearance of frozenness in random CSPs and we'll explain some of the tecniques used to analitically study such a phenomena.
]]>Abstract:
Efficiently optimizing linear functions over a polytope by directly solving the linear program requires a compact representation of the polytope, e.g., as an affine image of a polytope with few facets. We present an information theoretic approach for proving limits of such extension: the common information shared by the vertices and facets.
This framework not only improves recent lower bounds on the CLIQUE polytope by Braverman and Moitra, but also provides a much simplified proof, and is stable under perturbations of the polytope.
This is an ongoing joint work with Sebastian Pokutta.
]]>]]>
Abstract:
For a Boolean predicate f on k variables, let \rho(f) be the probability that a constraint of the form f(x_1,...,x_k) is satisfied by a random assignment. A predicate f is called "somewhat approximation resistant" if for some constant \tau > \rho(f), given a \tau-satisfiable instance of the Max-k-CSP(f) problem, it is NP-hard to find an assignment that strictly beats the naive algorithm that outputs a uniformly random assignment.
Let \tau(f) denote the supremum over all \tau for which the above holds. It is known that a predicate is somewhat approximation resistant precisely when its Fourier degree is at least 3. For such predicates, we give a characterization of the "hardness gap" (\tau(f) -\rho(f)) up to a factor of O(k^5). We also give a similar characterization of the integrality gap for the natural SDP relaxation of Max-k-CSP after \Omega(n) rounds of the Lasserre hierarchy.
Joint work with Subhash Khot and Pratik Worah.
]]>
Abstract:
Let F be a random Boolean formula in conjunctive normal form over n Boolean variables with m clauses of length k. The existence of a (non-uniform) sharp threshold for the satisfiability of such formulas is well known [Friedgut 1999]. However, despite considerable effort the precise location of this phase transition remains unknown for any k>2. The best previous upper and lower bounds differ by an additive $k\ln 2/2$ [Achlioptas, Peres 2003]. In this talk I present an improved lower bound, which reduces the gap to ~0.19. The proof is inspired by the cavity method of statistical mechanics.
]]>Abstract:
I shall discuss examples of recent Internet research oriented math activities:
1) Polymath5 - Erdos discrepancy problem.
The problem is to find a function from the natural numbers to {-1,1} such that the sum of values on any sequence of the form {a,2,3a,...,ra} is bounded. Erdos conjectured that no such function exists. It is still open even after many individual attempts and an attempt to solve it collectively in a polymath project.
Background: please look at this MO problem
http://mathoverflow.net/questions/105383/the-behavior-of-a-certain-greedy-algorithm-for-erds-discrepancy-problem (and the blog post linked there.)
2) The study of Mobius randomness over blogs and MathOverflow.
A function defined on the natural number is Mobius-random if its correlation with the Mobius function tends to zero. The prime number theorem asserts that the constant one function is Mobius random. I will discuss the result by Ben Green that functions described by bounded depth circuits are Mobius-random.
Here is one link
MO posts: http://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function, which contains more links.
I may briefly mention a couple more examples. One is my debate with Aram Harrow on the feasibility of quantum computers. It took place over the blog "Goedel's lost letter and NP=P" (The first post the last post ) and the other is probability-motivated questions regarding the computer game "angry birds".
I will try to give some taste of the mathematical problems/issues and also a little taste of this way of "doing mathematics".
]]>
http://www.cc.gatech.edu/~vempala/spectral/course.html
]]>
Abstract:
A fundamental problem in energy-efficient computing is to schedule multiple jobs released over time on a single machine with adjustable speed so as to minimize the sum of flowtime and energy. Note that the two objectives are in conflict: higher speeds reduce flowtime at the cost of increased energy consumption. In the clairvoyant version of the problem, the parameters of a job (volume and density) are revealed when the job is released. For this problem, a series of results culminated in a (2+epsilon)-competitive algorithm due to Bansal, Chan, and Pruhs. In this talk, I will consider the non-clairvoyant version of the problem where the density of a job is revealed on release but the volume is unknown. This version is often more practical and has been widely considered in other scheduling problems. We give a constant-competitive algorithm, which to the best of our knowledge, is the first non-trivial result for this problem.
Our algorithm is defined by simulating the clairvoyant algorithm in a novel inductive way, which then leads to an inductive analytical tool that may be of independent interest for other non-clairvoyant scheduling problems.
(Based on joint work with Yossi Azar, Nikhil Devanur, and Zhiyi Huang.)
]]>Abstract:
The focus of this talk is optimization in the presence of uncertain inputs. We model uncertainty as input being drawn from one among a large known class of distributions, however the specific distribution is unknown to the algorithm. The goal is to develop a single algorithm that for every distribution in this class, performs approximately as well as the optimal algorithm tailored for that specific distribution. Such algorithms are robust to assumptions on prior
distributions and are good candidates for deployment in real systems.
In this talk, we present general techniques for developing prior robust algorithms for two distinct lines of research --- online algorithms and mechanism design. In online algorithms, we present our results for a very general class of resource allocation problems with several applications, including to internet advertising. We develop a simple-to-implement prior robust algorithm with near optimal profit guarantee. Our algorithm has been deployed globally along with Microsoft MSN's display ads serving engine. In mechanism design, we focus on the well studied makespan minimization problem in machine scheduling. Here, our goal is to schedule jobs with stochastic runtimes on machines which are operated by strategic agents who hold the runtimes private. We design simple-to-implement truthful prior robust mechanisms that under different distributional assumptions provide constant and sub-logarithmic approximations to expected makespan.
]]>
Abstract:
Many tasks in machine learning (especially unsupervised learning) are provably intractable: NP-hard or worse. Nevertheless, researchers have developed heuristic algorithms to solve these tasks in practice. In most cases, there are no provable guarantees on the performance of these algorithms/heuristics ---neither on their running time, nor on the quality of solutions they return. Can we change this state of affairs?
This talk will suggest that the answer is yes, and cover three recent works as illustration. (a) A new algorithm for learning topic models.
This concerns a new algorithm for topic models (including the Linear Dirichlet Allocations of Blei et al. but also works for more general models) that provably works in theory under some reasonable assumptions and is also up to 50 times faster than existing software in practice. It relies upon a new procedure for nonnegative matrix factorization. (b) What classifiers are worth learning? (c) Provable ICA with unknown gaussian noise.
(Based upon joint works with Rong Ge, Ravi Kannan, Ankur Moitra, Sushant Sachdeva.)
]]>