Title:  Providing Statistical Guarantees for Topological Summaries of Data

Abstract:
Persistent homology is a method for probing topological properties of point clouds and function. The method involves tracking the birth and death of topological features as one varies a tuning parameter. Features with short lifetimes are informally considered to be “topological noise.” I am interested in bringing statistical ideas to persistent homology in order to distinguish topological signal from topological noise and to derive meaningful, yet computable, summaries of large datasets.  In this talk, I will define some of the existing topological summaries of data, and show how we can provide statistical guarantees of these summaries.
www.fasy.us

Wednesday, November 19, 2014

Klaus 1116 E & W - 1:30 pm

Geoffrey Hinton – Distinguished Professor, University of Toronto and Distinguished Researcher, Google

Title: "Deep Learning" 

Abstract:

Dr. Hinton will give a brief history of deep learning explaining what it is, what kinds of task it should be good for and why it was largely abandoned in the 1990's. He will then describe how ideas from statistical physics were used to make deep learning work much better on small datasets. Finally Dr. Hinton will describe how deep learning is now used by Google for speech recognition and object recognition and how it may soon  be used for machine translation.

Bio:

Geoffrey Hinton received his BA in experimental psychology from Cambridge in 1970 and his PhD in Artificial Intelligence from Edinburgh in 1978. He did postdoctoral work at Sussex University and the University of California San Diego and spent five years as a faculty member in the Computer Science department at Carnegie-Mellon University. He then became a fellow of the Canadian Institute for Advanced Research and moved to the Department of Computer Science at the University of Toronto. He spent three years from 1998 until 2001 setting up the Gatsby Computational Neuroscience Unit at University College London and then returned to the University of Toronto where he is a University Professor. He is the director of the program on "Neural Computation and Adaptive Perception" which is funded by the Canadian Institute for Advanced Research. Geoffrey Hinton is a fellow of the Royal Society, the Royal Society of Canada, and the Association for the Advancement of Artificial Intelligence. He is an honorary foreign member of the American Academy of Arts and Sciences, and a former president of the Cognitive Science Society. He has received honorary doctorates from the University of Edinburgh and the University of Sussex. He was awarded the first David E. Rumelhart prize (2001), the IJCAI award for research excellence (2005), the IEEE Neural Network Pioneer award (1998), the ITAC/NSERC award for contributions to information technology (1992) the Killam prize for Engineering (2012) and the NSERC Herzberg Gold Medal (2010) which is Canada's top award in Science and Engineering. Geoffrey Hinton designs machine learning algorithms. His aim is to discover a learning procedure that is efficient at finding complex structure in large, high-dimensional datasets and to show that this is how the brain learns to see. He was one of the researchers who introduced the back-propagation algorithm that has been widely used for practical applications. His other contributions to neural network research include Boltzmann machines, distributed representations, time-delay neural nets, mixtures of experts, variational learning, products of experts and deep belief nets. His current main interest is in unsupervised learning procedures for multi-layer neural networks with rich sensory input.

Title: 
A Faster Algorithm for Linear Programming

Abstract: 
In this talk I will present a new algorithm for solving linear programs. Given a linear program with n variables, m > n constraints, and bit complexity L, our algorithm runs in Õ(sqrt(n) L) iterations each consisting of solving Õ(1) linear systems and additional nearly linear time computation. Our method improves upon the convergence rate of previous state-of-the-art linear programming methods which required solving either Õ(sqrt(m)L) linear systems [R88] or consisted of Õ((mn)^(1/4)) steps of more expensive linear algebra [VA93]. 

