[Theory] NOW: 11/7 Young Researcher Seminar Series: June Vuong, Stanford
Mary Marre
mmarre at ttic.edu
Mon Nov 7 14:58:00 CST 2022
*(PLEASE NOTE SPECIAL TIME!)*
*When:* Monday, November 7th at *3 **pm CT *
*Where: *Talk will be given *live, in-person* at
TTIC, 6045 S. Kenwood Avenue
5th Floor, Room 530
*Virtually:* via Panopto (*livestream*
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=72b5485e-fb43-4971-9a37-af3f0167d327>
)
*Who: * June Vuong, Stanford University
------------------------------
*Title:* Optimal Sublinear Sampling of Spanning Trees and Determinantal
Point Processes via Average-Case Entropic Independence
*Abstract: *We design fast algorithms for repeatedly sampling from strongly
Rayleigh distributions, which include as special cases random spanning tree
distributions and determinantal point processes. For a graph G=(V, E), we
show how to approximately sample uniformly random spanning trees from G in
$O(| V | log ^2 |V|) time per sample after an initial $O(|E| polylog |E|)$
time preprocessing. This is the first nearly-linear runtime in the output
size, which is clearly optimal. For a determinantal point process on
k-sized subsets of a ground set of n elements, defined via an nxn kernel
matrix, we show how to approximately sample in $\tilde{O}(k^\omega)$ time
after an initial $\tilde{O}(nk^{\omega-1})$ time preprocessing, where
$\omega<2.372864$ is the matrix multiplication exponent. The time to
compute just the weight of the output set is roughly $k^\omega$, a natural
barrier that suggests our runtime might be optimal for determinantal point
processes as well. As a corollary, we even improve the state of the art for
obtaining a single sample from a determinantal point process, from the
prior runtime of $\tilde{O}(\min\{nk^2, n^\omega\})$ to
$\tilde{O}(nk^{\omega-1})$.
In our main technical result, we achieve the optimal limit on domain
sparsification for strongly Rayleigh distributions. In domain
sparsification, sampling from a distribution $\mu$ on $\binom{[n]}{k}$ is
reduced to sampling from related distributions on $\binom{[t]}{k}$ for $t
\leq n$. We show that for strongly Rayleigh distributions, the domain size
can be reduced to nearly linear in the output size $t=\tilde{O}(k)$,
improving the state of the art from $t= \tilde{O}(k^2)$ for general
strongly Rayleigh distributions and the more specialized
$t=\tilde{O}(k^{1.5})$ for spanning tree distributions. Our reduction
involves sampling from $\tilde{O}(1)$ domain-sparsified distributions, all
of which can be produced efficiently assuming approximate overestimates for
marginals of $\mu$ are known and stored in a convenient data structure.
Having access to marginals is the discrete analog of having access to the
mean and covariance of a continuous distribution, or equivalently knowing
``isotropy'' for the distribution, the key behind optimal samplers in the
continuous setting based on the famous Kannan-Lov\'asz-Simonovits (KLS)
conjecture. We view our result as analogous in spirit to the KLS conjecture
and its consequences for sampling, but rather for discrete strongly
Rayleigh measures.
Joint work with Nima Anari and Yang P. Liu. To appear in FOCS 2022.
Arxiv link [2204.02570v1] Optimal Sublinear Sampling of Spanning Trees and
Determinantal Point Processes via Average-Case Entropic Independence
(arxiv.org) <https://arxiv.org/abs/2204.02570v1>
*Host: Madhur Tulsiani <madhurt at ttic.edu>*
**************************************************************************************************
The *TTIC Young Researcher Seminar Series* (
http://www.ttic.edu/young-researcher.php) features talks by Ph.D. students
and postdocs whose research is of broad interest to the computer science
community. The series provides an opportunity for
early-career researchers to present recent work to and meet with students
and faculty at TTIC and nearby universities.
The seminars are typically held on Wednesdays at 10:30am in TTIC Room 530.
For additional information, please contact *David McAllester *(
mcallester at ttic.edu).
Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Chicago, IL 60637*
*mmarre at ttic.edu <mmarre at ttic.edu>*
On Mon, Nov 7, 2022 at 1:51 PM Mary Marre <mmarre at ttic.edu> wrote:
> *(PLEASE NOTE SPECIAL TIME!)*
>
> *When:* Monday, November 7th at *3 **pm CT *
>
>
> *Where: *Talk will be given *live, in-person* at
>
> TTIC, 6045 S. Kenwood Avenue
>
> 5th Floor, Room 530
>
>
> *Virtually:* via Panopto (*livestream*
> <https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=72b5485e-fb43-4971-9a37-af3f0167d327>
> )
>
>
> *Who: * June Vuong, Stanford University
>
>
> ------------------------------
>
> *Title:* Optimal Sublinear Sampling of Spanning Trees and Determinantal
> Point Processes via Average-Case Entropic Independence
> *Abstract: *We design fast algorithms for repeatedly sampling from
> strongly Rayleigh distributions, which include as special cases random
> spanning tree distributions and determinantal point processes. For a graph
> G=(V, E), we show how to approximately sample uniformly random spanning
> trees from G in $O(| V | log ^2 |V|) time per sample after an initial
> $O(|E| polylog |E|)$ time preprocessing. This is the first nearly-linear
> runtime in the output size, which is clearly optimal. For a determinantal
> point process on k-sized subsets of a ground set of n elements, defined via
> an nxn kernel matrix, we show how to approximately sample in
> $\tilde{O}(k^\omega)$ time after an initial $\tilde{O}(nk^{\omega-1})$ time
> preprocessing, where $\omega<2.372864$ is the matrix multiplication
> exponent. The time to compute just the weight of the output set is roughly
> $k^\omega$, a natural barrier that suggests our runtime might be optimal
> for determinantal point processes as well. As a corollary, we even improve
> the state of the art for obtaining a single sample from a determinantal
> point process, from the prior runtime of $\tilde{O}(\min\{nk^2,
> n^\omega\})$ to $\tilde{O}(nk^{\omega-1})$.
>
> In our main technical result, we achieve the optimal limit on domain
> sparsification for strongly Rayleigh distributions. In domain
> sparsification, sampling from a distribution $\mu$ on $\binom{[n]}{k}$ is
> reduced to sampling from related distributions on $\binom{[t]}{k}$ for $t
> \leq n$. We show that for strongly Rayleigh distributions, the domain size
> can be reduced to nearly linear in the output size $t=\tilde{O}(k)$,
> improving the state of the art from $t= \tilde{O}(k^2)$ for general
> strongly Rayleigh distributions and the more specialized
> $t=\tilde{O}(k^{1.5})$ for spanning tree distributions. Our reduction
> involves sampling from $\tilde{O}(1)$ domain-sparsified distributions, all
> of which can be produced efficiently assuming approximate overestimates for
> marginals of $\mu$ are known and stored in a convenient data structure.
> Having access to marginals is the discrete analog of having access to the
> mean and covariance of a continuous distribution, or equivalently knowing
> ``isotropy'' for the distribution, the key behind optimal samplers in the
> continuous setting based on the famous Kannan-Lov\'asz-Simonovits (KLS)
> conjecture. We view our result as analogous in spirit to the KLS conjecture
> and its consequences for sampling, but rather for discrete strongly
> Rayleigh measures.
> Joint work with Nima Anari and Yang P. Liu. To appear in FOCS 2022.
> Arxiv link [2204.02570v1] Optimal Sublinear Sampling of Spanning Trees
> and Determinantal Point Processes via Average-Case Entropic Independence
> (arxiv.org) <https://arxiv.org/abs/2204.02570v1>
>
>
> *Host: Madhur Tulsiani <madhurt at ttic.edu>*
>
>
> **************************************************************************************************
>
>
>
> The *TTIC Young Researcher Seminar Series* (
> http://www.ttic.edu/young-researcher.php) features talks by Ph.D.
> students and postdocs whose research is of broad interest to the computer
> science community. The series provides an opportunity for
> early-career researchers to present recent work to and meet with students
> and faculty at TTIC and nearby universities.
>
>
> The seminars are typically held on Wednesdays at 10:30am in TTIC Room 530.
>
> For additional information, please contact *David McAllester *(
> mcallester at ttic.edu).
> Mary C. Marre
> Faculty Administrative Support
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Chicago, IL 60637*
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
>
> On Sun, Nov 6, 2022 at 3:23 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *(PLEASE NOTE SPECIAL TIME!)*
>>
>> *When:* Monday, November 7th at *3 **pm CT *
>>
>>
>> *Where: *Talk will be given *live, in-person* at
>>
>> TTIC, 6045 S. Kenwood Avenue
>>
>> 5th Floor, Room 530
>>
>>
>> *Virtually:* via Panopto (*livestream*
>> <https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=72b5485e-fb43-4971-9a37-af3f0167d327>
>> )
>>
>>
>> *Who: * June Vuong, Stanford University
>>
>>
>> ------------------------------
>>
>> *Title:* Optimal Sublinear Sampling of Spanning Trees and Determinantal
>> Point Processes via Average-Case Entropic Independence
>> *Abstract: *We design fast algorithms for repeatedly sampling from
>> strongly Rayleigh distributions, which include as special cases random
>> spanning tree distributions and determinantal point processes. For a graph
>> G=(V, E), we show how to approximately sample uniformly random spanning
>> trees from G in $O(| V | log ^2 |V|) time per sample after an initial
>> $O(|E| polylog |E|)$ time preprocessing. This is the first nearly-linear
>> runtime in the output size, which is clearly optimal. For a determinantal
>> point process on k-sized subsets of a ground set of n elements, defined via
>> an nxn kernel matrix, we show how to approximately sample in
>> $\tilde{O}(k^\omega)$ time after an initial $\tilde{O}(nk^{\omega-1})$ time
>> preprocessing, where $\omega<2.372864$ is the matrix multiplication
>> exponent. The time to compute just the weight of the output set is roughly
>> $k^\omega$, a natural barrier that suggests our runtime might be optimal
>> for determinantal point processes as well. As a corollary, we even improve
>> the state of the art for obtaining a single sample from a determinantal
>> point process, from the prior runtime of $\tilde{O}(\min\{nk^2,
>> n^\omega\})$ to $\tilde{O}(nk^{\omega-1})$.
>>
>> In our main technical result, we achieve the optimal limit on domain
>> sparsification for strongly Rayleigh distributions. In domain
>> sparsification, sampling from a distribution $\mu$ on $\binom{[n]}{k}$ is
>> reduced to sampling from related distributions on $\binom{[t]}{k}$ for $t
>> \leq n$. We show that for strongly Rayleigh distributions, the domain size
>> can be reduced to nearly linear in the output size $t=\tilde{O}(k)$,
>> improving the state of the art from $t= \tilde{O}(k^2)$ for general
>> strongly Rayleigh distributions and the more specialized
>> $t=\tilde{O}(k^{1.5})$ for spanning tree distributions. Our reduction
>> involves sampling from $\tilde{O}(1)$ domain-sparsified distributions, all
>> of which can be produced efficiently assuming approximate overestimates for
>> marginals of $\mu$ are known and stored in a convenient data structure.
>> Having access to marginals is the discrete analog of having access to the
>> mean and covariance of a continuous distribution, or equivalently knowing
>> ``isotropy'' for the distribution, the key behind optimal samplers in the
>> continuous setting based on the famous Kannan-Lov\'asz-Simonovits (KLS)
>> conjecture. We view our result as analogous in spirit to the KLS conjecture
>> and its consequences for sampling, but rather for discrete strongly
>> Rayleigh measures.
>> Joint work with Nima Anari and Yang P. Liu. To appear in FOCS 2022.
>> Arxiv link [2204.02570v1] Optimal Sublinear Sampling of Spanning Trees
>> and Determinantal Point Processes via Average-Case Entropic Independence
>> (arxiv.org) <https://arxiv.org/abs/2204.02570v1>
>>
>>
>> *Host: Madhur Tulsiani <madhurt at ttic.edu>*
>>
>>
>> **************************************************************************************************
>>
>>
>>
>> The *TTIC Young Researcher Seminar Series* (
>> http://www.ttic.edu/young-researcher.php) features talks by Ph.D.
>> students and postdocs whose research is of broad interest to the computer
>> science community. The series provides an opportunity for
>> early-career researchers to present recent work to and meet with students
>> and faculty at TTIC and nearby universities.
>>
>>
>> The seminars are typically held on Wednesdays at 10:30am in TTIC Room 530.
>>
>> For additional information, please contact *David McAllester *(
>> mcallester at ttic.edu).
>>
>> Mary C. Marre
>> Faculty Administrative Support
>> *Toyota Technological Institute*
>> *6045 S. Kenwood Avenue*
>> *Chicago, IL 60637*
>> *mmarre at ttic.edu <mmarre at ttic.edu>*
>>
>>
>> On Mon, Oct 31, 2022 at 4:58 PM Mary Marre <mmarre at ttic.edu> wrote:
>>
>>> *(PLEASE NOTE SPECIAL TIME!)*
>>>
>>> *When:* Monday, November 7th at *3 **pm CT *
>>>
>>>
>>> *Where: *Talk will be given *live, in-person* at
>>>
>>> TTIC, 6045 S. Kenwood Avenue
>>>
>>> 5th Floor, Room 530
>>>
>>>
>>> *Virtually:* via Panopto (*livestream*
>>> <https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=72b5485e-fb43-4971-9a37-af3f0167d327>
>>> )
>>>
>>>
>>> *Who: * June Vuong, Stanford University
>>>
>>>
>>> ------------------------------
>>>
>>> *Title:* Optimal Sublinear Sampling of Spanning Trees and Determinantal
>>> Point Processes via Average-Case Entropic Independence
>>> *Abstract: *We design fast algorithms for repeatedly sampling from
>>> strongly Rayleigh distributions, which include as special cases random
>>> spanning tree distributions and determinantal point processes. For a graph
>>> G=(V, E), we show how to approximately sample uniformly random spanning
>>> trees from G in $O(| V | log ^2 |V|) time per sample after an initial
>>> $O(|E| polylog |E|)$ time preprocessing. This is the first nearly-linear
>>> runtime in the output size, which is clearly optimal. For a determinantal
>>> point process on k-sized subsets of a ground set of n elements, defined via
>>> an nxn kernel matrix, we show how to approximately sample in
>>> $\tilde{O}(k^\omega)$ time after an initial $\tilde{O}(nk^{\omega-1})$ time
>>> preprocessing, where $\omega<2.372864$ is the matrix multiplication
>>> exponent. The time to compute just the weight of the output set is roughly
>>> $k^\omega$, a natural barrier that suggests our runtime might be optimal
>>> for determinantal point processes as well. As a corollary, we even improve
>>> the state of the art for obtaining a single sample from a determinantal
>>> point process, from the prior runtime of $\tilde{O}(\min\{nk^2,
>>> n^\omega\})$ to $\tilde{O}(nk^{\omega-1})$.
>>>
>>> In our main technical result, we achieve the optimal limit on domain
>>> sparsification for strongly Rayleigh distributions. In domain
>>> sparsification, sampling from a distribution $\mu$ on $\binom{[n]}{k}$ is
>>> reduced to sampling from related distributions on $\binom{[t]}{k}$ for $t
>>> \leq n$. We show that for strongly Rayleigh distributions, the domain size
>>> can be reduced to nearly linear in the output size $t=\tilde{O}(k)$,
>>> improving the state of the art from $t= \tilde{O}(k^2)$ for general
>>> strongly Rayleigh distributions and the more specialized
>>> $t=\tilde{O}(k^{1.5})$ for spanning tree distributions. Our reduction
>>> involves sampling from $\tilde{O}(1)$ domain-sparsified distributions, all
>>> of which can be produced efficiently assuming approximate overestimates for
>>> marginals of $\mu$ are known and stored in a convenient data structure.
>>> Having access to marginals is the discrete analog of having access to the
>>> mean and covariance of a continuous distribution, or equivalently knowing
>>> ``isotropy'' for the distribution, the key behind optimal samplers in the
>>> continuous setting based on the famous Kannan-Lov\'asz-Simonovits (KLS)
>>> conjecture. We view our result as analogous in spirit to the KLS conjecture
>>> and its consequences for sampling, but rather for discrete strongly
>>> Rayleigh measures.
>>> Joint work with Nima Anari and Yang P. Liu. To appear in FOCS 2022.
>>> Arxiv link [2204.02570v1] Optimal Sublinear Sampling of Spanning Trees
>>> and Determinantal Point Processes via Average-Case Entropic Independence
>>> (arxiv.org) <https://arxiv.org/abs/2204.02570v1>
>>>
>>>
>>> *Host: Madhur Tulsiani <madhurt at ttic.edu>*
>>>
>>>
>>> **************************************************************************************************
>>>
>>>
>>>
>>> The *TTIC Young Researcher Seminar Series* (http://www.ttic.edu/young-
>>> researcher.php) features talks by Ph.D. students and postdocs
>>> whose research is of broad interest to the computer science community. The
>>> series provides an opportunity for early-career researchers to present
>>> recent work to and meet with students and faculty at TTIC and nearby
>>> universities.
>>>
>>>
>>> The seminars are typically held on Wednesdays at 10:30am in TTIC Room
>>> 530.
>>>
>>> For additional information, please contact *David McAllester *(
>>> mcallester at ttic.edu).
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> ]
>>>
>>> Mary C. Marre
>>> Faculty Administrative Support
>>> *Toyota Technological Institute*
>>> *6045 S. Kenwood Avenue*
>>> *Chicago, IL 60637*
>>> *mmarre at ttic.edu <mmarre at ttic.edu>*
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221107/ba133f26/attachment-0001.html>
More information about the Theory
mailing list