Results 451 - 460 of 24335
Algorithms for supervised learning typically require some sort of distributional assumption (e.g., Gaussianity), in contrast to the traditional worst-case analysis paradigm from theoretical computer science. This leads to algorithms that succeed only under hard-to-verify assumptions, undermining the very notion of provable correctness.
In this talk, I will describe new learning models where an algorithm either certifies the accuracy of its output classifier or abstains when a distributional assumption has been violated. We will show how this framework leads to the first provably efficient algorithms for learning with distribution shift (with no assumptions on the target domain) and also introduces new techniques that resolve longstanding open problems in supervised learning with contamination.
A conjecture of Komlós states that the discrepancy of any collection
of unit vectors is O(1), i.e., for any matrix A with unit columns,
there is a vector x with -1,1 entries such that |Ax|_\infty = O(1).
The related Beck-Fiala conjecture states that any set system with
maximum degree k has discrepancy O(k^{1/2}).
I will describe an O((log n)^{1/4}) bound for the Komlós problem,
improving upon an O((log n)^{1/2}) bound due to Banaszczyk.
Time permitting, we will see how these ideas can be used to resolve
the Beck-Fiala conjecture for k >= (log n)^2.
In this talk, I will introduce multiobjective learning as a unifying paradigm for learning models with performance guarantees across arbitrary downstream tasks and losses. I will present an algorithmic toolbox for learning such multiobjective models from a small number of samples and with modest computation. I will also highlight how this toolbox provides a useful lens for designing algorithms and obtaining improved or optimal guarantees for several general frameworks in ML theory, including multi-distribution learning, group distributionally robust learning, fairness in ML, calibration, and omniprediction.
In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects each dicut. Woodall conjectured in 1976 that in every digraph, the minimum size of a dicut equals to the maximum number of disjoint dijoins. By building connections with nowhere-zero k-flows, we prove that every digraph with minimum dicut size $\tau$ contains $\lfloor \tau/k \rfloor$ disjoint dijoins if the underlying undirected graph admits a nowhere-zero k-flow.
Joint work with Gérard Cornuéjols (CMU) and Siyue Liu (CMU)