More Like this

1. Adaptive Metrics for Adaptive Samples

   https://doi.org/10.3390/a13080200  

   Cavanna, Nicholas J.; Sheehy, Donald R. (August 2020, Algorithms)

   null (Ed.)

   We generalize the local-feature size definition of adaptive sampling used in surface reconstruction to relate it to an alternative metric on Euclidean space. In the new metric, adaptive samples become uniform samples, making it simpler both to give adaptive sampling versions of homological inference results and to prove topological guarantees using the critical points theory of distance functions. This ultimately leads to an algorithm for homology inference from samples whose spacing depends on their distance to a discrete representation of the complement space. 

   more » « less
2. Adaptive Incentive Design

   https://doi.org/10.1109/TAC.2020.3027503  

   Ratliff, Lillian J.; Fiez, Tanner (August 2021, IEEE Transactions on Automatic Control)

   null (Ed.)
3. Adaptive Machine Unlearning

   Varun Gupta; Christopher Jung; Seth Neel; Aaron Roth; Saeed Sharifi-Malvajerdi; Chris Waites (January 2021, Neural Information Processing Systems (NeurIPS))

   Data deletion algorithms aim to remove the influence of deleted data points from trained models at a cheaper computational cost than fully retraining those models. However, for sequences of deletions, most prior work in the non-convex setting gives valid guarantees only for sequences that are chosen independently of the models that are published. If people choose to delete their data as a function of the published models (because they don't like what the models reveal about them, for example), then the update sequence is adaptive. In this paper, we give a general reduction from deletion guarantees against adaptive sequences to deletion guarantees against non-adaptive sequences, using differential privacy and its connection to max information. Combined with ideas from prior work which give guarantees for non-adaptive deletion sequences, this leads to extremely flexible algorithms able to handle arbitrary model classes and training methodologies, giving strong provable deletion guarantees for adaptive deletion sequences. We show in theory how prior work for non-convex models fails against adaptive deletion sequences, and use this intuition to design a practical attack against the SISA algorithm of Bourtoule et al. [2021] on CIFAR-10, MNIST, Fashion-MNIST. 

   more » « less
4. Adaptive display images

   https://doi.org/10.1142/s0219530519410112  

   Zhi, Meipeng; Xu, Yuesheng (January 2020, Analysis and Applications)

   We develop a numerical method for construction of an adaptive display image from a given display image which is an artificial scene displayed in a computer screen. The adaptive display image is encoded on an adaptive pixel mesh obtained by a merging scheme from the original pixel mesh. The cardinality of the adaptive pixel mesh is significantly less than that of the original pixel mesh. The resulting adaptive display image is the best [Formula: see text] piecewise constant approximation of the original display image. Under the assumption that a natural image, the real scene that we see, belongs to a Besov space, we provide the optimal [Formula: see text] error estimate between the adaptive display image and its original natural image. Experimental results are presented to demonstrate the visual quality, the approximation accuracy and the computational complexity of the adaptive display image. 

   more » « less
5. Adaptive Schema Databases

   Spoth, W.; Arab, B. S.; Chan, E. S.; Gawlick, D.; Ghoneimy, A.; Glavic, B.; Hammerschmidt, B.; Kennedy, O.; Lee, S.; Liu, Z. H.; et al (January 2017, CIDR 2017, 8th Biennial Conference on Innovative Data Systems Research, Chaminade, CA, USA, January 8-11, 2017, Online Proceedings)

   The rigid schemas of classical relational databases help users in specifying queries and inform the storage organization of data. However, the advantages of schemas come at a high upfront cost through schema and ETL process design. In this work, we propose a new paradigm where the database system takes a more active role in schema development and data integration. We refer to this approach as adaptive schema databases (ASDs). An ASD ingests semi-structured or unstructured data directly using a pluggable combination of extraction and data integration techniques. Over time it discovers and adapts schemas for the ingested data using information provided by data integration and information extraction techniques, as well as from queries and user-feedback. In contrast to relational databases, ASDs maintain multiple schema workspaces that represent individualized views over the data, which are fine-tuned to the needs of a particular user or group of users. A novel aspect of ASDs is that probabilistic database techniques are used to encode ambiguity in automatically generated data extraction workflows and in generated schemas. ASDs can provide users with context-dependent feedback on the quality of a schema, both in terms of its ability to satisfy a user's queries, and the quality of the resulting answers. We outline our vision for ASDs, and present a proof of concept implementation as part of the Mimir probabilistic data curation system. 

   more » « less