Shaddin Dughmi
University of Southern California, CA·Computer Science
Machine learning works well in practice, yet basic theoretical questions about it remain open. Which problems can be learned at all?
- Fields
Computer Science
Mathematics & Statistics
- Topics
learning theory
supervised learning
classification
- Grants
- 1 known grant, through Dec 2027
What they work on
- Identify algorithmic recipes for optimal supervised learning by treating classification as bipartite matching on the one-inclusion graph, a structure linking possible labelings of data.
- Test whether the matching-based view explains the success of common learning algorithms or prescribes new ones, using tools from combinatorics and optimization.
- Derive structural characterizations of learnability that apply broadly to supervised learning by generalizing the one-inclusion graph matching problem beyond classification.
More about the research
What does the best possible learning algorithm look like? What features of a problem make learning possible or impossible? Answering these questions could deepen understanding of machine learning and point toward better algorithms.
Why it matters
This is basic theory. The work aims to clarify what can be learned from data and what optimal learning algorithms look like. These insights could eventually guide the design of better machine learning algorithms and help explain why existing approaches work.
Known grants
From NIH and NSF research grants. Labs often have other funding we can't see.
Closest labs
Vijay Vazirani
University of California-Irvine, CA·Computer Science
Design algorithms for online hypergraph matching, where each match can involve more than two parties, and its generalizations, building on the simple proof of the RANKING algorithm, with applications to ride-sharing and network revenue management.
Kirk Pruhs
University of Pittsburgh, PA·Computer Science
Develop combinatorial surrogates, graph-theoretic and local expansion conditions, that imply the high topological connectivity needed by topological fixed-point proofs but can be verified by algorithm researchers without topology training.
Sayan Bandyapadhyay
Portland State University, OR·Computer Science
Design polynomial-time approximation algorithms for balanced k-median and k-means clustering, where each cluster must fairly represent every protected group, aiming for constant-factor guarantees like those known for ordinary clustering.
The school
University of Southern California: 47 labs on PI Pages, $1.3B a year on research, 882 research doctorates a year.
Reach out
A start for your email. Fill in the brackets.