[{"date_published":"2026-05-18T00:00:00Z","das_tickbox":"0","file_date_updated":"2026-06-22T08:18:41Z","page":"214-233","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"day":"18","date_created":"2026-06-14T22:01:44Z","status":"public","language":[{"iso":"eng"}],"acknowledgement":"We thank the anonymous reviewers for their helpful comments. This work was supported by the European Research Council (ERC) Grants VAMOS (No. 101020093) and HYPER (No. 101055412), and by the Advanced Research and Invention Agency under the Safeguarded AI programme (MSAI-PR01-P047).","abstract":[{"text":"Runtime monitoring checks, during execution, whether a partial signal produced by a hybrid system satisfies its specification. Signal First-Order Logic (SFO) offers expressive real-time specifications over such signals, but currently comes only with Boolean semantics and has no tool support. We provide the first robustness-based quantitative semantics for SFO, enabling the expression and evaluation of rich real-time properties beyond the scope of existing formalisms such as Signal Temporal Logic. To enable online monitoring, we identify a past-time fragment of SFO and give a pastification procedure that transforms bounded-response SFO formulas into equisatisfiable formulas in this fragment. We then develop an efficient runtime monitoring algorithm for this past-time fragment and evaluate its performance on a set of benchmarks, demonstrating the practicality and effectiveness of our approach. To the best of our knowledge, this is the first publicly available prototype for online quantitative monitoring of full SFO.","lang":"eng"}],"publication":"27th International Symposium on Formal Methods","intvolume":"     16557","doi":"10.1007/978-3-032-26220-2_11","oa_version":"Published Version","type":"conference","scopus_import":"1","file":[{"relation":"main_file","creator":"dernst","file_id":"22113","access_level":"open_access","date_updated":"2026-06-22T08:18:41Z","content_type":"application/pdf","success":1,"file_size":849237,"checksum":"7055199ecb985e9e2e272f4988827067","file_name":"2026_LNCS_Chalupa.pdf","date_created":"2026-06-22T08:18:41Z"}],"external_id":{"arxiv":["2603.00728"]},"author":[{"last_name":"Chalupa","first_name":"Marek","full_name":"Chalupa, Marek","id":"87e34708-d6c6-11ec-9f5b-9391e7be2463"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Sarac","first_name":"Naci E","full_name":"Sarac, Naci E","id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425"},{"id":"20aa2ae8-f2f1-11ed-bbfa-8205053f1342","orcid":"0000-0002-4993-773X","last_name":"Yu","first_name":"Zhengqi","full_name":"Yu, Zhengqi"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"_id":"62781420-2b32-11ec-9570-8d9b63373d4d","call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093"}],"publication_status":"published","article_processing_charge":"No","conference":{"start_date":"2026-05-18","location":"Tokyo, Japan","end_date":"2026-05-22","name":"FM: Formal Methods"},"citation":{"apa":"Chalupa, M., Henzinger, T. A., Sarac, N. E., &#38; Yu, E. (2026). Quantitative monitoring of Signal First-Order logic. In <i>27th International Symposium on Formal Methods</i> (Vol. 16557, pp. 214–233). Tokyo, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-26220-2_11\">https://doi.org/10.1007/978-3-032-26220-2_11</a>","ama":"Chalupa M, Henzinger TA, Sarac NE, Yu E. Quantitative monitoring of Signal First-Order logic. In: <i>27th International Symposium on Formal Methods</i>. Vol 16557. Springer Nature; 2026:214-233. doi:<a href=\"https://doi.org/10.1007/978-3-032-26220-2_11\">10.1007/978-3-032-26220-2_11</a>","ieee":"M. Chalupa, T. A. Henzinger, N. E. Sarac, and E. Yu, “Quantitative monitoring of Signal First-Order logic,” in <i>27th International Symposium on Formal Methods</i>, Tokyo, Japan, 2026, vol. 16557, pp. 214–233.","chicago":"Chalupa, Marek, Thomas A Henzinger, Naci E Sarac, and Emily Yu. “Quantitative Monitoring of Signal First-Order Logic.” In <i>27th International Symposium on Formal Methods</i>, 16557:214–33. Springer Nature, 2026. <a href=\"https://doi.org/10.1007/978-3-032-26220-2_11\">https://doi.org/10.1007/978-3-032-26220-2_11</a>.","short":"M. Chalupa, T.A. Henzinger, N.E. Sarac, E. Yu, in:, 27th International Symposium on Formal Methods, Springer Nature, 2026, pp. 214–233.","ista":"Chalupa M, Henzinger TA, Sarac NE, Yu E. 2026. Quantitative monitoring of Signal First-Order logic. 27th International Symposium on Formal Methods. FM: Formal Methods, LNCS, vol. 16557, 214–233.","mla":"Chalupa, Marek, et al. “Quantitative Monitoring of Signal First-Order Logic.” <i>27th International Symposium on Formal Methods</i>, vol. 16557, Springer Nature, 2026, pp. 214–33, doi:<a href=\"https://doi.org/10.1007/978-3-032-26220-2_11\">10.1007/978-3-032-26220-2_11</a>."},"ddc":["000"],"OA_place":"publisher","volume":16557,"oa":1,"has_accepted_license":"1","month":"05","OA_type":"hybrid","title":"Quantitative monitoring of Signal First-Order logic","arxiv":1,"_id":"22006","keyword":["Signal first-order logic","Robustness-based quantitative semantics","Online runtime monitoring"],"date_updated":"2026-06-22T08:21:09Z","fulldoi":"https://doi.org/10.1007/978-3-032-26220-2_11","publisher":"Springer Nature","year":"2026","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783032262196"],"issn":["0302-9743"]},"ec_funded":1,"department":[{"_id":"ToHe"}],"quality_controlled":"1","alternative_title":["LNCS"]},{"related_material":{"record":[{"id":"12537","relation":"part_of_dissertation","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"21324"},{"id":"22894","relation":"part_of_dissertation","status":"public"},{"id":"19627","relation":"part_of_dissertation","status":"public"},{"id":"12859","status":"public","relation":"part_of_dissertation"},{"id":"18973","status":"public","relation":"part_of_dissertation"},{"status":"public","relation":"part_of_dissertation","id":"18972"}]},"day":"08","corr_author":"1","das_tickbox":"0","date_published":"2026-09-08T00:00:00Z","page":"446","file_date_updated":"2026-09-10T10:03:48Z","acknowledgement":"This project was partially supported by the 2019 Lopez-Loreta prize,\r\nthe European Union (ERC, INF2\r\n, project number 101161364), the Austrian Science Fund\r\n(FWF) 10.55776/COE12, and a Google PhD fellowship in machine intelligence. Furthermore,\r\nthe candidate acknowledges the support from the Scientific Service Units of the Institute of\r\nScience and Technology Austria through resources provided by Scientific Computing.","status":"public","language":[{"iso":"eng"}],"supervisor":[{"orcid":"0000-0002-3242-7020","last_name":"Mondelli","first_name":"Marco","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"}],"abstract":[{"lang":"eng","text":"Artificial intelligence and machine learning have undergone an unprecedented evolution in the past decade, motivating a research effort toward a theory able to capture the qualitative behavior of large-scale neural systems. A central puzzle has been the clear benefit of scaling architecture size and overfitting the training set in supervised learning tasks. This evidence, in apparent contradiction with classical statistical learning theory, pushed researchers to develop a new theory capturing the interplay between the algorithmic and architectural bias of training and the specific target function, differently from previous methods rooted in uniform stability.\r\nThis approach has enabled a grounded understanding of novel learning regimes, typically through formal limits where the number of training samples $n$, data dimensions $d$, and model parameters $p$ grow to infinity at different rates. \\\\\r\nIn this thesis, we follow this approach, focusing on the trustworthiness of high-dimensional models: properties that are difficult to control during training or deployment and often emerge under unpredictable or adversarial conditions. In such settings, it is crucial to formally ensure a priori the reliability of machine learning systems.\r\nFirst, we study data memorization, both as label fitting and as the storage of private information about training samples in trained parameters. We prove that $p = \\Omega(n)$ parameters are sufficient for a deep neural network to memorize a generic set of labels, and for a model to memorize spurious features across training data. We then give evidence that $p = \\Omega(dn)$ parameters are instead necessary for an adversary to reconstruct the full training set from the trained parameters.\r\nSecond, we study robustness, both to adversarial perturbations and to distribution shift. We first prove that $p = \\Omega(dn)$ parameters can be sufficient for a class of neural networks to overfit the training data while guaranteeing robustness to adversarial perturbations. Then, we focus on spurious correlations learning in high-dimensional regression, studying the effect of the ridge regularization parameter in the proportional regime $n = \\Theta(d)$, and connecting it via an equivalence argument to the role of over-parameterization $p = \\Omega(n)$ in neural networks. We also investigate the architectural bias of attention-based networks, showing that they are sensitive to the replacement of individual words in an embedded sentence, allowing them to generalize on sentences where the contextual meaning depends on one or few words.\r\nFinally, we study differentially private optimization in high-dimensional regimes. We prove that standard private gradient methods do not suffer in the over-parameterized regime $p = \\Omega(n)$, challenging the current wisdom based on stability-derived generalization bounds. We then consider linear regression in the proportional regime $n = \\Theta(d)$, showing that standard private gradient descent can achieve optimal rates under appropriate hyper-parameter scaling, such as sufficiently small gradient clipping constants, whose role is still debated in practice."}],"date_created":"2026-09-08T13:40:08Z","file":[{"file_id":"22859","access_level":"closed","relation":"source_file","creator":"sbombari","checksum":"8eab99d6dc6e4476826bdfc7c00fdebb","file_name":"Thesis copy.zip","date_created":"2026-09-08T13:28:38Z","content_type":"application/zip","date_updated":"2026-09-08T13:28:38Z","file_size":99154325},{"creator":"sbombari","relation":"main_file","access_level":"open_access","file_id":"22898","success":1,"file_size":12856211,"content_type":"application/pdf","date_updated":"2026-09-10T10:03:48Z","date_created":"2026-09-10T10:03:48Z","file_name":"2026_Bombari_Simone_Thesis.pdf","checksum":"007033bafe4622ff4c2e758301354df1"}],"type":"dissertation","author":[{"id":"ca726dda-de17-11ea-bc14-f9da834f63aa","full_name":"Bombari, Simone","first_name":"Simone","last_name":"Bombari"}],"doi":"10.15479/AT-ISTA-22857","researchdata_availability":"no","doi_confirm":"1","oa_version":"Published Version","citation":{"apa":"Bombari, S. (2026). <i>Trustworthy machine learning in high dimensions</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-22857\">https://doi.org/10.15479/AT-ISTA-22857</a>","ama":"Bombari S. Trustworthy machine learning in high dimensions. 2026. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-22857\">10.15479/AT-ISTA-22857</a>","ieee":"S. Bombari, “Trustworthy machine learning in high dimensions,” Institute of Science and Technology Austria, 2026.","chicago":"Bombari, Simone. “Trustworthy Machine Learning in High Dimensions.” Institute of Science and Technology Austria, 2026. <a href=\"https://doi.org/10.15479/AT-ISTA-22857\">https://doi.org/10.15479/AT-ISTA-22857</a>.","short":"S. Bombari, Trustworthy Machine Learning in High Dimensions, Institute of Science and Technology Austria, 2026.","ista":"Bombari S. 2026. Trustworthy machine learning in high dimensions. Institute of Science and Technology Austria.","mla":"Bombari, Simone. <i>Trustworthy Machine Learning in High Dimensions</i>. Institute of Science and Technology Austria, 2026, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-22857\">10.15479/AT-ISTA-22857</a>."},"ddc":["519"],"supplementarymaterial":"no","article_processing_charge":"No","OA_place":"publisher","degree_awarded":"PhD","project":[{"_id":"92099302-16d5-11f0-9cad-f9a785f54fbd","name":"Trustworthy Deep Learning Theory: Private Over-Parameterized Models and Robust LLMs"},{"grant_number":"101161364","name":"Inference in High Dimensions: Light-speed Algorithms and Information Limits","_id":"911e6d1f-16d5-11f0-9cad-c5c68c6a1cdf"},{"_id":"74caaef7-b034-11f1-8f2d-e0e993bb422e","name":"Bilateral Artificial Intelligence (Mondelli)","grant_number":"COE12"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","publication_status":"published","title":"Trustworthy machine learning in high dimensions","has_accepted_license":"1","oa":1,"month":"09","acknowledged_ssus":[{"_id":"ScienComp"}],"date_updated":"2026-10-16T10:42:36Z","_id":"22857","keyword":["machine learning","high-dimensional statistics","deep learning theory","privacy","memorization","robustness"],"department":[{"_id":"GradSch"},{"_id":"MaMo"}],"fulldoi":"https://doi.org/10.15479/AT-ISTA-22857","year":"2026","publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-091-6"]},"publisher":"Institute of Science and Technology Austria","alternative_title":["ISTA Thesis"]},{"date_updated":"2026-04-07T14:19:48Z","keyword":["robustness","fairness","machine learning","PAC learning","adversarial learning"],"_id":"10799","title":"Robustness and fairness in machine learning","month":"03","has_accepted_license":"1","oa":1,"alternative_title":["ISTA Thesis"],"department":[{"_id":"GradSch"},{"_id":"ChLa"}],"publication_identifier":{"isbn":["978-3-99078-015-2"],"issn":["2663-337X"]},"ec_funded":1,"year":"2022","publisher":"Institute of Science and Technology Austria","fulldoi":"https://doi.org/10.15479/at:ista:10799","abstract":[{"text":"Because of the increasing popularity of machine learning methods, it is becoming important to understand the impact of learned components on automated decision-making systems and to guarantee that their consequences are beneficial to society. In other words, it is necessary to ensure that machine learning is sufficiently trustworthy to be used in real-world applications. This thesis studies two properties of machine learning models that are highly desirable for the\r\nsake of reliability: robustness and fairness. In the first part of the thesis we study the robustness of learning algorithms to training data corruption. Previous work has shown that machine learning models are vulnerable to a range\r\nof training set issues, varying from label noise through systematic biases to worst-case data manipulations. This is an especially relevant problem from a present perspective, since modern machine learning methods are particularly data hungry and therefore practitioners often have to rely on data collected from various external sources, e.g. from the Internet, from app users or via crowdsourcing. Naturally, such sources vary greatly in the quality and reliability of the\r\ndata they provide. With these considerations in mind, we study the problem of designing machine learning algorithms that are robust to corruptions in data coming from multiple sources. We show that, in contrast to the case of a single dataset with outliers, successful learning within this model is possible both theoretically and practically, even under worst-case data corruptions. The second part of this thesis deals with fairness-aware machine learning. There are multiple areas where machine learning models have shown promising results, but where careful considerations are required, in order to avoid discrimanative decisions taken by such learned components. Ensuring fairness can be particularly challenging, because real-world training datasets are expected to contain various forms of historical bias that may affect the learning process. In this thesis we show that data corruption can indeed render the problem of achieving fairness impossible, by tightly characterizing the theoretical limits of fair learning under worst-case data manipulations. However, assuming access to clean data, we also show how fairness-aware learning can be made practical in contexts beyond binary classification, in particular in the challenging learning to rank setting.","lang":"eng"}],"language":[{"iso":"eng"}],"status":"public","supervisor":[{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph","full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887","last_name":"Lampert"}],"date_created":"2022-02-28T13:03:49Z","day":"08","corr_author":"1","related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"10802"},{"id":"10803","relation":"part_of_dissertation","status":"public"},{"id":"6590","relation":"part_of_dissertation","status":"public"},{"id":"8724","relation":"part_of_dissertation","status":"public"}]},"page":"176","file_date_updated":"2022-03-10T12:11:48Z","date_published":"2022-03-08T00:00:00Z","OA_place":"publisher","degree_awarded":"PhD","ddc":["000"],"citation":{"chicago":"Konstantinov, Nikola H. “Robustness and Fairness in Machine Learning.” Institute of Science and Technology Austria, 2022. <a href=\"https://doi.org/10.15479/at:ista:10799\">https://doi.org/10.15479/at:ista:10799</a>.","short":"N.H. Konstantinov, Robustness and Fairness in Machine Learning, Institute of Science and Technology Austria, 2022.","apa":"Konstantinov, N. H. (2022). <i>Robustness and fairness in machine learning</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:10799\">https://doi.org/10.15479/at:ista:10799</a>","ama":"Konstantinov NH. Robustness and fairness in machine learning. 2022. doi:<a href=\"https://doi.org/10.15479/at:ista:10799\">10.15479/at:ista:10799</a>","ieee":"N. H. Konstantinov, “Robustness and fairness in machine learning,” Institute of Science and Technology Austria, 2022.","mla":"Konstantinov, Nikola H. <i>Robustness and Fairness in Machine Learning</i>. Institute of Science and Technology Austria, 2022, doi:<a href=\"https://doi.org/10.15479/at:ista:10799\">10.15479/at:ista:10799</a>.","ista":"Konstantinov NH. 2022. Robustness and fairness in machine learning. Institute of Science and Technology Austria."},"article_processing_charge":"No","publication_status":"published","project":[{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"665385","name":"International IST Doctoral Program"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","author":[{"id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87","full_name":"Konstantinov, Nikola H","first_name":"Nikola H","last_name":"Konstantinov","orcid":"0009-0009-5204-7621"}],"file":[{"date_created":"2022-03-06T11:42:54Z","file_name":"thesis.pdf","checksum":"626bc523ae8822d20e635d0e2d95182e","file_size":4204905,"success":1,"content_type":"application/pdf","date_updated":"2022-03-06T11:42:54Z","access_level":"open_access","file_id":"10823","relation":"main_file","creator":"nkonstan"},{"file_id":"10824","access_level":"closed","creator":"nkonstan","relation":"source_file","checksum":"e2ca2b88350ac8ea1515b948885cbcb1","file_name":"thesis.zip","date_created":"2022-03-06T11:42:57Z","date_updated":"2022-03-10T12:11:48Z","content_type":"application/x-zip-compressed","file_size":22841103}],"type":"dissertation","oa_version":"Published Version","doi":"10.15479/at:ista:10799"},{"article_processing_charge":"No","citation":{"mla":"Konstantinov, Nikola H., and Christoph Lampert. “Fairness-Aware PAC Learning from Corrupted Data.” <i>Journal of Machine Learning Research</i>, vol. 23, ML Research Press, 2022, pp. 1–60.","ista":"Konstantinov NH, Lampert C. 2022. Fairness-aware PAC learning from corrupted data. Journal of Machine Learning Research. 23, 1–60.","short":"N.H. Konstantinov, C. Lampert, Journal of Machine Learning Research 23 (2022) 1–60.","chicago":"Konstantinov, Nikola H, and Christoph Lampert. “Fairness-Aware PAC Learning from Corrupted Data.” <i>Journal of Machine Learning Research</i>. ML Research Press, 2022.","apa":"Konstantinov, N. H., &#38; Lampert, C. (2022). Fairness-aware PAC learning from corrupted data. <i>Journal of Machine Learning Research</i>. ML Research Press.","ama":"Konstantinov NH, Lampert C. Fairness-aware PAC learning from corrupted data. <i>Journal of Machine Learning Research</i>. 2022;23:1-60.","ieee":"N. H. Konstantinov and C. Lampert, “Fairness-aware PAC learning from corrupted data,” <i>Journal of Machine Learning Research</i>, vol. 23. ML Research Press, pp. 1–60, 2022."},"ddc":["004"],"volume":23,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","type":"journal_article","file":[{"checksum":"9cac897b54a0ddf3a553a2c33e88cfda","file_name":"2022_JournalMachineLearningResearch_Konstantinov.pdf","date_created":"2022-07-12T15:08:28Z","date_updated":"2022-07-12T15:08:28Z","content_type":"application/pdf","file_size":551862,"success":1,"file_id":"11570","access_level":"open_access","relation":"main_file","creator":"kschuh"}],"scopus_import":"1","external_id":{"arxiv":["2102.06004"]},"author":[{"id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0009-5204-7621","last_name":"Konstantinov","first_name":"Nikola H","full_name":"Konstantinov, Nikola H"},{"full_name":"Lampert, Christoph","first_name":"Christoph","last_name":"Lampert","orcid":"0000-0002-4561-241X","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"}],"intvolume":"        23","oa_version":"Published Version","status":"public","language":[{"iso":"eng"}],"acknowledgement":"The authors thank Eugenia Iofinova and Bernd Prach for providing feedback on early versions of this paper. This publication was made possible by an ETH AI Center postdoctoral fellowship to Nikola Konstantinov.","abstract":[{"lang":"eng","text":"Addressing fairness concerns about machine learning models is a crucial step towards their long-term adoption in real-world automated systems. While many approaches have been developed for training fair models from data, little is known about the robustness of these methods to data corruption. In this work we consider fairness-aware learning under worst-case data manipulations. We show that an adversary can in some situations force any learner to return an overly biased classifier, regardless of the sample size and with or without degrading\r\naccuracy, and that the strength of the excess bias increases for learning problems with underrepresented protected groups in the data. We also prove that our hardness results are tight up to constant factors. To this end, we study two natural learning algorithms that optimize for both accuracy and fairness and show that these algorithms enjoy guarantees that are order-optimal in terms of the corruption ratio and the protected groups frequencies in the large data\r\nlimit."}],"publication":"Journal of Machine Learning Research","date_created":"2022-02-28T14:05:42Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"related_material":{"record":[{"status":"public","relation":"shorter_version","id":"13241"},{"relation":"dissertation_contains","status":"public","id":"10799"}]},"corr_author":"1","day":"01","date_published":"2022-05-01T00:00:00Z","page":"1-60","file_date_updated":"2022-07-12T15:08:28Z","quality_controlled":"1","department":[{"_id":"ChLa"}],"publisher":"ML Research Press","year":"2022","publication_identifier":{"issn":["1532-4435"],"eissn":["1533-7928"]},"date_updated":"2026-04-07T14:19:48Z","_id":"10802","keyword":["Fairness","robustness","data poisoning","trustworthy machine learning","PAC learning"],"title":"Fairness-aware PAC learning from corrupted data","arxiv":1,"oa":1,"has_accepted_license":"1","month":"05","article_type":"original"}]
