More Like this

1. Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models

   Bezakova, Ivona; Blanca, Antonio; Chen, Zongchen; Stefankovic, Daniel; Vigoda, Eric (July 2019, Proceedings of Machine Learning Research)

   We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model M and a sampling oracle for the distribution \mu_{M^*} of an unknown model M^*, can we efficiently determine if the two models M and M^* are the same? We consider identity testing for both soft-constraint and hard-constraint systems. In particular, we prove hardness results in two prototypical cases, the Ising model and proper colorings, and explore whether identity testing is any easier than structure learning. For the ferromagnetic (attractive) Ising model, Daskalasis et al. (2018) presented a polynomial time algorithm for identity testing. We prove hardness results in the antiferromagnetic (repulsive) setting in the same regime of parameters where structure learning is known to require a super-polynomial number of samples. In particular, for n-vertex graphs of maximum degree d, we prove that if |\beta| d = \omega(\log n) (where \beta is the inverse temperature parameter), then there is no identity testing algorithm for the antiferromagnetic Ising model that runs in polynomial time unless RP = NP. We also establish computational lower bounds for a broader set of parameters under the (randomized) exponential time hypothesis. In our proofs, we use random graphs as gadgets; this is inspired by similar constructions in seminal works on the hardness of approximate counting. In the hard-constraint setting, we present hardness results for identity testing for proper colorings. Our results are based on the presumed hardness of #BIS, the problem of (approximately) counting independent sets in bipartite graphs. In particular, we prove that identity testing for colorings is hard in the same range of parameters where structure learning is known to be hard, which in turn matches the parameter regime for NP-hardness of the corresponding decision problem. 

   more » « less
2. Moments of Random Quantum Marginals via Weingarten Calculus

   https://doi.org/10.1093/imrn/rnad105  

   Matsumoto, Sho; McSwiggen, Colin (May 2023, International Mathematics Research Notices)

   The randomized quantum marginal problem asks about the joint distribution of the partial traces (“marginals”) of a uniform random Hermitian operator with fixed spectrum acting on a space of tensors. We introduce a new approach to this problem based on studying the mixed moments of the entries of the marginals. For randomized quantum marginal problems that describe systems of distinguishable particles, bosons, or fermions, we prove formulae for these mixed moments, which determine the joint distribution of the marginals completely. Our main tool is Weingarten calculus, which provides a method for computing integrals of polynomial functions with respect to Haar measure on the unitary group. As an application, in the case of two distinguishable particles, we prove some results on the asymptotic behavior of the marginals as the dimension of one or both Hilbert spaces goes to infinity. 

   more » « less
3. Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms

   Chi Jin, Qinghua Liu (December 2021, Advances in Neural Information Processing Systems)

   Finding the minimal structural assumptions that empower sample-efficient learning is one of the most important research directions in Reinforcement Learning (RL). This paper advances our understanding of this fundamental question by introducing a new complexity measure—Bellman Eluder (BE) dimension. We show that the family of RL problems of low BE dimension is remarkably rich, which subsumes a vast majority of existing tractable RL problems including but not limited to tabular MDPs, linear MDPs, reactive POMDPs, low Bellman rank problems as well as low Eluder dimension problems. This paper further designs a new optimization-based algorithm— GOLF, and reanalyzes a hypothesis elimination-based algorithm—OLIVE (proposed in Jiang et al. (2017)). We prove that both algorithms learn the near-optimal policies of low BE dimension problems in a number of samples that is polynomial in all relevant parameters, but independent of the size of state-action space. Our regret and sample complexity results match or improve the best existing results for several well-known subclasses of low BE dimension problems. 

   more » « less
4. Approximation of compositional functions with ReLU neural networks

   https://doi.org/10.1016/j.sysconle.2023.105508  

   Gong, Q.; Kang, W.; Fahroo, F. (May 2023, Systems control letters)

   The power of DNN has been successfully demonstrated on a wide variety of high-dimensional problems that cannot be solved by conventional control design methods. These successes also uncover some fundamental and pressing challenges in understanding the representability of deep neural networks for complex and high dimensional input–output relations. Towards the goal of understanding these fundamental questions, we applied an algebraic framework developed in our previous work to analyze ReLU neural network approximation of compositional functions. We prove that for Lipschitz continuous functions, ReLU neural networks have an approximation error upper bound that is a polynomial of the network’s complexity and the compositional features. If the compositional features do not increase exponentially with dimension, which is the case in many applications, the complexity of DNN has a polynomial growth. In addition to function approximations, we also establish ReLU network approximation results for the trajectories of control systems, and for a Lyapunov function that characterizes the domain of attraction. 

   more » « less
5. Sign-rank Can Increase under Intersection

   https://doi.org/10.1145/3470863  

   Bun, Mark; Mande, Nikhil S.; Thaler, Justin (December 2021, ACM Transactions on Computation Theory)

   The communication class UPP cc is a communication analog of the Turing Machine complexity class PP . It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds. For a communication problem f , let f ∧ f denote the function that evaluates f on two disjoint inputs and outputs the AND of the results. We exhibit a communication problem f with UPP cc ( f ) = O (log n ), and UPP cc ( f ∧ f ) = Θ (log 2 n ). This is the first result showing that UPP communication complexity can increase by more than a constant factor under intersection. We view this as a first step toward showing that UPP cc , the class of problems with polylogarithmic-cost UPP communication protocols, is not closed under intersection. Our result shows that the function class consisting of intersections of two majorities on n bits has dimension complexity n Omega Ω(log n ) . This matches an upper bound of (Klivans, O’Donnell, and Servedio, FOCS 2002), who used it to give a quasipolynomial time algorithm for PAC learning intersections of polylogarithmically many majorities. Hence, fundamentally new techniques will be needed to learn this class of functions in polynomial time. 

   more » « less