Publications (27)
A Novel CMB Component Separation Method: Hierarchical Generalized Morphological Component Analysis
Sebastian Wagner-Carena, Max Hopkins, Ana Diaz Rivero +1
We present a novel technique for Cosmic Microwave Background (CMB) foreground subtraction based on the framework of blind source separation. Inspired by previous work incorporating…
The Power of Comparisons for Actively Learning Linear Classifiers
Max Hopkins, Daniel M. Kane, Shachar Lovett
In the world of big data, large but costly to label datasets dominate many fields. Active learning, a semi-supervised alternative to the standard PAC-learning model, was introduced…
Sampling Equilibria: Fast No-Regret Learning in Structured Games
Daniel Beaglehole, Max Hopkins, Daniel Kane +2
Learning and equilibrium computation in games are fundamental problems across computer science and economics, with applications ranging from politics to machine learning. Much of t…
Noise-tolerant, Reliable Active Classification with Comparison Queries
Max Hopkins, Daniel Kane, Shachar Lovett +1
With the explosion of massive, widely available unlabeled data in the past years, finding label and time efficient, robust learning algorithms has become ever more important in the…
Replicability in High Dimensional Statistics
Max Hopkins, Russell Impagliazzo, Daniel Kane +2
The replicability crisis is a major issue across nearly all areas of empirical science, calling for the formal study of replicability in statistics. Motivated in this context, [Imp…
Chernoff Bounds and Reverse Hypercontractivity on HDX
Yotam Dikstein, Max Hopkins
We prove optimal concentration of measure for lifted functions on high dimensional expanders (HDX). Let be a -dimensional HDX. We show for any and $f:X(i)\to [0,1]…
High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games
Mitali Bafna, Max Hopkins, Tali Kaufman +1
Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass [KM16]…
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments
Mitali Bafna, Max Hopkins, Tali Kaufman +1
Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in ext…
Simulated Annealing for JPEG Quantization
Max Hopkins, Michael Mitzenmacher, Sebastian Wagner-Carena
JPEG is one of the most widely used image formats, but in some ways remains surprisingly unoptimized, perhaps because some natural optimizations would go outside the standard that…
A Simple Sub-Polynomial Degree Coboundary Expander
Max Hopkins, Arka Ray
High dimensional expanders simultaneously satisfying spectral and combinatorial (coboundary) expansion have recently played a major role in breakthroughs in PCP and coding theory,…
Realizable Learning is All You Need
Max Hopkins, Daniel M. Kane, Shachar Lovett +1
The equivalence of realizable and agnostic learnability is a fundamental phenomenon in learning theory. With variants ranging from classical settings like PAC learning and regressi…
Toward a KKL Theorem for any HDX
Max Hopkins
The KKL Theorem, a seminal result in boolean function analysis, characterizes the structure of low-influence (non-expanding) functions on the hypercube. While recent years have see…
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets
Jason Gaitonde, Max Hopkins, Tali Kaufman +2
We study the relationship between the underlying structure of posets and the spectral and combinatorial properties of their higher-order random walks. While fast mixing of random w…
Doppelgangers: the Ur-Operation and Posets of Bounded Height
Thomas Browning, Max Hopkins, Zander Kelley
In the early 1970's, Richard Stanley and Kenneth Johnson introduced and laid the groundwork for studying the order polynomial of partially ordered sets (posets). Decades later, Ham…
Do PAC-Learners Learn the Marginal Distribution?
Max Hopkins, Daniel M. Kane, Shachar Lovett +1
The Fundamental Theorem of PAC Learning asserts that learnability of a concept class is equivalent to the of empirical error in to its mean,…
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Mark Bun, Marco Gaboardi, Max Hopkins +5
The notion of replicable algorithms was introduced in Impagliazzo et al. [STOC '22] to describe randomized algorithms that are stable under the resampling of their inputs. More pre…
High Rate Efficient Local List Decoding from HDX
Yotam Dikstein, Max Hopkins, Russell Impagliazzo +1
We construct the first (locally computable, approximately) locally list decodable codes with rate, efficiency, and error tolerance approaching the information theoretic limit, a co…
The Role of Randomness in Stability
Max Hopkins, Shay Moran
Stability is a central property in learning and statistics promising the output of an algorithm does not change substantially when applied to similar datasets and . It…
Explicit Lower Bounds Against -Rounds of Sum-of-Squares
Max Hopkins, Ting-Chun Lin
We construct an explicit family of 3-XOR instances hard for -levels of the Sum-of-Squares (SoS) semi-definite programming hierarchy. Not only is this the first explicit cons…
Non-Signaling Locality Lower Bounds for Dominating Set
Noah Fleming, Max Hopkins, Yuichi Yoshida
Minimum dominating set is a basic local covering problem and a core task in distributed computing. Despite extensive study, in the classic LOCAL model there exist significant gaps…
Bounded Memory Active Learning through Enriched Queries
Max Hopkins, Daniel Kane, Shachar Lovett +1
The explosive growth of easily-accessible unlabeled data has lead to growing interest in active learning, a paradigm in which data-hungry learning algorithms adaptively select info…
Approximate Replicability in Learning
Max Hopkins, Russell Impagliazzo, Christopher Ye
Replicability, introduced by (Impagliazzo et al. STOC '22), is the notion that algorithms should remain stable under a resampling of their inputs (given access to shared randomness…
Point Location and Active Learning: Learning Halfspaces Almost Optimally
Max Hopkins, Daniel M. Kane, Shachar Lovett +1
Given a finite set and a binary linear classifier , how many queries of the form are required to learn the label of eve…
Robust Empirical Risk Minimization with Tolerance
Robi Bhattacharjee, Max Hopkins, Akash Kumar +2
Developing simple, sample-efficient learning algorithms for robust classification is a pressing issue in today's tech-dominated world, and current theoretical techniques requiring…
From Generative to Episodic: Sample-Efficient Replicable Reinforcement Learning
Max Hopkins, Sihan Liu, Christopher Ye +1
The epidemic failure of replicability across empirical science and machine learning has recently motivated the formal study of replicable learning algorithms [Impagliazzo et al. (2…
Hypercontractivity on HDX II: Symmetrization and q-Norms
Max Hopkins
Bourgain's symmetrization theorem is a powerful technique reducing boolean analysis on product spaces to the cube. It states that for any product , function $f: Î…
Active Learning Polynomial Threshold Functions
Omri Ben-Eliezer, Max Hopkins, Chutong Yang +1
We initiate the study of active learning polynomial threshold functions (PTFs). While traditional lower bounds imply that even univariate quadratics cannot be non-trivially activel…