Source author record

Mihir Singhal

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Complexity Machine Learning math.PR

Catalog footprint

Research overview

5works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Low-Degree Multicalibration

Introduced as a notion of algorithmic fairness, multicalibration has proved to be a powerful and versatile concept with implications far beyond its original intent. This stringent notion -- that predictions be well-calibrated across a rich class of intersecting subpopulations -- provides its strong guarantees at a cost: the computational and sample complexity of learning multicalibrated predictors are high, and grow exponentially with the number of class labels. In contrast, the relaxed notion of multiaccuracy can be achieved more efficiently, yet many of the most desirable properties of multicalibration cannot be guaranteed assuming multiaccuracy alone. This tension raises a key question: Can we learn predictors with multicalibration-style guarantees at a cost commensurate with multiaccuracy? In this work, we define and initiate the study of Low-Degree Multicalibration. Low-Degree Multicalibration defines a hierarchy of increasingly-powerful multi-group fairness notions that spans multiaccuracy and the original formulation of multicalibration at the extremes. Our main technical contribution demonstrates that key properties of multicalibration, related to fairness and accuracy, actually manifest as low-degree properties. Importantly, we show that low-degree multicalibration can be significantly more efficient than full multicalibration. In the multi-class setting, the sample complexity to achieve low-degree multicalibration improves exponentially (in the number of classes) over full multicalibration. Our work presents compelling evidence that low-degree multicalibration represents a sweet spot, pairing computational and sample efficiency with strong fairness and accuracy guarantees.

preprint2021arXiv

Lower bounds for superpatterns and universal sequences

A permutation $σ\in S_n$ is said to be $k$ -universal or a $k$ -superpattern if for every $π\in S_k$ , there is a subsequence of $σ$ that is order-isomorphic to $π$ . A simple counting argument shows that $σ$ can be a $k$ -superpattern only if $n\ge (1/e^2+o(1))k^2$ , and Arratia conjectured that this lower bound is best-possible. Disproving Arratia's conjecture, we improve the trivial bound by a small constant factor. We accomplish this by designing an efficient encoding scheme for the patterns that appear in $σ$ . This approach is quite flexible and is applicable to other universality-type problems; for example, we also improve a bound by Engen and Vatter on a problem concerning $(k+1)$ -ary sequences which contain all $k$ -permutations.

preprint2020arXiv

Families with no perfect matchings

We consider families of $k$ -subsets of $\{1, \dots, n\}$ , where $n$ is a multiple of $k$ , which have no perfect matching. An equivalent condition for a family $\mathcal{F}$ to have no perfect matching is for there to be a blocking set, which is a set of $b$ elements of $\{1, \dots, n\}$ that cannot be covered by $b$ disjoint sets in $\mathcal{F}$ . We are specifically interested in the largest possible size of a family $\mathcal{F}$ with no perfect matching and no blocking set of size less than $b$ . Frankl resolved the case of families with no singleton blocking set (in other words, the $b=2$ case) for sufficiently large $n$ and conjectured an optimal construction for general $b$ . Though Frankl's construction fails to be optimal for $k = 2, 3$ , we show that the construction is optimal whenever $k \ge 100$ and $n$ is sufficiently large.

preprint2020arXiv

Unimodality of a refinement of Lassalle's sequence

Defant, Engen, and Miller defined a refinement of Lassalle's sequence $A_{k+1}$ by considering uniquely sorted permutations of length $2k+1$ whose first element is $\ell$ . They showed that each such sequence is symmetric in $\ell$ and conjectured that these sequences are unimodal. We prove that the sequences are unimodal.

preprint2019arXiv

Erdos-Littlewood-Offord problem with arbitrary probabilities

The classical Erdős-Littlewood-Offord problem concerns the random variable $X = a_1 ξ_1 + \dots + a_n ξ_n$ , where $a_i \in \mathbb{R} \setminus \{0\}$ are fixed and $ξ_i \sim \text{Ber}(1/2)$ are independent. The Erdős-Littlewood-Offord theorem states that the maximum possible concentration probability $\max_{x \in \mathbb{R}} \Pr(X = x)$ is $\binom{n}{\lfloor n/2\rfloor} / 2^n$ , achieved when the $a_i$ are all $1$ . As proposed by Fox, Kwan, and Sauermann, we investigate the general case where $ξ_i \sim \text{Ber}(p)$ instead. Using purely combinatorial techniques, we show that the exact maximum concentration probability is achieved when $a_i \in \{-1, 1\}$ for each $i$ . Then, using Fourier-analytic techniques, we investigate the optimal ratio of $1$ s to $-1$ s. Surprisingly, we find that in some cases, the numbers of $1$ s and $-1$ s can be far from equal.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.