@inproceedings{14208, abstract = {This paper focuses on over-parameterized deep neural networks (DNNs) with ReLU activation functions and proves that when the data distribution is well-separated, DNNs can achieve Bayes-optimal test error for classification while obtaining (nearly) zero-training error under the lazy training regime. For this purpose, we unify three interrelated concepts of overparameterization, benign overfitting, and the Lipschitz constant of DNNs. Our results indicate that interpolating with smoother functions leads to better generalization. Furthermore, we investigate the special case where interpolating smooth ground-truth functions is performed by DNNs under the Neural Tangent Kernel (NTK) regime for generalization. Our result demonstrates that the generalization error converges to a constant order that only depends on label noise and initialization noise, which theoretically verifies benign overfitting. Our analysis provides a tight lower bound on the normalized margin under non-smooth activation functions, as well as the minimum eigenvalue of NTK under high-dimensional settings, which has its own interest in learning theory.}, author = {Zhu, Zhenyu and Liu, Fanghui and Chrysos, Grigorios G and Locatello, Francesco and Cevher, Volkan}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, location = {Honolulu, Hawaii, United States}, pages = {43105--43128}, publisher = {ML Research Press}, title = {{Benign overfitting in deep neural networks under lazy training}}, volume = {202}, year = {2023}, } @unpublished{14209, abstract = {Diffusion models excel at generating photorealistic images from text-queries. Naturally, many approaches have been proposed to use these generative abilities to augment training datasets for downstream tasks, such as classification. However, diffusion models are themselves trained on large noisily supervised, but nonetheless, annotated datasets. It is an open question whether the generalization capabilities of diffusion models beyond using the additional data of the pre-training process for augmentation lead to improved downstream performance. We perform a systematic evaluation of existing methods to generate images from diffusion models and study new extensions to assess their benefit for data augmentation. While we find that personalizing diffusion models towards the target data outperforms simpler prompting strategies, we also show that using the training data of the diffusion model alone, via a simple nearest neighbor retrieval procedure, leads to even stronger downstream performance. Overall, our study probes the limitations of diffusion models for data augmentation but also highlights its potential in generating new training data to improve performance on simple downstream vision tasks.}, author = {Burg, Max F. and Wenzel, Florian and Zietlow, Dominik and Horn, Max and Makansi, Osama and Locatello, Francesco and Russell, Chris}, booktitle = {arXiv}, title = {{A data augmentation perspective on diffusion models and retrieval}}, doi = {10.48550/arXiv.2304.10253}, year = {2023}, } @unpublished{14210, abstract = {Recovering the latent factors of variation of high dimensional data has so far focused on simple synthetic settings. Mostly building on unsupervised and weakly-supervised objectives, prior work missed out on the positive implications for representation learning on real world data. In this work, we propose to leverage knowledge extracted from a diversified set of supervised tasks to learn a common disentangled representation. Assuming each supervised task only depends on an unknown subset of the factors of variation, we disentangle the feature space of a supervised multi-task model, with features activating sparsely across different tasks and information being shared as appropriate. Importantly, we never directly observe the factors of variations but establish that access to multiple tasks is sufficient for identifiability under sufficiency and minimality assumptions. We validate our approach on six real world distribution shift benchmarks, and different data modalities (images, text), demonstrating how disentangled representations can be transferred to real settings.}, author = {Fumero, Marco and Wenzel, Florian and Zancato, Luca and Achille, Alessandro and Rodolà, Emanuele and Soatto, Stefano and Schölkopf, Bernhard and Locatello, Francesco}, booktitle = {arXiv}, title = {{Leveraging sparse and shared feature activations for disentangled representation learning}}, doi = {10.48550/arXiv.2304.07939}, year = {2023}, } @inproceedings{14211, abstract = {Causal discovery methods are intrinsically constrained by the set of assumptions needed to ensure structure identifiability. Moreover additional restrictions are often imposed in order to simplify the inference task: this is the case for the Gaussian noise assumption on additive non-linear models, which is common to many causal discovery approaches. In this paper we show the shortcomings of inference under this hypothesis, analyzing the risk of edge inversion under violation of Gaussianity of the noise terms. Then, we propose a novel method for inferring the topological ordering of the variables in the causal graph, from data generated according to an additive non-linear model with a generic noise distribution. This leads to NoGAM (Not only Gaussian Additive noise Models), a causal discovery algorithm with a minimal set of assumptions and state of the art performance, experimentally benchmarked on synthetic data.}, author = {Montagna, Francesco and Noceti, Nicoletta and Rosasco, Lorenzo and Zhang, Kun and Locatello, Francesco}, booktitle = {2nd Conference on Causal Learning and Reasoning}, location = {Tübingen, Germany}, title = {{Causal discovery with score matching on additive models with arbitrary noise}}, year = {2023}, } @inproceedings{14212, abstract = {This paper demonstrates how to discover the whole causal graph from the second derivative of the log-likelihood in observational non-linear additive Gaussian noise models. Leveraging scalable machine learning approaches to approximate the score function ∇logp(X), we extend the work of Rolland et al. (2022) that only recovers the topological order from the score and requires an expensive pruning step removing spurious edges among those admitted by the ordering. Our analysis leads to DAS (acronym for Discovery At Scale), a practical algorithm that reduces the complexity of the pruning by a factor proportional to the graph size. In practice, DAS achieves competitive accuracy with current state-of-the-art while being over an order of magnitude faster. Overall, our approach enables principled and scalable causal discovery, significantly lowering the compute bar.}, author = {Montagna, Francesco and Noceti, Nicoletta and Rosasco, Lorenzo and Zhang, Kun and Locatello, Francesco}, booktitle = {2nd Conference on Causal Learning and Reasoning}, location = {Tübingen, Germany}, title = {{Scalable causal discovery with score matching}}, year = {2023}, } @inproceedings{14214, abstract = {Recent years have seen a surge of interest in learning high-level causal representations from low-level image pairs under interventions. Yet, existing efforts are largely limited to simple synthetic settings that are far away from real-world problems. In this paper, we present Causal Triplet, a causal representation learning benchmark featuring not only visually more complex scenes, but also two crucial desiderata commonly overlooked in previous works: (i) an actionable counterfactual setting, where only certain object-level variables allow for counterfactual observations whereas others do not; (ii) an interventional downstream task with an emphasis on out-of-distribution robustness from the independent causal mechanisms principle. Through extensive experiments, we find that models built with the knowledge of disentangled or object-centric representations significantly outperform their distributed counterparts. However, recent causal representation learning methods still struggle to identify such latent structures, indicating substantial challenges and opportunities for future work.}, author = {Liu, Yuejiang and Alahi, Alexandre and Russell, Chris and Horn, Max and Zietlow, Dominik and Schölkopf, Bernhard and Locatello, Francesco}, booktitle = {2nd Conference on Causal Learning and Reasoning}, location = {Tübingen, Germany}, title = {{Causal triplet: An open challenge for intervention-centric causal representation learning}}, year = {2023}, } @inproceedings{14216, abstract = {CLIP proved that aligning visual and language spaces is key to solving many vision tasks without explicit training, but required to train image and text encoders from scratch on a huge dataset. LiT improved this by only training the text encoder and using a pre-trained vision network. In this paper, we show that a common space can be created without any training at all, using single-domain encoders (trained with or without supervision) and a much smaller amount of image-text pairs. Furthermore, our model has unique properties. Most notably, deploying a new version with updated training samples can be done in a matter of seconds. Additionally, the representations in the common space are easily interpretable as every dimension corresponds to the similarity of the input to a unique entry in the multimodal dataset. Experiments on standard zero-shot visual benchmarks demonstrate the typical transfer ability of image-text models. Overall, our method represents a simple yet surprisingly strong baseline for foundation multi-modal models, raising important questions on their data efficiency and on the role of retrieval in machine learning.}, author = {Norelli, Antonio and Fumero, Marco and Maiorca, Valentino and Moschella, Luca and Rodolà, Emanuele and Locatello, Francesco}, booktitle = {37th Conference on Neural Information Processing Systems}, isbn = {9781713899921}, location = {New Orleans, LA, United States}, pages = {15303--15319}, publisher = {Neural Information Processing Systems Foundation}, title = {{ASIF: Coupled data turns unimodal models to multimodal without training}}, volume = {36}, year = {2023}, } @inproceedings{14217, abstract = {Neural networks embed the geometric structure of a data manifold lying in a high-dimensional space into latent representations. Ideally, the distribution of the data points in the latent space should depend only on the task, the data, the loss, and other architecture-specific constraints. However, factors such as the random weights initialization, training hyperparameters, or other sources of randomness in the training phase may induce incoherent latent spaces that hinder any form of reuse. Nevertheless, we empirically observe that, under the same data and modeling choices, the angles between the encodings within distinct latent spaces do not change. In this work, we propose the latent similarity between each sample and a fixed set of anchors as an alternative data representation, demonstrating that it can enforce the desired invariances without any additional training. We show how neural architectures can leverage these relative representations to guarantee, in practice, invariance to latent isometries and rescalings, effectively enabling latent space communication: from zero-shot model stitching to latent space comparison between diverse settings. We extensively validate the generalization capability of our approach on different datasets, spanning various modalities (images, text, graphs), tasks (e.g., classification, reconstruction) and architectures (e.g., CNNs, GCNs, transformers).}, author = {Moschella, Luca and Maiorca, Valentino and Fumero, Marco and Norelli, Antonio and Locatello, Francesco and Rodolà, Emanuele}, booktitle = {The 11th International Conference on Learning Representations}, location = {Kigali, Rwanda}, title = {{Relative representations enable zero-shot latent space communication}}, year = {2023}, } @inproceedings{14218, abstract = {Humans naturally decompose their environment into entities at the appropriate level of abstraction to act in the world. Allowing machine learning algorithms to derive this decomposition in an unsupervised way has become an important line of research. However, current methods are restricted to simulated data or require additional information in the form of motion or depth in order to successfully discover objects. In this work, we overcome this limitation by showing that reconstructing features from models trained in a self-supervised manner is a sufficient training signal for object-centric representations to arise in a fully unsupervised way. Our approach, DINOSAUR, significantly out-performs existing image-based object-centric learning models on simulated data and is the first unsupervised object-centric model that scales to real-world datasets such as COCO and PASCAL VOC. DINOSAUR is conceptually simple and shows competitive performance compared to more involved pipelines from the computer vision literature.}, author = {Seitzer, Maximilian and Horn, Max and Zadaianchuk, Andrii and Zietlow, Dominik and Xiao, Tianjun and Carl-Johann Simon-Gabriel, Carl-Johann Simon-Gabriel and He, Tong and Zhang, Zheng and Schölkopf, Bernhard and Brox, Thomas and Locatello, Francesco}, booktitle = {The 11th International Conference on Learning Representations}, location = {Kigali, Rwanda}, title = {{Bridging the gap to real-world object-centric learning}}, year = {2023}, } @inproceedings{14219, abstract = {In this paper, we show that recent advances in self-supervised feature learning enable unsupervised object discovery and semantic segmentation with a performance that matches the state of the field on supervised semantic segmentation 10 years ago. We propose a methodology based on unsupervised saliency masks and self-supervised feature clustering to kickstart object discovery followed by training a semantic segmentation network on pseudo-labels to bootstrap the system on images with multiple objects. We present results on PASCAL VOC that go far beyond the current state of the art (50.0 mIoU), and we report for the first time results on MS COCO for the whole set of 81 classes: our method discovers 34 categories with more than $20\%$ IoU, while obtaining an average IoU of 19.6 for all 81 categories.}, author = {Zadaianchuk, Andrii and Kleindessner, Matthaeus and Zhu, Yi and Locatello, Francesco and Brox, Thomas}, booktitle = {The 11th International Conference on Learning Representations}, location = {Kigali, Rwanda}, title = {{Unsupervised semantic segmentation with self-supervised object-centric representations}}, year = {2023}, } @inproceedings{14222, abstract = {Learning generative object models from unlabelled videos is a long standing problem and required for causal scene modeling. We decompose this problem into three easier subtasks, and provide candidate solutions for each of them. Inspired by the Common Fate Principle of Gestalt Psychology, we first extract (noisy) masks of moving objects via unsupervised motion segmentation. Second, generative models are trained on the masks of the background and the moving objects, respectively. Third, background and foreground models are combined in a conditional "dead leaves" scene model to sample novel scene configurations where occlusions and depth layering arise naturally. To evaluate the individual stages, we introduce the Fishbowl dataset positioned between complex real-world scenes and common object-centric benchmarks of simplistic objects. We show that our approach allows learning generative models that generalize beyond the occlusions present in the input videos, and represent scenes in a modular fashion that allows sampling plausible scenes outside the training distribution by permitting, for instance, object numbers or densities not observed in the training set.}, author = {Tangemann, Matthias and Schneider, Steffen and Kügelgen, Julius von and Locatello, Francesco and Gehler, Peter and Brox, Thomas and Kümmerer, Matthias and Bethge, Matthias and Schölkopf, Bernhard}, booktitle = {2nd Conference on Causal Learning and Reasoning}, location = {Tübingen, Germany}, title = {{Unsupervised object learning via common fate}}, year = {2023}, } @article{14238, abstract = {We demonstrate that a sodium dimer, Na2(13Σ+u), residing on the surface of a helium nanodroplet, can be set into rotation by a nonresonant 1.0 ps infrared laser pulse. The time-dependent degree of alignment measured, exhibits a periodic, gradually decreasing structure that deviates qualitatively from that expected for gas-phase dimers. Comparison to alignment dynamics calculated from the time-dependent rotational Schrödinger equation shows that the deviation is due to the alignment dependent interaction between the dimer and the droplet surface. This interaction confines the dimer to the tangential plane of the droplet surface at the point where it resides and is the reason that the observed alignment dynamics is also well described by a 2D quantum rotor model.}, author = {Kranabetter, Lorenz and Kristensen, Henrik H. and Ghazaryan, Areg and Schouder, Constant A. and Chatterley, Adam S. and Janssen, Paul and Jensen, Frank and Zillich, Robert E. and Lemeshko, Mikhail and Stapelfeldt, Henrik}, issn = {1079-7114}, journal = {Physical Review Letters}, number = {5}, publisher = {American Physical Society}, title = {{Nonadiabatic laser-induced alignment dynamics of molecules on a surface}}, doi = {10.1103/PhysRevLett.131.053201}, volume = {131}, year = {2023}, } @article{14239, abstract = {Given a resolution of rational singularities π:X~→X over a field of characteristic zero, we use a Hodge-theoretic argument to prove that the image of the functor Rπ∗:Db(X~)→Db(X) between bounded derived categories of coherent sheaves generates Db(X) as a triangulated category. This gives a weak version of the Bondal–Orlov localization conjecture [BO02], answering a question from [PS21]. The same result is established more generally for proper (not necessarily birational) morphisms π:X~→X , with X~ smooth, satisfying Rπ∗(OX~)=OX .}, author = {Mauri, Mirko and Shinder, Evgeny}, issn = {2050-5094}, journal = {Forum of Mathematics, Sigma}, publisher = {Cambridge University Press}, title = {{Homological Bondal-Orlov localization conjecture for rational singularities}}, doi = {10.1017/fms.2023.65}, volume = {11}, year = {2023}, } @article{14240, abstract = {This paper introduces a novel method for simulating large bodies of water as a height field. At the start of each time step, we partition the waves into a bulk flow (which approximately satisfies the assumptions of the shallow water equations) and surface waves (which approximately satisfy the assumptions of Airy wave theory). We then solve the two wave regimes separately using appropriate state-of-the-art techniques, and re-combine the resulting wave velocities at the end of each step. This strategy leads to the first heightfield wave model capable of simulating complex interactions between both deep and shallow water effects, like the waves from a boat wake sloshing up onto a beach, or a dam break producing wave interference patterns and eddies. We also analyze the numerical dispersion created by our method and derive an exact correction factor for waves at a constant water depth, giving us a numerically perfect re-creation of theoretical water wave dispersion patterns.}, author = {Jeschke, Stefan and Wojtan, Christopher J}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {Association for Computing Machinery}, title = {{Generalizing shallow water simulations with dispersive surface waves}}, doi = {10.1145/3592098}, volume = {42}, year = {2023}, } @inproceedings{14241, abstract = {We present a technique to optimize the reflectivity of a surface while preserving its overall shape. The naïve optimization of the mesh vertices using the gradients of reflectivity simulations results in undesirable distortion. In contrast, our robust formulation optimizes the surface normal as an independent variable that bridges the reflectivity term with differential rendering, and the regularization term with as-rigid-as-possible elastic energy. We further adaptively subdivide the input mesh to improve the convergence. Consequently, our method can minimize the retroreflectivity of a wide range of input shapes, resulting in sharply creased shapes ubiquitous among stealth aircraft and Sci-Fi vehicles. Furthermore, by changing the reward for the direction of the outgoing light directions, our method can be applied to other reflectivity design tasks, such as the optimization of architectural walls to concentrate light in a specific region. We have tested the proposed method using light-transport simulations and real-world 3D-printed objects.}, author = {Tojo, Kenji and Shamir, Ariel and Bickel, Bernd and Umetani, Nobuyuki}, booktitle = {SIGGRAPH 2023 Conference Proceedings}, isbn = {9798400701597}, location = {Los Angeles, CA, United States}, publisher = {Association for Computing Machinery}, title = {{Stealth shaper: Reflectivity optimization as surface stylization}}, doi = {10.1145/3588432.3591542}, year = {2023}, } @inproceedings{14242, abstract = {We study the problem of training and certifying adversarially robust quantized neural networks (QNNs). Quantization is a technique for making neural networks more efficient by running them using low-bit integer arithmetic and is therefore commonly adopted in industry. Recent work has shown that floating-point neural networks that have been verified to be robust can become vulnerable to adversarial attacks after quantization, and certification of the quantized representation is necessary to guarantee robustness. In this work, we present quantization-aware interval bound propagation (QA-IBP), a novel method for training robust QNNs. Inspired by advances in robust learning of non-quantized networks, our training algorithm computes the gradient of an abstract representation of the actual network. Unlike existing approaches, our method can handle the discrete semantics of QNNs. Based on QA-IBP, we also develop a complete verification procedure for verifying the adversarial robustness of QNNs, which is guaranteed to terminate and produce a correct answer. Compared to existing approaches, the key advantage of our verification procedure is that it runs entirely on GPU or other accelerator devices. We demonstrate experimentally that our approach significantly outperforms existing methods and establish the new state-of-the-art for training and certifying the robustness of QNNs.}, author = {Lechner, Mathias and Zikelic, Dorde and Chatterjee, Krishnendu and Henzinger, Thomas A and Rus, Daniela}, booktitle = {Proceedings of the 37th AAAI Conference on Artificial Intelligence}, isbn = {9781577358800}, location = {Washington, DC, United States}, number = {12}, pages = {14964--14973}, publisher = {Association for the Advancement of Artificial Intelligence}, title = {{Quantization-aware interval bound propagation for training certifiably robust quantized neural networks}}, doi = {10.1609/aaai.v37i12.26747}, volume = {37}, year = {2023}, } @inproceedings{14243, abstract = {Two-player zero-sum "graph games" are central in logic, verification, and multi-agent systems. The game proceeds by placing a token on a vertex of a graph, and allowing the players to move it to produce an infinite path, which determines the winner or payoff of the game. Traditionally, the players alternate turns in moving the token. In "bidding games", however, the players have budgets and in each turn, an auction (bidding) determines which player moves the token. So far, bidding games have only been studied as full-information games. In this work we initiate the study of partial-information bidding games: we study bidding games in which a player's initial budget is drawn from a known probability distribution. We show that while for some bidding mechanisms and objectives, it is straightforward to adapt the results from the full-information setting to the partial-information setting, for others, the analysis is significantly more challenging, requires new techniques, and gives rise to interesting results. Specifically, we study games with "mean-payoff" objectives in combination with "poorman" bidding. We construct optimal strategies for a partially-informed player who plays against a fully-informed adversary. We show that, somewhat surprisingly, the "value" under pure strategies does not necessarily exist in such games.}, author = {Avni, Guy and Jecker, Ismael R and Zikelic, Dorde}, booktitle = {Proceedings of the 37th AAAI Conference on Artificial Intelligence}, isbn = {9781577358800}, location = {Washington, DC, United States}, number = {5}, pages = {5464--5471}, title = {{Bidding graph games with partially-observable budgets}}, doi = {10.1609/aaai.v37i5.25679}, volume = {37}, year = {2023}, } @article{14244, abstract = {In this paper, we determine the motivic class — in particular, the weight polynomial and conjecturally the Poincaré polynomial — of the open de Rham space, defined and studied by Boalch, of certain moduli spaces of irregular meromorphic connections on the trivial rank bundle on P1. The computation is by motivic Fourier transform. We show that the result satisfies the purity conjecture, that is, it agrees with the pure part of the conjectured mixed Hodge polynomial of the corresponding wild character variety. We also identify the open de Rham spaces with quiver varieties with multiplicities of Yamakawa and Geiss–Leclerc–Schröer. We finish with constructing natural complete hyperkähler metrics on them, which in the four-dimensional cases are expected to be of type ALF.}, author = {Hausel, Tamás and Wong, Michael Lennox and Wyss, Dimitri}, issn = {1460-244X}, journal = {Proceedings of the London Mathematical Society}, number = {4}, pages = {958--1027}, publisher = {Wiley}, title = {{Arithmetic and metric aspects of open de Rham spaces}}, doi = {10.1112/plms.12555}, volume = {127}, year = {2023}, } @article{14245, abstract = {We establish effective counting results for lattice points in families of domains in real, complex and quaternionic hyperbolic spaces of any dimension. The domains we focus on are defined as product sets with respect to an Iwasawa decomposition. Several natural diophantine problems can be reduced to counting lattice points in such domains. These include equidistribution of the ratio of the length of the shortest solution (x,y) to the gcd equation bx−ay=1 relative to the length of (a,b), where (a,b) ranges over primitive vectors in a disc whose radius increases, the natural analog of this problem in imaginary quadratic number fields, as well as equidistribution of integral solutions to the diophantine equation defined by an integral Lorentz form in three or more variables. We establish an effective rate of convergence for these equidistribution problems, depending on the size of the spectral gap associated with a suitable lattice subgroup in the isometry group of the relevant hyperbolic space. The main result underlying our discussion amounts to establishing effective joint equidistribution for the horospherical component and the radial component in the Iwasawa decomposition of lattice elements.}, author = {Horesh, Tal and Nevo, Amos}, issn = {1945-5844}, journal = {Pacific Journal of Mathematics}, number = {2}, pages = {265--294}, publisher = {Mathematical Sciences Publishers}, title = {{Horospherical coordinates of lattice points in hyperbolic spaces: Effective counting and equidistribution}}, doi = {10.2140/pjm.2023.324.265}, volume = {324}, year = {2023}, } @article{14246, abstract = {The model of a ring threaded by the Aharonov-Bohm flux underlies our understanding of a coupling between gauge potentials and matter. The typical formulation of the model is based upon a single particle picture, and should be extended when interactions with other particles become relevant. Here, we illustrate such an extension for a particle in an Aharonov-Bohm ring subject to interactions with a weakly interacting Bose gas. We show that the ground state of the system can be described using the Bose-polaron concept—a particle dressed by interactions with a bosonic environment. We connect the energy spectrum to the effective mass of the polaron, and demonstrate how to change currents in the system by tuning boson-particle interactions. Our results suggest the Aharonov-Bohm ring as a platform for studying coherence and few- to many-body crossover of quasi-particles that arise from an impurity immersed in a medium.}, author = {Brauneis, Fabian and Ghazaryan, Areg and Hammer, Hans-Werner and Volosniev, Artem}, issn = {2399-3650}, journal = {Communications Physics}, keywords = {General Physics and Astronomy}, publisher = {Springer Nature}, title = {{Emergence of a Bose polaron in a small ring threaded by the Aharonov-Bohm flux}}, doi = {10.1038/s42005-023-01281-2}, volume = {6}, year = {2023}, }