More Like this

1. Coxeter groups and meridional rank of links

   https://doi.org/10.1007/s00208-020-02124-z  

   Baader, Sebastian; Blair, Ryan; Kjuchukova, Alexandra (April 2021, Mathematische Annalen)

   null (Ed.)

   Abstract We prove the meridional rank conjecture for twisted links and arborescent links associated to bipartite trees with even weights. These links are substantial generalizations of pretzels and two-bridge links, respectively. Lower bounds on meridional rank are obtained via Coxeter quotients of the groups of link complements. Matching upper bounds on bridge number are found using the Wirtinger numbers of link diagrams, a combinatorial tool developed by the authors. 

   more » « less
2. On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation

   https://doi.org/10.1137/1.9781611977912.32  

   Meyer, Raphael A.; Musco, Cameron; Musco, Christopher (January 2024, ACM-SIAM Symposium on Discrete Algorithms)

   Krylov subspace methods are a ubiquitous tool for computing near-optimal rank kk approximations of large matrices. While "large block" Krylov methods with block size at least kk give the best known theoretical guarantees, block size one (a single vector) or a small constant is often preferred in practice. Despite their popularity, we lack theoretical bounds on the performance of such "small block" Krylov methods for low-rank approximation. We address this gap between theory and practice by proving that small block Krylov methods essentially match all known low-rank approximation guarantees for large block methods. Via a black-box reduction we show, for example, that the standard single vector Krylov method run for t iterations obtains the same spectral norm and Frobenius norm error bounds as a Krylov method with block size ℓ≥kℓ≥k run for O(t/ℓ)O(t/ℓ) iterations, up to a logarithmic dependence on the smallest gap between sequential singular values. That is, for a given number of matrix-vector products, single vector methods are essentially as effective as any choice of large block size. By combining our result with tail-bounds on eigenvalue gaps in random matrices, we prove that the dependence on the smallest singular value gap can be eliminated if the input matrix is perturbed by a small random matrix. Further, we show that single vector methods match the more complex algorithm of [Bakshi et al. `22], which combines the results of multiple block sizes to achieve an improved algorithm for Schatten pp-norm low-rank approximation. 

   more » « less
3. Rigid local systems with monodromy group the Conway group Co2

   https://doi.org/10.1142/S1793042120500189  

   Katz, Nicholas M.; Rojas-León, Antonio; Tiep, Pham Huu (March 2020, International Journal of Number Theory)

   null (Ed.)

   We first develop some basic facts about hypergeometric sheaves on the multiplicative group [Formula: see text] in characteristic [Formula: see text]. Certain of their Kummer pullbacks extend to irreducible local systems on the affine line in characteristic [Formula: see text]. One of these, of rank [Formula: see text] in characteristic [Formula: see text], turns out to have the Conway group [Formula: see text], in its irreducible orthogonal representation of degree [Formula: see text], as its arithmetic and geometric monodromy groups. 

   more » « less
4. On Multilinear Forms: Bias, Correlation, and Tensor Rank

   Bhrushundi, Abhishek; Harsha, Prahladh; Hatami, Pooya; Kopparty, Swastik; Kumar, Mrinal (August 2020, Leibniz international proceedings in informatics)

   Byrka, Jaroslaw; Meka, Raghu (Ed.)

   In this work, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over F₂. We show the following results for multilinear forms and tensors. Correlation bounds. We show that a random d-linear form has exponentially low correlation with low-degree polynomials. More precisely, for d = 2^{o(k)}, we show that a random d-linear form f(X₁,X₂, … , X_d) : (F₂^{k}) ^d → F₂ has correlation 2^{-k(1-o(1))} with any polynomial of degree at most d/2 with high probability. This result is proved by giving near-optimal bounds on the bias of a random d-linear form, which is in turn proved by giving near-optimal bounds on the probability that a sum of t random d-dimensional rank-1 tensors is identically zero. Tensor rank vs Bias. We show that if a 3-dimensional tensor has small rank then its bias, when viewed as a 3-linear form, is large. More precisely, given any 3-dimensional tensor T: [k]³ → F₂ of rank at most t, the bias of the 3-linear form f_T(X₁, X₂, X₃) : = ∑_{(i₁, i₂, i₃) ∈ [k]³} T(i₁, i₂, i₃)⋅ X_{1,i₁}⋅ X_{2,i₂}⋅ X_{3,i₃} is at least (3/4)^t. This bias vs tensor-rank connection suggests a natural approach to proving nontrivial tensor-rank lower bounds. In particular, we use this approach to give a new proof that the finite field multiplication tensor has tensor rank at least 3.52 k, which is the best known rank lower bound for any explicit tensor in three dimensions over F₂. Moreover, this relation between bias and tensor rank holds for d-dimensional tensors for any fixed d. 

   more » « less
5. The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learning

   Wang, Kaiwen; Zhou, Kevin; Wu, Runzhe; Kallus, Nathan; Sun, Wen (December 2023, 37th Conference on Neural Information Processing Systems (NeurIPS 2023))

   While distributional reinforcement learning (DistRL) has been empirically effective, the question of when and why it is better than vanilla, non-distributional RL has remained unanswered. This paper explains the benefits of DistRL through the lens of small-loss bounds, which are instance-dependent bounds that scale with optimal achievable cost. Particularly, our bounds converge much faster than those from non-distributional approaches if the optimal cost is small. As warmup, we propose a distributional contextual bandit (DistCB) algorithm, which we show enjoys small-loss regret bounds and empirically outperforms the state-of-the-art on three real-world tasks. In online RL, we propose a DistRL algorithm that constructs confidence sets using maximum likelihood estimation. We prove that our algorithm enjoys novel small-loss PAC bounds in low-rank MDPs. As part of our analysis, we introduce the l1 distributional eluder dimension which may be of independent interest. Then, in offline RL, we show that pessimistic DistRL enjoys small-loss PAC bounds that are novel to the offline setting and are more robust to bad single-policy coverage. 

   more » « less