Author name cluster

Zachary Chase 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

STOC Conference 2024 Conference Paper

Local Borsuk-Ulam, Stability, and Replicability

Zachary Chase 0001
Bogdan Chornomaz
Shay Moran
Amir Yehudayoff

We use and adapt the Borsuk-Ulam Theorem from topology to derive limitations on list-replicable and globally stable learning algorithms. We further demonstrate the applicability of our methods in combinatorics and topology. We show that, besides trivial cases, both list-replicable and globally stable learning are impossible in the agnostic PAC setting. This is in contrast with the realizable case where it is known that any class with a finite Littlestone dimension can be learned by such algorithms. In the realizable PAC setting, we sharpen previous impossibility results and broaden their scope. Specifically, we establish optimal bounds for list replicability and global stability numbers in finite classes. This provides an exponential improvement over previous works and implies an exponential separation from the Littlestone dimension. We further introduce lower bounds for weak learners, i.e., learners that are only marginally better than random guessing. Lower bounds from previous works apply only to stronger learners. To offer a broader and more comprehensive view of our topological approach, we prove a local variant of the Borsuk-Ulam theorem in topology and a result in combinatorics concerning Kneser colorings. In combinatorics, we prove that if c is a coloring of all non-empty subsets of [ n ] such that disjoint sets have different colors, then there is a chain of subsets that receives at least 1+ ⌊ n /2⌋ colors (this bound is sharp). In topology, we prove e.g. that for any open antipodal-free cover of the d -dimensional sphere, there is a point ‍ x that belongs to at least t =⌈ d +3/2⌉ sets.

Details

FOCS Conference 2023 Conference Paper

Stability and Replicability in Learning

Zachary Chase 0001
Shay Moran
Amir Yehudayoff

Replicability is essential in science as it allows us to validate and verify research findings. Impagliazzo, Lei, Pitassi and Sorrell ('22) recently initiated the study of replicability in machine learning. A learning algorithm is replicable if it typically produces the same output when applied on two i. i. d. inputs using the same internal randomness. We study a variant of replicability that does not involve fixing the randomness. An algorithm satisfies this form of replicability if it typically produces the same output when applied on two i. i. d. inputs (without fixing the internal randomness). This variant is called global stability and was introduced by Bun, Livni and Moran ('20) in the context of differential privacy. Impagliazzo et al. showed how to boost any replicable algorithm so that it produces the same output with probability arbitrarily close to 1. In contrast, we demonstrate that for numerous learning tasks, global stability can only be accomplished weakly, where the same output is produced only with probability bounded away from 1. To overcome this limitation, we introduce the concept of list replicability, which is equivalent to global stability. Moreover, we prove that list replicability can be boosted so that it is achieved with probability arbitrarily close to 1. We also describe basic relations between standard learningtheoretic complexity measures and list replicable numbers. Our results, in addition, imply that besides trivial cases, replicable algorithms (in the sense of Impagliazzo et al.) must be randomized. The proof of the impossibility result is based on a topological fixed-point theorem. For every algorithm, we are able to locate a "hard input distribution by applying the Poincaré-Miranda theorem in a related topological setting. The equivalence between global stability and list replicability is algorithmic.

Details

STOC Conference 2021 Conference Paper

Separating words and trace reconstruction

Zachary Chase 0001

We prove that for any distinct x , y ∈ {0,1} n , there is a deterministic finite automaton with O ( n 1/3 ) states that accepts x but not y . This improves Robson’s 1989 bound of O ( n 2/5 ). Using a similar complex analytic technique, we improve the upper bound on worst case trace reconstruction, showing that any unknown string x ∈ {0,1} n can be reconstructed with high probability from exp( O ( n 1/5 )) independently generated traces.

Details