Interestingly, our algorithm not only nearly matches the convergence rate of the universal barrier of Nesterov and Nemirovskii [NN94], but in the special case of the linear programming formulation of various flow problems our methods converge at a rate faster than that predicted by any self-concordant barrier. In particular, we achieve a running time of Õ(|E| sqrt(|V| log^2 U) for solving the maximum flow problem on a directed graph with |E| edges, |V| vertices, and capacity ratio U, thereby improving upon the previous fastest running time for solving this problem when |E| > Ω(|V|^1+epsilon) for any constant epsilon. 

This talk will assume little exposure to linear programming algorithms, convex optimization, or graph theory and will require no previous experience with the universal barrier or self-concordance. 

This talk reflects joint work with Aaron Sidford. 
 See http://arxiv.org/abs/1312.6677 and http://arxiv.org/abs/1312.6713

Bio:
Yin Tat Lee is a PhD student (under Professor Jonathan Kelner) at MIT, studying theoretical computer science. His areas of research span convex optimization, linear programming, spectral graph theory and algorithmic graph theory. He is particularly interested in combining convex optimization and combinations techniques to design fast algorithms for fundamental cut/flow problems. He is one of the recipients of the Best Paper Awards at SODA 2014, FOCS 2014 for his results on the maximum flow problem and linear programming.

Efficient Density Estimation via Piecewise Polynomial Approximation

Abstract:

We give a highly efficient "semi-agnostic" algorithm for learning univariate probability distributions that are well approximated by piecewise polynomial density functions. Let p be an arbitrary distribution over an interval I which is τ-close (in total variation distance) to an unknown probability distribution q that is defined by an unknown partition of I into t intervals and t unknown degree-d polynomials specifying q over each of the intervals. We give an algorithm that draws O~(t (d+1)/ε^2) samples from p, runs in time poly(t,d,1/ ε), and with high probability outputs a piecewise polynomial hypothesis distribution h that is (O(τ)+ε)-close (in total variation distance) to p. This sample complexity is essentially optimal; we show that even for τ=0, any algorithm that learns an unknown t-piecewise degree-d probability distribution over I to accuracy ε must use Ω(t(d+1)/(polylog(d+1) ε^2)) samples from the distribution, regardless of its running time. Our algorithm combines tools from approximation theory, uniform convergence, linear programming, and dynamic programming.

We apply this general algorithm to obtain a wide range of results for many natural problems in density estimation over both continuous and discrete domains. These include state-of-the-art results for learning mixtures of log-concave distributions; mixtures of t-modal distributions; mixtures of Monotone Hazard Rate distributions; mixtures of Poisson Binomial Distributions; mixtures of Gaussians; and mixtures of k-monotone densities. Our general technique yields computationally efficient algorithms for all these problems, in many cases with provably optimal sample complexities (up to logarithmic factors) in all parameters.

Short Bio:

Siu On Chan is a Postdoc at Microsoft Research. He did his undergrad in Chinese University of Hong Kong, MSc at University of Toronto, and PhD at UC Berkeley. He is interested in studying the limitations of approximation algorithms, in terms of NP-hardness and integrality gaps of convex programming hierarchies. He is also interested in random graphs and property testing. He received a Best Paper Award at STOC 2013.

On-line Approach to Off-line Graph Coloring Problems

Abstract: 

The on-line graph coloring problem is modeled by a game between two players: Presenter, who constructs a graph of some fixed class presenting new vertices one by one, and Algorithm, who colors each vertex right after it is presented without the possibility of changing the color afterwards. The goal of Algorithm is to use as few colors as possible, while Presenter tries to force Algorithm to use many colors. Any game of this kind gives rise to a new class of graphs, called game graphs, which "encode" strategies of Presenter in the game. The chromatic number of such a game graph is equal to the number of colors that Algorithm is forced to use playing against the corresponding strategy. It turns out that game graphs of appropriately defined games can be modeled as intersection graphs of geometric objects. This is the key idea which combined with on-line competitivity analysis and graph decomposition techniques yields lower and upper bounds on the maximum possible chromatic number in various classes of geometric intersection graphs. I will survey results obtained with this method, present in detail its application to constructing triangle-free geometric intersection graphs with arbitrarily large chromatic number (solution to a problem of Erdős from the 1970s), and discuss several open problems that arose from this research. This is my joint work with various coauthors during last 2 years.

ARC: http://www.arc.gatech.edu/

Abstract:

I will present a number of stories about some results that I think highlight how results get proved and how they do not. These will span problems from almost all areas of theory, and will include both successes and failures. I hope that beyond the actual results you will enjoy and hopefully profit from the stories.

Abstract:

Many of today's real-world communication networks are highly dynamic, i.e., their network topology changes continuously over time. Examples include Peer-to-Peer (P2P) networks and ad hoc wireless and sensor networks. Such networks are now widely used in various applications, including sharing data and resources, search and storage, Internet telephony, environment monitoring and management. In P2P networks (e.g., Skype, BitTorrent), the topology changes at a rapid rate due to continuous joining and leaving of nodes; in ad hoc sensor and vehicular networks, the topology changes dynamically due to failure or mobility of the nodes. Performing robust and efficient non-trivial distributed computation in such highly dynamic networks is challenging. In this talk, I will give an overview of our recent results that make progress towards developing an algorithmic theory of dynamic networks. First, I will present a rigorous theoretical framework for studying dynamic networks. Then I will present efficient techniques and algorithms for solving the fundamental agreement problem in dynamic networks. I will also present efficient algorithms for key problems such as information spreading, search, and storage. To complement our algorithms, I will also present almost tight lower bounds for agreement and information spreading. 

Abstract:

Given a very large, node-weighted, rooted tree on, say, n nodes, if one has only enough space to display a k-node summary of the tree, what is the most informative way to draw the tree?  We define a type of weighted tree that we call a "summary tree" of the original tree, that results from aggregating nodes of the original tree subject to certain constraints. We suggest that the best choice of which summary tree to use (among those with a fixed number of nodes) is the one that maximizes the information-theoretic entropy of a natural probability distribution associated with the summary tree, and we provide a (pseudopolynomial-time) dynamic-programming algorithm to compute this maximum entropy summary tree, when the weights are integral. The result is an automated way to summarize large trees and retain as much information about them as possible, while using (and displaying) only a fraction of the original node set.  We also provide an additive approximation algorithm and a greedy heuristic that are faster than the optimal algorithm, and generalize to trees with real-valued weights.

This is joint work with Ken Shirley of ATT Labs and Richard Cole of NYU.

Abstract:

The cut-dominant of a connected graph G is the polyhedron that corresponds to the problem of computing global min-cuts in G. Despite the fact that computing a global min-cut can be done in polynomial time, the geometry of the cut-dominant is far from being understood. We study graphs for which all facets of the corresponding cut-dominant have right-hand side at most a fixed integer k. These graphs form a minor-closed collection. We give a complete list of forbidden minors for k <= 2. This is then applied to the TSP to give a shorter proof of a classic result of Fonlupt and Naddef (Math. Prog., 1992)  that characterizes TSP-perfect graphs. This work in progress is joint with Kanstantsin Pashkovich (Brussels) and Michele Conforti (Padova).

 Abstract:

In this talk we will talk about two new database join algorithms with provable optimality guarantees.

 We first present a recent algorithm (PODS 2012) that is the first provably optimal (worst-case) algorithm to compute database joins. As a special case, this join algorithm implies (i) The first algorithmic versions of some well-known geometric inequalities due to Loomis and Whitney (and their generalizations by Bollobas and Thomason); (ii) Algorithmically list recoverable codes that work with parameters that no known algorithmic list recovery result work with (e.g. those based on the Reed-Solomon codes) and an application of this result in designing sublinear time decodable compressed sensing schemes; (ii) Worst-case optimal algorithm to list all occurrences of any fixed hypergraph H in a given large hypergraph G.

 The second algorithm (PODS 2014) has stronger optimality guarantees: we present an adaptive join algorithm whose run time depends on the "difficulty" of the data. We believe that this algorithm has more practical applications since worst-case optimal algorithms might have terrible performance on "real data." As a special case, we present an (almost) instance optimal algorithm (with respect to comparison based algorithms) for a large class of join queries (namely Fagin's \beta-acyclic queries).

 The talk will be self-contained and is based on join(t) works with Ngo, Nguyen, Porat and Re.

Abstract:

We present an e-voting system wherein votes are represented to the vote-tallying center in the form COM(X) = (COM(u) , COM(v)) , vote = val(X) = (u + v) mod p. The voter gets a paper receipt for COM(X). His actual vote remains secret and he cannot be coerced to cast a specified vote. Vote tallying retains secrecy of individual votes while producing and posting a publicly verifiable proof of correctness of announced election results. The presentation will be generally accessible. Joint work with Ron Rivest.

Abstract:

In an important mechanism for sealed bid auctions developed by Vickrey and rewarded by a Nobel Prize, the highest bidder gets the item and pays the second highest bid value. Vickrey proved that for these auctions the best strategy for a participant is to bid his private true value for the item. Despite this advantage, second-price auctions are rarely used because they are subject to collusion of bidders. Employing novel cryptography we show that collusion can be avoided thus solving a long standing open problem. The talk will be generally accessible. Joint work with Silvio Micali.

Abstract:

Advances in machine learning and developments in modern massive parallel computational systems motivate a large number of challenging questions for the theory of computing. How to make sense of massive amounts of noisy data? How to cluster billions of points and compare large images? How to design scalable algorithms for distributed systems?

I will present examples of settings in which these questions can be addressed through the design of randomized algorithms:

• Sublinear algorithms for testing properties of high-dimensional noisy data such (e.g. monotonicity, the Lipschitz property and convexity)
• Distributed algorithms for geometric problems in Euclidean space (minimum cost spanning tree, Earth-Mover Distance)

Through these examples I will illustrate how information-theoretic measures of performance such as query complexity and the number of rounds of communication play a key role in the design and analysis of such algorithms. I will show that even in the worst-case these fundamental problems can be solved almost optimally with respect to these measures. The information-theoretic nature is crucial here since lower bounds can be proved unconditionally, i.e. with no computational hardness assumptions.

This talk will be primarily based on two papers which will appear in STOC’14 (joint work with Andoni, Berman, Nikolov, Onak and Raskhodnikova) as well as other work by the speaker.

Abstract:

A k-ary boolean predicate f, naturally implies a canonical constraint satisfaction problem (CSP(f)). Let MAX k-CSP(f) denote the problem of finding the maximum fraction of simultaneously satisfiable constraints in any given instance of CSP(f). A trivial randomized algorithm achieves an approximation factor proportional to f^{-1}(1).

 On the other hand, it is known, for some f, that an efficient algorithm can not perform strictly better than the trivial algorithm - such f are known as approximation resistant.

 One of the main problems in this area is to characterize which predicates are approximation resistant.

 In this talk, I will survey known bounds for CSPs and their connections with LP and SDP hierarchies. Finally, I will give an overview of my recent research in this area, which gives a characterization of approximation resistance.

 (Joint with S.Khot and M.Tulsiani).

 Abstract:

Walras, while defining the quintessential notion of market equilibrium in 1874, also gave a simple and natural rule for updating prices and called it the tatonnement process.  Does the tatonnement process converge to equilibrium prices? This was a central question in mathematical economics for almost a century. Positive news came in the 1950s, when convergence  was established for the gross substitutes case. However, it was followed by negative news in the 1960s: an example by Scarf on which tatonnement cycles and the Sonnenschein-Debreu-Mantel theorem which showed that the task was hopeless for a general Arow-Debreu market.

  In this work we have, for the first time, gone beyond the gross substitutes case. We define a class of markets for which tatonnement is equivalent to gradient descent. This is the class of markets for which there is a convex potential function whose gradient is always equal to the negative of the excess demand. We call this class the Convex Potential Function (CPF) markets. We show the following results:

  - CPF markets contain the class of Eisenberg Gale (EG) markets, defined previously by Jain and Vazirani.

  - The subclass of CPF markets for which the demand is a differentiable function contains exactly those markets whose demand function has a symmetric negative semi-definite Jacobian.

  - We define a family of continuous versions of tatonnement based on gradient descent using a Bregman divergence. As we show, for many CPF markets, every process in this family will converge to an equilibrium and the process based on KL-divergence will converge for even more of these markets. This is analogous to the classic result for markets satisfying the Weak Gross Substitutes property. We use the theory of differential inclusions, a generalization of differential equations, to establish this result.

  - A discrete version of tatonnement converges toward the equilibrium for Fisher markets with buyers having CES or Leontief utility functions; the convergence rates for these settings are analyzed using a common potential function. For the CES case, we prove that the tatonnement converges linearly by showing that the potential function satisfies strong sandwiching property, which is reminiscent of strong convexity.

  I will also discuss our recent results on:

  - ongoing Fisher markets, a model proposed by Cole and Fleischer. In this model, price updates are asynchronous, and warehouses are incorporated to meet excess demand and store excess supply;

 - Fisher markets with NCES utility functions, a generalization of CES utility functions.

 Joint work with Richard Cole and Nikhil Devanur.

 Abstract: A direct sum theorem for two parties and a function f states that the communication cost of solving k copies of f simultaneously with error probability 1/3 is at least k R_{1/3}(f), where R_{1/3}(f) is the communication required to solve a single copy of f with error probability 1/3. We improve this for a natural family of functions f, showing that the 1-way communication required to solve k copies of f simultaneously with probability 2/3 is Omega(k R_{1/k}(f)). Since R_{1/k}(f) may be as large as Omega(R_{1/3}(f) log k), we asymptotically beat the direct sum bound for such functions, showing that the trivial upper bound of solving each of the k copies of f with probability 1-O(1/k) and taking a union bound is optimal! In order to achieve this, our direct sum involves a novel measure of information cost which allows a protocol to abort with constant probability, and otherwise must be correct with very high probability. Moreover, for the functions considered, we show strong lower bounds on the communication cost of protocols with these relaxed guarantees; indeed, our lower bounds match those for protocols that are not allowed to abort.

In the distributed and streaming models, where one wants to be correct not only on a single query, but simultaneously on a sequence of n queries, we obtain optimal lower bounds on the communication or space complexity. Lower bounds obtained from our direct sum result show that a number of techniques in the sketching literature are optimal, including the following:

- (JL transform) Lower bound of Omega((1/eps^2) log(n/delta)) on the dimension of (oblivious) Johnson-Lindenstrauss transforms.

- (l_p-estimation) Lower bound for the size of encodings of n vectors in [-M, M]^d that allow l_1 or l_2-estimation of Omega((n/eps^2) log (n/delta) (log d + log M)).

- (Matrix sketching) Lower bound of Omega((1/eps^2) log n/delta) on the dimension of a matrix sketch S satisfying the entrywise guarantee |(ASS^TB)_{i,j} - (AB)_{i,j}| <= eps |A_i|_2 |B^j|_2.

- (Database joins) Lower bound of Omega((n/eps^2) log(n/delta) log M) for sketching frequency vectors of n tables in a database, each with M records, in order to allow join size estimation.

Joint work with David P. Woodruff and Grigory Yaroslavtsev.

Abstract:

Spin systems such as the Ising model originated in statistical physics as a tool for the qualitative study of phase transitions in phenomena like magnetism.  They have since found applications in the modeling of other complex systems. e.g., in the study of social networks and in machine learning.  In this work, we study the computational complexity of computing mean statistics of such models (e.g., the magnetization of the Ising model), and relate these questions to the location of the complex zeros of the "partition function" (a well studied generating polynomial of the probability distribution specified by such a model).

In two seminal papers, Lee and Yang [1952] initiated the study of the zeros of the partition function, and related phase transitions in the Ising model to the location of such zeros. To use this connection, they then proved the striking theorem that the zeros of the partition function of the so-called "ferromagnetic" Ising model lie on the unit circle in the complex plane.  The study of the location of zeros of other classes of polynomials has an even longer history, and also has applications in probability theory and combinatorics.

In this talk, we will briefly survey the Lee-Yang theorem and its connection to phase transitions, and then present our recent extension of the Lee-Yang theorem which has applications to proving the #P-hardness of computing the magnetization of the Ising model. We will also present another example of our method of using results about locations of zeros of polynomials to prove #P-hardness by applying it to the problem of computing the average size of a matching in the monomer-dimer model.

This talk is based on joint work with Alistair Sinclair.