More Like this

1. Statistical Optimal Transport via Factored Couplings

   Forrow, Aden; Huetter, Jan-Christian; Nitzan, Mor; Rigollet, Philippe; Schiebinger, Geoffrey; Weed, Jonathan (April 2019, Proceedings of Machine Learning Research)

   We propose a new method to estimate Wasserstein distances and optimal transport plans between two probability distributions from samples in high dimension. Unlike plug-in rules that simply replace the true distributions by their empirical counterparts, our method promotes couplings with low transport rank, a new structural assumption that is similar to the nonnegative rank of a matrix. Regularizing based on this assumption leads to drastic improvements on high-dimensional data for various tasks, including domain adaptation in single-cell RNA sequencing data. These findings are supported by a theoretical analysis that indicates that the transport rank is key in overcoming the curse of dimensionality inherent to data-driven optimal transport. 

   more » « less
2. Bayesian Reinforcement Learning in Factored POMDPs

   Katt, Sammie; Oliehoek, Frans A.; Amato, Christopher (January 2019, Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems)

   Model-based Bayesian Reinforcement Learning (BRL) provides a principled solution to dealing with the exploration-exploitation trade-off, but such methods typically assume a fully observable environments. The few Bayesian RL methods that are applicable in partially observable domains, such as the Bayes-Adaptive POMDP (BA-POMDP), scale poorly. To address this issue, we introduce the Factored BA-POMDP model (FBA-POMDP), a framework that is able to learn a compact model of the dynamics by exploiting the underlying structure of a POMDP. The FBA-POMDP framework casts the problem as a planning task, for which we adapt the Monte-Carlo Tree Search planning algorithm and develop a belief tracking method to approximate the joint posterior over the state and model variables. Our empirical results show that this method outperforms a number of BRL baselines and is able to learn efficiently when the factorization is known, as well as learn both the factorization and the model parameters simultaneously. 

   more » « less
3. Statistical Optimal Transport via Factored Couplings

   Forrow, Aden; Hütter, Jan-Christian; Nitzan, Mor; Rigollet, Philippe; Schiebinger, Geoffrey; Weed, Jonathan (January 2019, AISTATS)

   null (Ed.)
4. Near-optimal interdiction of factored MDPs

   Panda, Swetasudha; Vorobeychik, Yevgeniy (July 2017, Conference on Uncertainty in Artificial Intelligence)
5. The Computational Complexity of Factored Graphs

   https://doi.org/10.4230/LIPICS.ITCS.2025.58  

   Gupta, Shreya; Huang, Boyang; Impagliazzo, Russell; Woo, Stanley; Ye, Christopher (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   While graphs and abstract data structures can be large and complex, practical instances are often regular or highly structured. If the instance has sufficient structure, we might hope to compress the object into a more succinct representation. An efficient algorithm (with respect to the compressed input size) could then lead to more efficient computations than algorithms taking the explicit, uncompressed object as input. This leads to a natural question: when does knowing the input instance has a more succinct representation make computation easier? We initiate the study of the computational complexity of problems on factored graphs: graphs that are given as a formula of products and unions on smaller graphs. For any graph problem, we define a parameterized version that takes factored graphs as input, parameterized by the number of (smaller) ordinary graphs used to construct the factored graph. In this setting, we characterize the parameterized complexity of several natural graph problems, exhibiting a variety of complexities. We show that a decision version of lexicographically first maximal independent set is XP-complete, and therefore unconditionally not fixed-parameter tractable (FPT). On the other hand, we show that clique counting is FPT. Finally, we show that reachability is XNL-complete. Moreover, XNL is contained in FPT if and only if NL is contained in some fixed polynomial time. 

   more » « less