Search

Your search keyword '"Kane, Daniel A."' showing total 108 results
Start Over Author "Kane, Daniel A." Database eScholarship
108 results on '"Kane, Daniel A."'

3. Locality Bounds for Sampling Hamming Slices

Author

Kane, Daniel M, Ostuni, Anthony, and Wu, Kewen

Subjects
Applied Mathematics, Pure Mathematics, Mathematical Sciences
Abstract

Spurred by the influential work of Viola (Journal of Computing 2012), the past decade has witnessed an active line of research into the complexity of (approximately) sampling distributions, in contrast to the traditional focus on the complexity of computing functions. We build upon and make explicit earlier implicit results of Viola to provide superconstant lower bounds on the locality of Boolean functions approximately sampling the uniform distribution over binary strings of particular Hamming weights, both exactly and modulo an integer, answering questions of Viola (Journal of Computing 2012) and Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023). Applications to data structure lower bounds and quantum-classical separations are discussed. This is an extended abstract. The full paper can be found at https://arxiv.org/abs/2402.14278.

Published
2024

4. Realizable Learning is All You Need

Author

Hopkins, Max, Kane, Daniel, Lovett, Shachar, and Mahajan, Gaurav

Subjects
Information and Computing Sciences, Machine Learning, Clinical Research
Abstract

The equivalence of realizable and agnostic learnability is a fundamentalphenomenon in learning theory. With variants ranging from classical settingslike PAC learning and regression to recent trends such as adversarially robustlearning, it's surprising that we still lack a unified theory; traditionalproofs of the equivalence tend to be disparate, and rely on strongmodel-specific assumptions like uniform convergence and sample compression. In this work, we give the first model-independent framework explaining theequivalence of realizable and agnostic learnability: a three-line blackboxreduction that simplifies, unifies, and extends our understanding across a widevariety of settings. This includes models with no known characterization oflearnability such as learning with arbitrary distributional assumptions andmore general loss functions, as well as a host of other popular settings suchas robust learning, partial learning, fair learning, and the statistical querymodel. More generally, we argue that the equivalence of realizable and agnosticlearning is actually a special case of a broader phenomenon we call propertygeneralization: any desirable property of a learning algorithm (e.g. noisetolerance, privacy, stability) that can be satisfied over finite hypothesisclasses extends (possibly in some variation) to any learnable hypothesis class.

Published
2024

16. Megahertz‐rate ultrafast X‐ray scattering and holographic imaging at the European XFEL

Author

Hagström, Nanna Zhou, Schneider, Michael, Kerber, Nico, Yaroslavtsev, Alexander, Parra, Erick Burgos, Beg, Marijan, Lang, Martin, Günther, Christian M, Seng, Boris, Kammerbauer, Fabian, Popescu, Horia, Pancaldi, Matteo, Neeraj, Kumar, Polley, Debanjan, Jangid, Rahul, Hrkac, Stjepan B, Patel, Sheena KK, Ovcharenko, Sergei, Turenne, Diego, Ksenzov, Dmitriy, Boeglin, Christine, Baidakova, Marina, von Korff Schmising, Clemens, Borchert, Martin, Vodungbo, Boris, Chen, Kai, Luo, Chen, Radu, Florin, Müller, Leonard, Flórez, Miriam Martínez, Philippi-Kobs, André, Riepp, Matthias, Roseker, Wojciech, Grübel, Gerhard, Carley, Robert, Schlappa, Justine, Van Kuiken, Benjamin E, Gort, Rafael, Mercadier, Laurent, Agarwal, Naman, Le Guyader, Loïc, Mercurio, Giuseppe, Teichmann, Martin, Delitz, Jan Torben, Reich, Alexander, Broers, Carsten, Hickin, David, Deiter, Carsten, Moore, James, Rompotis, Dimitrios, Wang, Jinxiong, Kane, Daniel, Venkatesan, Sandhya, Meier, Joachim, Pallas, Florent, Jezynski, Tomasz, Lederer, Maximilian, Boukhelef, Djelloul, Szuba, Janusz, Wrona, Krzysztof, Hauf, Steffen, Zhu, Jun, Bergemann, Martin, Kamil, Ebad, Kluyver, Thomas, Rosca, Robert, Spirzewski, Michał, Kuster, Markus, Turcato, Monica, Lomidze, David, Samartsev, Andrey, Engelke, Jan, Porro, Matteo, Maffessanti, Stefano, Hansen, Karsten, Erdinger, Florian, Fischer, Peter, Fiorini, Carlo, Castoldi, Andrea, Manghisoni, Massimo, Wunderer, Cornelia Beatrix, Fullerton, Eric E, Shpyrko, Oleg G, Gutt, Christian, Sanchez-Hanke, Cecilia, Dürr, Hermann A, Iacocca, Ezio, Nembach, Hans T, Keller, Mark W, Shaw, Justin M, Silva, Thomas J, Kukreja, Roopali, Fangohr, Hans, Eisebitt, Stefan, Kläui, Mathias, Jaouen, Nicolas, Scherz, Andreas, Bonetti, Stefano, and Jal, Emmanuelle

Subjects
X-Rays, Lasers, Radiography, Holography, holography, magnetic X-ray scattering, soft X-rays, ultrafast X-ray imaging, XFEL, Condensed Matter Physics, Optical Physics, Physical Chemistry (incl. Structural), Biophysics
Abstract

