More Like this

1. The Statistical Scope of Multicalibration

   Noarov, Georgy; Roth, Aaron (January 2023, International Conference on Machine Learning)

   We make a connection between multicalibration and property elicitation and show that (under mild technical conditions) it is possible to produce a multicalibrated predictor for a continuous scalar property if and only if is elicitable. On the negative side, we show that for non-elicitable continuous properties there exist simple data distributions on which even the true distributional predictor is not calibrated. On the positive side, for elicitable , we give simple canonical algorithms for the batch and the online adversarial setting, that learn a -multicalibrated predictor. This generalizes past work on multicalibrated means and quantiles, and in fact strengthens existing online quantile multicalibration results. To further counter-weigh our negative result, we show that if a property is not elicitable by itself, but is elicitable conditionally on another elicitable property , then there is a canonical algorithm that jointly multicalibrates and ; this generalizes past work on mean-moment multicalibration. Finally, as applications of our theory, we provide novel algorithmic and impossibility results for fair (multicalibrated) risk assessment. 

   more » « less
2. Reconstruction of the Crossing Type of a Point Set from the Compatible Exchange Graph of Noncrossing Spanning Trees

   https://doi.org/10.1007/978-3-030-14085-4_19  

   Marcos Oropeza, Csaba D. (February 2019, International Conference on Discrete Geometry for Computer Imagery)

   Let P be a set of n points in the plane in general position. The order type of P specifies, for every ordered triple, a positive or negative orientation; and the x-type (a.k.a. crossing type) of P specifies, for every unordered 4-tuple, whether they are in convex position. Geometric algorithms on P typically rely on primitives involving the order type or x-type (i.e., triples or 4-tuples). In this paper, we show that the x-type of P can be reconstructed from the compatible exchange graph G1(P) of noncrossing spanning trees on P. This extends a recent result by Keller and Perles (2016), who proved that the x-type of P can be reconstructed from the exchange graph G0(P) of noncrossing spanning trees, where G1(P) is a subgraph of G0(P) . A crucial ingredient of our proof is a structure theorem on the maximal sets of pairwise noncrossing edges (msnes) between two components of a planar straight-line graph on the point set P. 

   more » « less
3. Multicalibration as Boosting for Regression

   Globus-Harris, Ira; Harrison, Declan; Kearns, Michael; Roth, Aaron; Sorrell, Jessica (January 2023, International Conference on Machine Learning)

   We study the connection between multicalibration and boosting for squared error regression. First we prove a useful characterization of multicalibration in terms of a ``swap regret'' like condition on squared error. Using this characterization, we give an exceedingly simple algorithm that can be analyzed both as a boosting algorithm for regression and as a multicalibration algorithm for a class H that makes use only of a standard squared error regression oracle for H. We give a weak learning assumption on H that ensures convergence to Bayes optimality without the need to make any realizability assumptions -- giving us an agnostic boosting algorithm for regression. We then show that our weak learning assumption on H is both necessary and sufficient for multicalibration with respect to H to imply Bayes optimality. We also show that if H satisfies our weak learning condition relative to another class C then multicalibration with respect to H implies multicalibration with respect to C. Finally we investigate the empirical performance of our algorithm experimentally using an open source implementation that we make available. 

   more » « less
4. Online Multivalid Learning: Means, Moments, and Prediction Intervals

   Varun Gupta; Christopher Jung; Georgy Noarov; Mallesh M. Pai; Aaron Roth (January 2022, Innovations in Theoretical Computer Science (ITCS))

   We present a general, efficient technique for providing contextual predictions that are "multivalid" in various senses, against an online sequence of adversarially chosen examples (x,y). This means that the resulting estimates correctly predict various statistics of the labels y not just marginally --- as averaged over the sequence of examples --- but also conditionally on x in G for any G belonging to an arbitrary intersecting collection of groups. We provide three instantiations of this framework. The first is mean prediction, which corresponds to an online algorithm satisfying the notion of multicalibration from Hebert-Johnson et al. The second is variance and higher moment prediction, which corresponds to an online algorithm satisfying the notion of mean-conditioned moment multicalibration from Jung et al. Finally, we define a new notion of prediction interval multivalidity, and give an algorithm for finding prediction intervals which satisfy it. Because our algorithms handle adversarially chosen examples, they can equally well be used to predict statistics of the residuals of arbitrary point prediction methods, giving rise to very general techniques for quantifying the uncertainty of predictions of black box algorithms, even in an online adversarial setting. When instantiated for prediction intervals, this solves a similar problem as conformal prediction, but in an adversarial environment and with multivalidity guarantees stronger than simple marginal coverage guarantees. 

   more » « less
5. Enhancing diastolic function by strain-dependent detachment of cardiac myosin crossbridges

   https://doi.org/10.1085/jgp.201912484  

   Palmer, Bradley M.; Swank, Douglas M.; Miller, Mark S.; Tanner, Bertrand C. W.; Meyer, Markus; LeWinter, Martin M. (March 2020, Journal of General Physiology)

   The force response of cardiac muscle undergoing a quick stretch is conventionally interpreted to represent stretching of attached myosin crossbridges (phase 1) and detachment of these stretched crossbridges at an exponential rate (phase 2), followed by crossbridges reattaching in increased numbers due to an enhanced activation of the thin filament (phases 3 and 4). We propose that, at least in mammalian cardiac muscle, phase 2 instead represents an enhanced detachment rate of myosin crossbridges due to stretch, phase 3 represents the reattachment of those same crossbridges, and phase 4 is a passive-like viscoelastic response with power-law relaxation. To test this idea, we developed a two-state model of crossbridge attachment and detachment. Unitary force was assigned when a crossbridge was attached, and an elastic force was generated when an attached crossbridge was displaced. Attachment rate, f(x), was spatially distributed with a total magnitude f0. Detachment rate was modeled as g(x) = g0+ g1x, where g0 is a constant and g1 indicates sensitivity to displacement. The analytical solution suggested that the exponential decay rate of phase 2 represents (f0 + g0) and the exponential rise rate of phase 3 represents g0. The depth of the nadir between phases 2 and 3 is proportional to g1. We prepared skinned mouse myocardium and applied a 1% stretch under varying concentrations of inorganic phosphate (Pi). The resulting force responses fitted the analytical solution well. The interpretations of phases 2 and 3 were consistent with lower f0 and higher g0 with increasing Pi. This novel scheme of interpreting the force response to a quick stretch does not require enhanced thin-filament activation and suggests that the myosin detachment rate is sensitive to stretch. Furthermore, the enhanced detachment rate is likely not due to the typical detachment mechanism following MgATP binding, but rather before MgADP release, and may involve reversal of the myosin power stroke. 

   more » « less