BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//MIT Statistics and Data Science Center - ECPv5.4.0.2//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:MIT Statistics and Data Science Center
X-ORIGINAL-URL:https://stat.mit.edu
X-WR-CALDESC:Events for MIT Statistics and Data Science Center
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20070311T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20071104T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20080309T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20081102T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20090308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20091101T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20100314T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20101107T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20110313T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20111106T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20120311T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20121104T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20130310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20131103T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20140309T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20141102T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20150308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20151101T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20160313T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20161106T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20170312T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20171105T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20180311T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20181104T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20190310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20191103T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20200308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20201101T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20210314T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20211107T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20210421T102540
DTEND;TZID=America/New_York:20210421T102540
DTSTAMP:20210421T102540
CREATED:20180911T181504Z
LAST-MODIFIED:20180911T181504Z
UID:2833-1619000740-1619000740@stat.mit.edu
SUMMARY:Topics in Information and Inference Seminar
DESCRIPTION:This seminar consists of a series of lectures each followed by a period of informal discussion and social. The topics are at the nexus of information theory\, inference\, causality\, estimation\, and non-convex optimization. The lectures are intended to be tutorial in nature with the goal of learning about interesting and exciting topics rather than merely hearing about the most recent results. The topics are driven by the interests of the speakers\, and with the exception of the two lectures on randomness and information\, there is no planned coherence or dependency among them. Ad hoc follow-on meetings about any of the topics presented are highly encouraged.
URL:https://stat.mit.edu/calendar/topics-information-inference-seminar-3/
CATEGORIES:IDSS Special Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20210421T102540
DTEND;TZID=America/New_York:20210421T102540
DTSTAMP:20210421T102540
CREATED:20190130T204126Z
LAST-MODIFIED:20190130T204126Z
UID:3104-1619000740-1619000740@stat.mit.edu
SUMMARY:TAP free energy\, spin glasses\, and vibrational inference
DESCRIPTION:Abstract: We consider the Sherrington-Kirkpatrick model of spin glasses with ferromagnetically biased couplings. For a specific choice of the couplings mean\, the resulting Gibbs measure is equivalent to the Bayesian posterior for a high-dimensional estimation problem known as “Z2 synchronization”. Statistical physics suggests to compute the expectation with respect to this Gibbs measure (the posterior mean in the synchronization problem)\, by minimizing the so-called Thouless-Anderson-Palmer (TAP) free energy\, instead of the mean field (MF) free energy. We prove that this identification is correct\, provided the ferromagnetic bias is larger than a constant (i.e. the noise level is small enough in synchronization). Namely\, we prove that the scaled l_2 distance between any low energy local minimizers of the TAP free energy and the mean of the Gibbs measure vanishes in the large size limit. Our proof technique is based on upper bounding the expected number of critical points of the TAP free energy using the Kac-Rice formula. \nThis is joint work with Song Mei and Andrea Montanari. \nBio: Zhou Fan is an Assistant Professor in the Department of Statistics and Data Science at Yale University. His research interests include random matrix theory\, high dimensional and multivariate statistics\, inference in random graphs and networks\, discrete algorithms\, and applications in genetics and computational biology. Zhou received his Ph.D. in Statistics at Stanford University\, working with Iain M. Johnstone and Andrea Montanari. Prior to this\, Zhou developed statistical and software tools for molecular dynamics simulations at D. E. Shaw Research.
URL:https://stat.mit.edu/calendar/tap-free-energy-spin-glasses-vibrational-inference/
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20071116T110000
DTEND;TZID=America/New_York:20071116T120000
DTSTAMP:20210421T102540
CREATED:20200113T212627Z
LAST-MODIFIED:20200113T212627Z
UID:3947-1195210800-1195214400@stat.mit.edu
SUMMARY:Exponential Error Bounds for Random Codes on the BSC
DESCRIPTION:Abstract: \nOne of Shannon’s earliest results was his determination of the capacity of the binary symmetric channel (BSC). Shannon went on to show that\, with randomly chosen codes and optimal decoding\, the probability of decoding error decreases exponentially for any transmission rate less than capacity. Much of the important early work of Shannon\, Elias\, Fano and Gallager was devoted to determining bounds on the corresponding “error exponent.” A later approach to this problem\, pioneered by Csiszar and Korner\, and now adopted in many modern information theory courses such as 6.441\, determines error exponents using large-deviation theory. This approach has several advantages: (a) It can be remarkably simple and intuitive; (b) It gives correct error exponents\, not just bounds; (c) It gives insight into how decoding errors typically occur. We illustrate this approach by developing the correct error exponents at all rates for both random codes and random linear codes on the BSC\, assuming optimal decoding. We discuss how decoding errors typically occur. In particular\, we show why the classical algebraic coding approach never had any hope of approaching channel capacity\, even on the BSC. This talk is intended to be pitched at an elementary and tutorial level.
URL:https://stat.mit.edu/calendar/exponential-error-bounds-for-random-codes-on-the-bsc-2/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20080229T110000
DTEND;TZID=America/New_York:20080229T120000
DTSTAMP:20210421T102540
CREATED:20200110T203644Z
LAST-MODIFIED:20200110T203644Z
UID:3935-1204282800-1204286400@stat.mit.edu
SUMMARY:Quantile and Probability Curves without Crossing
DESCRIPTION:The most common approach to estimating conditional quantile curves is to fit a curve\, typically linear\, pointwise for each quantile. Linear functional forms\, coupled with pointwise fitting\, are used for a number of reasons including parsimony of the resulting approximations and good computational properties. The resulting fits\, however\, may not respect a logical monotonicity requirement — that the quantile curve be increasing as a function of probability. This paper studies the natural monotonization of these empirical curves induced by sampling from the estimated non-monotone model\, and then taking the resulting conditional quantile curves that by construction are monotone in the probability. This construction of monotone quantile curves may be seen as a bootstrap and also as a monotonic rearrangement of the original non-monotone function. It is shown that the monotonized curves are closer to the true curves in finite samples\, for any sample size. Under correct specification\, the rearranged conditional quantile curves have the same asymptotic distribution as the original non-monotone curves. Under misspecification\, however\, the asymptotics of the rearranged curves may partially differ from the asymptotics of the original non-monotone curves. An analogous procedure is developed to monotonize the estimates of conditional distribution functions. The results are derived by establishing the compact (Hadamard) differentiability of the monotonized quantile and probability curves with respect to the original curves in discontinuous directions\, tangentially to a set of continuous functions. In doing so\, the compact differentiability of the rearrangement-related operators is established.
URL:https://stat.mit.edu/calendar/quantile-and-probability-curves-without-crossing-2/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20080321T110000
DTEND;TZID=America/New_York:20080321T120000
DTSTAMP:20210421T102541
CREATED:20200110T203317Z
LAST-MODIFIED:20200110T203317Z
UID:3936-1206097200-1206100800@stat.mit.edu
SUMMARY:Fragility of Asymptotic Agreement under Bayesian Learning
DESCRIPTION:One of Shannon’s earliest results was his determination of the capacity of the binary symmetric channel (BSC). Shannon went on to show that\, with randomly chosen codes and optimal decoding\, the probability of decoding error decreases exponentially for any transmission rate less than capacity. Much of the important early work of Shannon\, Elias\, Fano and Gallager was devoted to determining bounds on the corresponding “error exponent.” A later approach to this problem\, pioneered by Csiszar and Korner\, and now adopted in many modern information theory courses such as 6.441\, determines error exponents using large-deviation theory. This approach has several advantages: (a) It can be remarkably simple and intuitive; (b) It gives correct error exponents\, not just bounds; (c) It gives insight into how decoding errors typically occur. We illustrate this approach by developing the correct error exponents at all rates for both random codes and random linear codes on the BSC\, assuming optimal decoding. We discuss how decoding errors typically occur. In particular\, we show why the classical algebraic coding approach never had any hope of approaching channel capacity\, even on the BSC. This talk is intended to be pitched at an elementary and tutorial level.
URL:https://stat.mit.edu/calendar/fragility-of-asymptotic-agreement-under-bayesian-learning-2/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20080410T110000
DTEND;TZID=America/New_York:20080410T110000
DTSTAMP:20210421T102541
CREATED:20191220T214309Z
LAST-MODIFIED:20191223T171242Z
UID:3723-1207825200-1207825200@stat.mit.edu
SUMMARY:Bounds on Stationary Expectations for Markov Processes
DESCRIPTION:Many performance engineering and operations research modeling formulations lead to Markov models in which the key performance measure is an expectation defined in terms of the stationary distribution of the process. In models of realistic complexity\, it is often difficult to compute such expectations in closed form. In this talk\, we will discuss a simple class of bounds for such stationary expectations\, and describe some of the mathematical subtleties that arise in making rigorous such bounds. We will also discuss how such bounds can be used algorithmically. This work is joint with Denis Saure and Assaf Zeevi.
URL:https://stat.mit.edu/calendar/bounds-on-stationary-expectations-for-markov-processes/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20080418T110000
DTEND;TZID=America/New_York:20080418T110000
DTSTAMP:20210421T102541
CREATED:20191220T214309Z
LAST-MODIFIED:20191223T171242Z
UID:3722-1208516400-1208516400@stat.mit.edu
SUMMARY:Large deviations for random walks under subexponentiality: the big-jump domain
DESCRIPTION:Stimulated by applications to internet traffic modeling and insurance mathematics\, distributions with heavy tails have been widely studied over the past decades. This talk addresses a fundamental large-deviation problem for random walks with heavy-tailed step-size distributions. We consider so-called subexponential step-size distributions\, which constitute the most widely-used class of heavy-tailed distributions. I will present a theory to study sequences {x_n} for which P{S_n>x_n} behaves asymptotically like n P {S_1>x_n} for large n. (joint work with D. Denisov and V. Shneer)
URL:https://stat.mit.edu/calendar/large-deviations-for-random-walks-under-subexponentiality-the-big-jump-domain/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20080425T110000
DTEND;TZID=America/New_York:20080425T110000
DTSTAMP:20210421T102541
CREATED:20191220T214309Z
LAST-MODIFIED:20191223T171241Z
UID:3721-1209121200-1209121200@stat.mit.edu
SUMMARY:Quantum Computation by Adiabatic Evolution
DESCRIPTION:The quantum adiabatic algorithm is a general approach to solving combinatorial search problems using a quantum computer. It will succeed if the run time is long enough. I will discuss how this algorithm works and our current understanding of the required run time.
URL:https://stat.mit.edu/calendar/quantum-computation-by-adiabatic-evolution/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20080523T110000
DTEND;TZID=America/New_York:20080523T110000
DTSTAMP:20210421T102541
CREATED:20191220T214308Z
LAST-MODIFIED:20191223T171241Z
UID:3720-1211540400-1211540400@stat.mit.edu
SUMMARY:The Gaussian random walk\, sampling Brownian motion\, and the Riemann zeta function
DESCRIPTION:We consider the Gaussian random walk (one-dimensional random walk with normally distributed increments)\, and in particular the moments of its maximum M. Explicit expressions for all moments of M are derived in terms of Taylor series with coefficients that involve the Riemann zeta function. We build upon the work of Chang and Peres (1997) on P(M=0) and Bateman’s formulas on Lerch’s transcendent. Our result for E(M) completes earlier work of Kingman (1965)\, Siegmund (1985)\, and Chang and Peres (1997). The maximum M shows up in a range of applications\, such as sequentially testing for the drift of a Brownian motion\, corrected diffusion approximations\, simulation of Brownian motion\, option pricing\, thermodynamics of a polymer chain\, and queueing systems in heavy traffic. Some of these applications are discussed\, as well as several issues open for further research. This talk is based on joint work with A.J.E.M. Janssen.
URL:https://stat.mit.edu/calendar/the-gaussian-random-walk-sampling-brownian-motion-and-the-riemann-zeta-function/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20080923T110000
DTEND;TZID=America/New_York:20080923T110000
DTSTAMP:20210421T102541
CREATED:20191220T214308Z
LAST-MODIFIED:20191223T171241Z
UID:3719-1222167600-1222167600@stat.mit.edu
SUMMARY:Convergence of unitary matrix integrals
DESCRIPTION:We introduce the unitary Schwinger-Dyson equation associated to a selfadjoint polynomial potential V. The V=0 case corresponds to the free product state\, so the Schwinger-Dyson equation can be considered as a deformation of free probability. We show that the solutions of this equation are unique for small V’s and correspond to a large N limit of a multi-matrix model. This technique allows to show that a wide class of unitary and orthogonal multi-matrix models converge asymptotically. We also give a combinatorial and analytic description of the limit\, solving a series of open questions raised in theoretical physics in the late 70’s. This is joint work with A. Guionnet and E. Maurel-Segala.
URL:https://stat.mit.edu/calendar/convergence-of-unitary-matrix-integrals/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20090313T110000
DTEND;TZID=America/New_York:20090313T110000
DTSTAMP:20210421T102541
CREATED:20191220T214308Z
LAST-MODIFIED:20191223T171240Z
UID:3718-1236942000-1236942000@stat.mit.edu
SUMMARY:Sequential algorithms for generating random graphs
DESCRIPTION:Large-scale complex networks have been the objects of study for the past two decades\, and one central problem have been constructing or designing realistic models for such networks. This problem appears in a variety of applications including coding theory and systems biology. Unfortunately\, the existing algorithms for this problem have large running times\, making them impractical to use for networks with millions of links. We will present a technique to design an almost linear time algorithm for generating random graphs with given degree sequences for a range of degrees. Next\, we extend the analysis to design an algorithm for efficiently generating random graphs without short cycles. These algorithms can be used for constructing high performance low-density parity-check codes (LDPC codes). Based on joint works with Jeong Han Kim\, Andrea Montanari\, and Amin Saberi.
URL:https://stat.mit.edu/calendar/sequential-algorithms-for-generating-random-graphs/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20090403T110000
DTEND;TZID=America/New_York:20090403T110000
DTSTAMP:20210421T102541
CREATED:20191220T214307Z
LAST-MODIFIED:20191223T171240Z
UID:3717-1238756400-1238756400@stat.mit.edu
SUMMARY:A New Look at the Compound Poisson Distribution and Compound Poisson Approximation using Entropy
DESCRIPTION:We develop an information-theoretic foundation for compound Poisson approximation and limit theorems (analogous to the corresponding developments for the central limit theorem and for simple Poisson approximation). First\, su?cient conditions are given under which the compound Poisson distribution has maximal entropy within a natural class of probability measures on the nonnegative integers. In particular\, it is shown that a maximum entropy property is valid if the measures under consideration are log-concave\, but that it fails in general. Second\, approximation bounds in the (strong) relative entropy sense are given for distributional approximation of sums of independent nonnegative integer valued random variables by compound Poisson distributions. The proof techniques involve the use of a notion of local information quantities that generalize the classical Fisher information used for normal approximation\, as well as the use of ingredients from Stein’s method for compound Poisson approximation. This work is joint with Andrew Barbour (Zurich)\, Oliver Johnson (Bristol) and Ioannis Kontoyiannis (AUEB).
URL:https://stat.mit.edu/calendar/a-new-look-at-the-compound-poisson-distribution-and-compound-poisson-approximation-using-entropy/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20090410T110000
DTEND;TZID=America/New_York:20090410T110000
DTSTAMP:20210421T102542
CREATED:20191220T214307Z
LAST-MODIFIED:20191223T171239Z
UID:3716-1239361200-1239361200@stat.mit.edu
SUMMARY:Fractional simple random walk
DESCRIPTION:Fractional Brownian motions are the most natural generalizations of ordinary (one-dimensional) Brownian motions that allow for some amount of long range dependence (a.k.a. “momentum effects”). They are sometimes used in mathematical finance as models for logarithmic asset prices. We describe some natural random simple walks on the integers that have fractional Brownian motion as a scaling limit. In a sense\, these walks are the most natural discrete analogs of fractional Brownian motion.
URL:https://stat.mit.edu/calendar/fractional-simple-random-walk/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20090417T110000
DTEND;TZID=America/New_York:20090417T110000
DTSTAMP:20210421T102542
CREATED:20191220T214307Z
LAST-MODIFIED:20191223T171239Z
UID:3715-1239966000-1239966000@stat.mit.edu
SUMMARY:The Smoothed Linear Program for Approximate Dynamic Programming
DESCRIPTION:We present a novel linear program for the approximation of the dynamic programming value function in high-dimensional stochastic control problems. LP approaches to approximate DP naturally restrict attention to approximations that\, depending on the context\, are upper or lower bounds to the optimal value function. Our program — the `smoothed LP’ — relaxes this restriction in an appropriate fashion while remaining computationally tractable. Doing so appears to have several advantages: o We demonstrate superior bounds on the quality of approximation to the optimal value function afforded by our approach. o Experiments with our approach on a challenging problem (the game of Tetris) show that the approach outperforms a variety of approximate DP algorithms (including the LP approach\, TD-learning and policy gradient methods) by a significant margin. Joint work with Vijay Desai and Ciamac Moallemi (Columbia).
URL:https://stat.mit.edu/calendar/the-smoothed-linear-program-for-approximate-dynamic-programming/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20090501T110000
DTEND;TZID=America/New_York:20090501T110000
DTSTAMP:20210421T102542
CREATED:20191220T214307Z
LAST-MODIFIED:20191223T171239Z
UID:3714-1241175600-1241175600@stat.mit.edu
SUMMARY:On Resolution\, Sparse Signal Recovery\, and Random Access Communication
DESCRIPTION:Resolution of a data acquisition system is usually thought to be determined completely by sensing properties\, such as density and accuracy of measurements. This talk advocates the view that resolution is\, in addition\, dependent on signal modeling and the complexity of computations allowed. This view is developed concretely for the acquisition of sparse signals\, where the asymptotic relationship between resolution and the number of measurements is studied for algorithms with various complexities. The sparse signal recovery problem corresponds perfectly to a model of random multiple access communication in which the task of the receiver is to determine only the subset of the users that transmitted. This connection gives insight on the performance of single- and multi-user detection algorithms. Specifically\, all known practical multiuser detection techniques become interference limited at high SNR. However\, power control is natural in the multiple access setting\, and we are able to prove that a simple detection algorithm based on orthogonal matching pursuit is not interference limited under optimal power control. The talk is based on joint work with Alyson Fletcher and Sundeep Rangan.
URL:https://stat.mit.edu/calendar/on-resolution-sparse-signal-recovery-and-random-access-communication/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20111007T110000
DTEND;TZID=America/New_York:20111007T110000
DTSTAMP:20210421T102542
CREATED:20191220T214306Z
LAST-MODIFIED:20191223T171238Z
UID:3713-1317985200-1317985200@stat.mit.edu
SUMMARY:Asymptotics for preferential attachment random graphs via Stein's method
DESCRIPTION:Preferential attachment random graphs evolve in time by sequentially adding vertices and edges randomly so that connections to vertices having high degree are favored. There has been an explosion of research on these models since Barabasi and Albert popularized them in 1999 to explain the so-called power law behavior observed in real networks such as the graph of the Internet where Web pages correspond to vertices and hyperlinks between them correspond to edges. In this talk we will show how to derive rates of convergence for the distribution of the degree of a fixed vertex to its distributional limit using a new variation of Stein’s method that relies on finding couplings to motivate distributional transformations for which limit distributions are fixed points. Surprisingly little is known about these limit distributions despite the large literature on such graphs.
URL:https://stat.mit.edu/calendar/asymptotics-for-preferential-attachment-random-graphs-via-steins-method/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20111021T110000
DTEND;TZID=America/New_York:20111021T110000
DTSTAMP:20210421T102542
CREATED:20191220T214306Z
LAST-MODIFIED:20191223T171238Z
UID:3712-1319194800-1319194800@stat.mit.edu
SUMMARY:Does god play dice? An I/O scheduling and airplane boarding perspective
DESCRIPTION:Given N I/O requests to a disk drive\, how long will it take the disk drive to service them? How long does it take to board an airplane? We will show that such questions are modeled by the same math that models the universe in relativity theory\, namely\, space-time (Lorentzian) geometry.As a result of this connection we will try to understand what is the best way to service I/O\, what is the best airplane boarding policy and what makes free falling bodies take the trajectories that they do. On the way we may also encounter a silly card game and random matrices. The talk is self contained\, experience with boarding an airplane is helpful. \nSpeaker Bio: Eitan Bachmat is a senior lecturer at the Computer Science department of Ben-Gurion U. He received his PhD in mathematics from M.I.T. He works mostly on the design of storage systems\, performance analysis and applied probability. He also consults to the storage industry and participated in the development of several commercially available systems. Consequently\, he has more patents than academic papers.
URL:https://stat.mit.edu/calendar/does-god-play-dice-an-i-o-scheduling-and-airplane-boarding-perspective/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20111216T110000
DTEND;TZID=America/New_York:20111216T110000
DTSTAMP:20210421T102542
CREATED:20191220T214306Z
LAST-MODIFIED:20191223T171238Z
UID:3711-1324033200-1324033200@stat.mit.edu
SUMMARY:Delay optimality in switched networks
DESCRIPTION:We consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time\, based on the current state or past history of the system. In the main result\, we provide a new class of online scheduling policies that achieve optimal average queue-size scaling for a class of switched networks including input-queued switches. In particular\, it establishes the validity of a conjecture about optimal queue-size scaling for input-queued switches. \nSpeaker Bio: Yuan Zhong is a doctoral candidate in the Operations Research Center at MIT\, under the supervision of Devavrat Shah and John Tsitsiklis. He has a BA degree in Mathematics from University of Cambridge\, and a MA degree in Mathematics from California Institute of Technology. He is broadly interested in stochastic modeling and analysis\, as well as their applications in various business and engineering domains.
URL:https://stat.mit.edu/calendar/delay-optimality-in-switched-networks/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20120320T110000
DTEND;TZID=America/New_York:20120320T110000
DTSTAMP:20210421T102542
CREATED:20191220T214306Z
LAST-MODIFIED:20191223T171237Z
UID:3710-1332241200-1332241200@stat.mit.edu
SUMMARY:Van der Warden Number and Coloring of Hypergraphs with Large Girth
DESCRIPTION:The talk is devoted to the classical problem of estimating the Van der Waerden number $W(n\,r)$. The famous Van der Waerden theorem states that\, for any integers $nge 3$\, $rge 2$\, there exists the smallest integer $W(n\,r)$ such that\, for every $Nge W(n\,r)$\, in any $r$-coloring of the set ${1\,2\,ldots\,N}$ there exists a monochromatic arithmetic progression of length $n$. The best upper bound for $W(n\,r)$ in the general case was obtained by W.T. Gowers in 2001 who proved thatW(n\,r)≤22r22n+9.\nOur talk is concentrated on the lower bounds for the Van der Waerden number. We shall show that lower estimates for $W(n\,r)$ are closely connected with extremal problems concerning colorings of uniform hypergraphs with large girth. Our main result is a new lower bound for $W(n\,r)$:\nW(n\,r)≥crn−1lnn\,\nwhere $c>0$ is an absolute constant. The proof is based on a continuous-time random recoloring process.
URL:https://stat.mit.edu/calendar/van-der-warden-number-and-coloring-of-hypergraphs-with-large-girth/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20120326T110000
DTEND;TZID=America/New_York:20120326T110000
DTSTAMP:20210421T102543
CREATED:20191220T214305Z
LAST-MODIFIED:20191223T171237Z
UID:3706-1332759600-1332759600@stat.mit.edu
SUMMARY:Research Groups at Yandex and Moscow Institute of Physics and Technology
DESCRIPTION:In my talk I will present our research groups in Yandex which is the main search engine in Russia\, and Moscow Institute of Physics and Technology which is a kind of Russian MIT.
URL:https://stat.mit.edu/calendar/research-groups-at-yandex-and-moscow-institute-of-physics-and-technology/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20120327T110000
DTEND;TZID=America/New_York:20120327T110000
DTSTAMP:20210421T102543
CREATED:20191220T214305Z
LAST-MODIFIED:20191223T171237Z
UID:3707-1332846000-1332846000@stat.mit.edu
SUMMARY:Web Graph Models and Their Applications
DESCRIPTION:In the past 20 years\, there has been a lot of work concerning modeling real networks such as Internet\, WWW\, social networks\, biological networks\, etc. In our talk\, we will mainly concentrate on models devoted to incorporating properties of the web graph. We will give a survey of different such models including those of Bollob’as–Riordan\, Buckley–Osthus\, Cooper–Frieze\, etc. We will also present some new related mathematical results obtained by our group in Yandex\, Moscow Institute of Physics and Technology\, Moscow State University. Finally\, we will discuss some applications of these results to ranking as well as some future research directions.
URL:https://stat.mit.edu/calendar/web-graph-models-and-their-applications/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20120328T110000
DTEND;TZID=America/New_York:20120328T110000
DTSTAMP:20210421T102543
CREATED:20191220T214305Z
LAST-MODIFIED:20191223T171237Z
UID:3708-1332932400-1332932400@stat.mit.edu
SUMMARY:Conditional Coding with Limiting Computational Resources
DESCRIPTION:Consider the following situation. Alice knows string x and Bob knows string y. There is a limited capacity information channel from Alice to Bob. Alice wants to transmit a message that is sufficient for Bob to recover x. What is a minimum capacity that allows her to do it? Obviously\, there is a theoretical minimum: the amount of information in x that is not contained in y. Astonishing enough\, this is a precise estimate: Alice can produce an optimal code even though she does not know what information Bob already possesses. In Shannon entropy framework this fact is stated as Slepian-Wolf theorem. In Kolmogorov complexity framework (where both Alice and Bob use computable functions and logarithmic advice) it was proven by Muchnik. In the talk we will give another proof of Muchnik’s result and extend it to space-bounded case\, where Alice and Bob use space-bounded computations and advice is still logarithmic.
URL:https://stat.mit.edu/calendar/conditional-coding-with-limiting-computational-resources/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20120329T110000
DTEND;TZID=America/New_York:20120329T110000
DTSTAMP:20210421T102543
CREATED:20191220T214306Z
LAST-MODIFIED:20191223T171237Z
UID:3709-1333018800-1333018800@stat.mit.edu
SUMMARY:An Application of Talagrand's Inequality to Prove a Concentration of Second Degrees in Buckley-Osthus Random Graph Model
DESCRIPTION:We consider the random graph model $H_{a\,m}^n$. An explicit construction of this model was suggested by Buckley and Osthus. For any fixed positive integer $m$ and positive real $a$ we define a random graph $H_{a\,m}^n$ in the following way. The graph $H_{a\,1}^1$ consists of one vertex and one loop. Given a graph $H_{a\,1}^{t-1}$ we transform it into $H_{a\,1}^{t}$ by adding one new vertex and one new random edge $(t\,i)$\, where $i in {1\, dots\, t }$ and $Prob(i=t) = frac{a}{(a+1)t-1}$\, $Prob(i=s) = frac{d_{H_{a\,1}^{t-1}}(s) – 1 + a}{(a+1)t-1}$ if $1 le s le t-1$. To construct $H_{a\,m}^n$ with $m>1$ we start from $H_{a\,1}^{mn}$. Then we identify the vertices $1\, dots\, m$ to form the first vertex; we identify the vertices $m+1\, dots\, 2m$ to form the second vertex\, etc. \nThe Buckley and Osthus random graph is a model of real-world networks. The parameter $a$ is called an “initial attractiveness” of a vertex. It was shown (by Buckley and Osthus for integer $a$ and by Grechnikov for real $a$) that the degree sequence in this model follows a power law distribution with exponent $-2-a$. We study second degrees of vertices in $H_{a\,m}^n$. By the second degree of $t$ we mean the number of edges adjacent to the neighbors of $t$ except for the edges adjacent to the vertex $t$. Second degree of a vertex is an approximation of the PageRank. We show that the distribution of second degrees in $H_{a\,1}^n$ follows a power law with exponent $-1-a$. \nProof of this result consists of two parts. The first step is to calculate the expectation of the number of vertices with second degree $k$ and the second step is to obtain a concentration. I will talk about the second step. It is a non-trivial application of Talagrand’s inequality. Instead of Talagrand’s inequality it is possible to apply Azuma’s inequality\, but the result will be weaker.
URL:https://stat.mit.edu/calendar/an-application-of-talagrands-inequality-to-prove-a-concentration-of-second-degrees-in-buckley-osthus-random-graph-model/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20120420T110000
DTEND;TZID=America/New_York:20120420T110000
DTSTAMP:20210421T102543
CREATED:20191220T214304Z
LAST-MODIFIED:20191223T171236Z
UID:3705-1334919600-1334919600@stat.mit.edu
SUMMARY:Information theory of DNA sequencing
DESCRIPTION:DNA sequencing is the basic workhorse of modern biology and medicine. Shotgun sequencing is the dominant technique used: many randomly located short fragments called reads are extracted from the DNA sequence\, and these reads are assembled to reconstruct the original DNA sequence. Despite major effort by the research community\, the DNA sequencing problem remains unresolved from a practical perspective: it is currently not known how to produce a good assembly of most read data-sets. \nBy drawing an analogy between the DNA sequencing problem and the classic communication problem\, we define an information theoretic notion of sequencing capacity. This is the maximum number of DNA base pairs that can be resolved reliably per read\, and provides a fundamental limit to the performance that can be achieved by any assembly algorithm. We compute the sequencing capacity explicitly assuming an IID model for the DNA sequence and a noiseless read process. These basic results are then partially extended to arbitrary DNA sequences: the capacity is determined by a simple sufficient statistic of the sequence which can be computed for actual genomes. \nThe talk is based on joint works with Ma’ayan Bresler\, Abolfazl Motahari\, and David Tse. \nSpeaker Bio: Guy Bresler is currently a PhD candidate in the Department of Electrical Engineering and Computer Sciences at the University of California\, Berkeley. Prior to that\, he received the B.S. degree in electrical and computer engineering and the M.S. degree in mathematics from the University of Illinois at Urbana-Champaign\, both in 2006. Guy is the recipient of an NSF Graduate Research Fellowship\, a Vodafone Graduate Fellowship\, the Barry M. Goldwater Scholarship\, a Vodafone Undergraduate Scholarship\, the E.C. Jordan Award from the ECE department at UIUC\, and the Roberto Padovani Scholarship from Qualcomm. His research interests include information theory\, applied probability\, and computational biology.
URL:https://stat.mit.edu/calendar/information-theory-of-dna-sequencing/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20120427T110000
DTEND;TZID=America/New_York:20120427T110000
DTSTAMP:20210421T102543
CREATED:20191220T214303Z
LAST-MODIFIED:20191223T171235Z
UID:3703-1335524400-1335524400@stat.mit.edu
SUMMARY:The Coherence Phase Transition
DESCRIPTION:We study particle systems corresponding to highly connected queueing networks. We examine the validity of the so-called Poisson Hypothesis (PH)\, which predicts that the Markov process\, describing the evolution of such particle system\, started from a reasonable initial state\, approaches the equilibrium in time independent of the size of the network. \nThis is indeed the case in many situations. However\, there are networks for which the relaxation process slows down. This behavior reflects the fact that the corresponding infinite system undergoes a phase transition. It is characterized by the property that different nodes of the network start to evolve in a synchronous way. \nSuch transition can happen only when the load per node exceeds some critical value\, while in the low load situation the PH behavior holds. The load thus plays here the same role as the inverse temperature in statistical mechanics. \nWe will mention a related open problem of ergodicity of interacting particle systems with unique stationary state. \nThe talk is based on joint works with A. Rybko and A. Vladimirov.
URL:https://stat.mit.edu/calendar/the-coherence-phase-transition/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20120427T110000
DTEND;TZID=America/New_York:20120427T110000
DTSTAMP:20210421T102543
CREATED:20191220T214304Z
LAST-MODIFIED:20191223T171236Z
UID:3704-1335524400-1335524400@stat.mit.edu
SUMMARY:Mean-field Limit for General Queueing Networks on Infinite Graphs
DESCRIPTION:We study the sequences of Markov processes defining the evolution of a general symmetric queueng network with the number of nodes tending to infinity. These sequences have limits which are nonlinear Markov processes. Time evolution of these nonlinear Markov processes are sometimes simpler and easier to analyze than the evolution of corresponding prelimit Markov processes on finite graphs. This fact give the possibility to find good approximation for the behavior of symmetric queueing networks on large graphs. Examples will be discussed. \nThe talk is based on a joint work with S. Shlosman.
URL:https://stat.mit.edu/calendar/mean-field-limit-for-general-queueing-networks-on-infinite-graphs/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20120518T110000
DTEND;TZID=America/New_York:20120518T110000
DTSTAMP:20210421T102543
CREATED:20191220T214302Z
LAST-MODIFIED:20191223T171235Z
UID:3702-1337338800-1337338800@stat.mit.edu
SUMMARY:Growth of random surfaces
DESCRIPTION:The goal of the talk is to describe a class of solvable random growth models of one and two-dimensional interfaces. The growth is local (distant parts of the interface grow independently)\, it has a smoothing mechanism (fractal boundaries do not appear)\, and the speed of growth depends on the local slope of the interface. \nThe models enjoy a rich algebraic structure that is reflected through closed determinantal formulas for the correlation functions. Large time asymptotic analysis of such formulas reveals asymptotic features of the emerging interface in different scales. Macroscopically\, a deterministic limit shape phenomenon can be observed. Fluctuations around the limit shape range from universal laws of Random Matrix Theory to conformally invariant Gaussian processes in the plane. On the microscopic (lattice) scale\, certain universal determinantal random point processes arise. \nNo preliminary knowledge of the material will be assumed.
URL:https://stat.mit.edu/calendar/growth-of-random-surfaces/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20121026T110000
DTEND;TZID=America/New_York:20121026T110000
DTSTAMP:20210421T102544
CREATED:20191220T214302Z
LAST-MODIFIED:20191223T171235Z
UID:3701-1351249200-1351249200@stat.mit.edu
SUMMARY:Optimal detection of a sparse principal component
DESCRIPTION:Sparse Principal Component Analysis (SPCA) is a remarkably useful tool for practitioners who had been relying on ad-hoc thresholding methods. Our analysis aims at providing a a framework to test whether the data at hand indeed contains a sparse principal component. More precisely we propose an optimal test procedure to detect the presence of a sparse principal component in a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse eigenvalue statistic. Alas\, computing this test is known to be NP-complete in general and we describe a computationally efficient alternative test using convex relaxations. Our relaxation is also proved to detect sparse principal components at near optimal detection levels and performs very well on simulated datasets. Moreover\, we exhibit some evidence from average case complexity that this slight deterioration may be unavoidable.
URL:https://stat.mit.edu/calendar/optimal-detection-of-a-sparse-principal-component/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20121116T110000
DTEND;TZID=America/New_York:20121116T110000
DTSTAMP:20210421T102544
CREATED:20191220T214302Z
LAST-MODIFIED:20191223T171235Z
UID:3700-1353063600-1353063600@stat.mit.edu
SUMMARY:Queueing system topologies with limited flexibility
DESCRIPTION: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) l n). In particular\, when d(n) gg 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-> ∞. 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.
URL:https://stat.mit.edu/calendar/queueing-system-topologies-with-limited-flexibility/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20121130T110000
DTEND;TZID=America/New_York:20121130T110000
DTSTAMP:20210421T102544
CREATED:20191220T214302Z
LAST-MODIFIED:20191223T171234Z
UID:3699-1354273200-1354273200@stat.mit.edu
SUMMARY:Low-rank Matrix Completion: Statistical Models and Large Scale Algorithms
DESCRIPTION:Low-rank matrix regularization is an important area of research in statistics and machine learning with a wide range of applications. For example\, in the context of Missing data imputation arising in recommender systems (e.g. the Netflix Prize)\, DNA microarray and audio signal processing\, among others\, the object of interest is a matrix (X) for which the training data comprises of a few noisy linear measurements. The task is to estimate X\, under a low rank constraint and possibly additional affine constraints on X. In practice\, the matrix dimensions frequently range from hundreds of thousands to even a million — leading to severe computational challenges. In this talk\, I will describe computationally tractable models and scalable (convex) optimization based algorithms for a class of low-rank regularized problems. Exploiting problem-specific statistical insights\, problem structure and using novel tools for large scale SVD computations play important roles in this task. This is joint work with Trevor Hastie\, Rob Tibshirani and Dennis Sun (Stanford Statistics).
URL:https://stat.mit.edu/calendar/low-rank-matrix-completion-statistical-models-and-large-scale-algorithms/
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
END:VCALENDAR