The advent of X-ray free-electron lasers (XFELs) has revolutionized fundamental science, from atomic to condensed matter physics, from chemistry to biology, giving researchers access to X-rays with unprecedented brightness, coherence and pulse duration. All XFEL facilities built until recently provided X-ray pulses at a relatively low repetition rate, with limited data statistics. Here, results from the first megahertz-repetition-rate X-ray scattering experiments at the Spectroscopy and Coherent Scattering (SCS) instrument of the European XFEL are presented. The experimental capabilities that the SCS instrument offers, resulting from the operation at megahertz repetition rates and the availability of the novel DSSC 2D imaging detector, are illustrated. Time-resolved magnetic X-ray scattering and holographic imaging experiments in solid state samples were chosen as representative, providing an ideal test-bed for operation at megahertz rates. Our results are relevant and applicable to any other non-destructive XFEL experiments in the soft X-ray range.

Published
2022

17. vqSGD: Vector Quantized Stochastic Gradient Descent

Author

Gandikota, Venkata, Kane, Daniel, Maity, Raj Kumar, and Mazumdar, Arya

Subjects
Engineering, Information and Computing Sciences, Communications Engineering, Computer Vision and Multimedia Computation, Machine Learning, Vector quantization, communication efficiency, mean estimation, stochastic gradient descent, Artificial Intelligence and Image Processing, Electrical and Electronic Engineering, Communications Technologies, Networking & Telecommunications, Communications engineering, Theory of computation
Published
2022

18. Robustly learning mixtures of k arbitrary Gaussians

Author

Bakshi, Ainesh, Diakonikolas, Ilias, Jia, He, Kane, Daniel M, Kothari, Pravesh K, and Vempala, Santosh S

Subjects
Applied Mathematics, Information and Computing Sciences, Engineering, Mathematical Sciences, Gaussian Mixture Model, Robust Statistics, Tensor Decomposition, Sum-of-Squares
Published
2022

21. Robust Sparse Mean Estimation via Sum of Squares

Author

Diakonikolas, Ilias, Kane, Daniel M, Karmalkar, Sushrut, Pensia, Ankit, and Pittas, Thanasis

Subjects
robust statistics, sparse estimation, sum of squares, statistical query model
Published
2022

32. Efficiently learning halfspaces with Tsybakov noise

Author

Diakonikolas, Ilias, Kane, Daniel M, Kontonis, Vasilis, Tzamos, Christos, and Zarifis, Nikos

Subjects
Applied Mathematics, Information and Computing Sciences, Mathematical Sciences, Machine Learning, PAC learning, Tsybakov Noise, Halfspaces, Log-Concave Distributions
Published
2021

33. Optimal testing of discrete distributions with high probability

Author

Diakonikolas, Ilias, Gouleakis, Themis, Kane, Daniel M, Peebles, John, and Price, Eric

Subjects
Applied Mathematics, Mathematical Sciences, Information and Computing Sciences, Statistics, Vaccine Related, distribution property testing, sampling, high confidence
Published
2021

34. Robustness meets algorithms

Author

Diakonikolas, Ilias, Kamath, Gautam, Kane, Daniel M, Li, Jerry, Moitra, Ankur, and Stewart, Alistair

Subjects
Peace, Justice and Strong Institutions, Information and Computing Sciences, Information Systems
Abstract

In every corner of machine learning and statistics, there is a need for estimators that work not just in an idealized model, but even when their assumptions are violated. Unfortunately, in high dimensions, being provably robust and being efficiently computable are often at odds with each other. We give the first efficient algorithm for estimating the parameters of a high-dimensional Gaussian that is able to tolerate a constant fraction of corruptions that is independent of the dimension. Prior to our work, all known estimators either needed time exponential in the dimension to compute or could tolerate only an inverse-polynomial fraction of corruptions. Not only does our algorithm bridge the gap between robustness and algorithms, but also it turns out to be highly practical in a variety of settings.

Published
2021

43. Prisoners, Rooms, and Light Switches

Author

Kane, Daniel M and Kominers, Scott Duke

Subjects
Pure Mathematics, Computation Theory and Mathematics, Computation Theory & Mathematics
Abstract

We examine a new variant of the classic prisoners and light switches puzzle: A warden leads his $n$ prisoners in and out of $r$ rooms, one at a time, in some order, with each prisoner eventually visiting every room an arbitrarily large number of times. The rooms are indistinguishable, except that each one has $s$ light switches; the prisoners win their freedom if at some point a prisoner can correctly declare that each prisoner has been in every room at least once. What is the minimum number of switches per room, $s$, such that the prisoners can manage this? We show that if the prisoners do not know the switches' starting configuration, then they have no chance of escape—but if the prisoners do know the starting configuration, then the minimum sufficient $s$ is surprisingly small. The analysis gives rise to a number of puzzling open questions, as well.

Published
2021

47. Testing Bayesian Networks

Author

Canonne, Clement L, Diakonikolas, Ilias, Kane, Daniel M, and Stewart, Alistair

Subjects
Testing, Complexity theory, Graphical models, Bayes methods, Task analysis, Random variables, Probabilistic logic, distribution testing, property testing, Bayesian networks, graphical models, Artificial Intelligence and Image Processing, Electrical and Electronic Engineering, Communications Technologies, Networking & Telecommunications
Published
2020

48. Testing Bayesian Networks

Author

Canonne, Clément L, Diakonikolas, Ilias, Kane, Daniel M, and Stewart, Alistair

Subjects
Testing, Complexity theory, Graphical models, Bayes methods, Task analysis, Random variables, Probabilistic logic, distribution testing, property testing, Bayesian networks, graphical models, Artificial Intelligence and Image Processing, Electrical and Electronic Engineering, Communications Technologies, Networking & Telecommunications
Published
2020

Catalog

Books, media, physical & digital resources
See catalog results