Results 461 - 470 of 24335
In the wake of the National Quantum Initiative, the Simons Institute’s Research Pod in Quantum Computing brings together researchers from computer...
In the wake of the National Quantum Initiative, the Simons Institute’s Research Pod in Quantum Computing brings together researchers from computer...
Speaker List:
Anupam Gupta
Kevin Stangl
Kavya Ramachandran
Han Shao
Naren Manoj
Jamie Morgenstern
Xinyuan Cao
Lev Reyzin
Adam Kalai
Siddharth Prasad
Pravesh Kothari
Not all convex functions have finite minimizers; some can only be minimized by a sequence as it heads to infinity. In this work, we aim to develop a theory for understanding such minimizers at infinity. We study astral space, a compact extension of Euclidean space to which such points at infinity have been added. Astral space is constructed to be as small as possible while still ensuring that all linear functions can be continuously extended to the new space. Although not a vector space, nor even a metric space, astral space is nevertheless so well-structured as to allow useful and meaningful extensions of such concepts as convexity, conjugacy, and subdifferentials. We develop these concepts and analyze various properties of convex functions on astral space, including the detailed structure of their minimizers, exact characterizations of continuity, and convergence of descent algorithms.
This is joint work with Miro Dudík and Matus Telgarsky. For further reading, see aka.ms/astral.
We introduce a Probably Approximately Correct (PAC) learning framework where each hypothesis is represented by a graph, with edges indicating positive interactions, such as between users and items. This framework subsumes the classical binary and multi-class PAC learning models as well as multi-label learning with partial feedback, where only a single random correct label per example is observed, rather than all correct labels.
Our work uncovers a rich statistical and algorithmic landscape, with nuanced boundaries on what can and cannot be learned. Notably, classical methods like Empirical Risk Minimization fail in this setting, even for simple hypothesis classes with only two hypotheses. To address these challenges, we develop novel algorithms that learn exclusively from positive data, effectively minimizing both precision and recall losses. Specifically, in the realizable setting, we design algorithms that achieve optimal sample complexity guarantees. In the agnostic case, we show that it is impossible to achieve additive error guarantees (i.e., additive regret)—as is standard in PAC learning—and instead obtain meaningful multiplicative approximations.
This is a joint work with Lee Cohen, Shay Moran and Han Shao