TY - CONF
AB - Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functionsthat facilitates the efficient search for new materials and material properties. We prove invarianceunder isometries, continuity, and completeness in the generic case, which are necessary featuresfor the reliable comparison of crystals. The proof of continuity integrates methods from discretegeometry and lattice theory, while the proof of generic completeness combines techniques fromgeometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and relatedinclusion-exclusion formulae. We have implemented the algorithm and describe its application tocrystal structure prediction.
AU - Edelsbrunner, Herbert
AU - Heiss, Teresa
AU - Kurlin , Vitaliy
AU - Smith, Philip
AU - Wintraecken, Mathijs
ID - 9345
SN - 1868-8969
T2 - 37th International Symposium on Computational Geometry (SoCG 2021)
TI - The density fingerprint of a periodic point set
VL - 189
ER -
TY - CONF
AB - matching is compatible to two or more labeled point sets of size n with labels {1,…,n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(logn) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.
AU - Aichholzer, Oswin
AU - Arroyo Guevara, Alan M
AU - Masárová, Zuzana
AU - Parada, Irene
AU - Perz, Daniel
AU - Pilz, Alexander
AU - Tkadlec, Josef
AU - Vogtenhuber, Birgit
ID - 9296
SN - 03029743
T2 - 15th International Conference on Algorithms and Computation
TI - On compatible matchings
VL - 12635
ER -
TY - CONF
AB - In this work, we apply the dynamical systems analysis of Hanrot et al. (CRYPTO’11) to a class of lattice block reduction algorithms that includes (natural variants of) slide reduction and block-Rankin reduction. This implies sharper bounds on the polynomial running times (in the query model) for these algorithms and opens the door to faster practical variants of slide reduction. We give heuristic arguments showing that such variants can indeed speed up slide reduction significantly in practice. This is confirmed by experimental evidence, which also shows that our variants are competitive with state-of-the-art reduction algorithms.
AU - Walter, Michael
ID - 9466
SN - 03029743
T2 - Public-Key Cryptography – PKC 2021
TI - The convergence of slide-type reductions
VL - 12710
ER -
TY - CONF
AB - Modern neural networks can easily fit their training set perfectly. Surprisingly, despite being “overfit” in this way, they tend to generalize well to future data, thereby defying the classic bias–variance trade-off of machine learning theory. Of the many possible explanations, a prevalent one is that training by stochastic gradient descent (SGD) imposes an implicit bias that leads it to learn simple functions, and these simple functions generalize well. However, the specifics of this implicit bias are not well understood.
In this work, we explore the smoothness conjecture which states that SGD is implicitly biased towards learning functions that are smooth. We propose several measures to formalize the intuitive notion of smoothness, and we conduct experiments to determine whether SGD indeed implicitly optimizes for these measures. Our findings rule out the possibility that smoothness measures based on first-order derivatives are being implicitly enforced. They are supportive, though, of the smoothness conjecture for measures based on second-order derivatives.
AU - Volhejn, Vaclav
AU - Lampert, Christoph
ID - 9210
SN - 03029743
T2 - 42nd German Conference on Pattern Recognition
TI - Does SGD implicitly optimize for smoothness?
VL - 12544 LNCS
ER -
TY - JOUR
AB - Selection and random drift determine the probability that novel mutations fixate in a population. Population structure is known to affect the dynamics of the evolutionary process. Amplifiers of selection are population structures that increase the fixation probability of beneficial mutants compared to well-mixed populations. Over the past 15 years, extensive research has produced remarkable structures called strong amplifiers which guarantee that every beneficial mutation fixates with high probability. But strong amplification has come at the cost of considerably delaying the fixation event, which can slow down the overall rate of evolution. However, the precise relationship between fixation probability and time has remained elusive. Here we characterize the slowdown effect of strong amplification. First, we prove that all strong amplifiers must delay the fixation event at least to some extent. Second, we construct strong amplifiers that delay the fixation event only marginally as compared to the well-mixed populations. Our results thus establish a tight relationship between fixation probability and time: Strong amplification always comes at a cost of a slowdown, but more than a marginal slowdown is not needed.
AU - Tkadlec, Josef
AU - Pavlogiannis, Andreas
AU - Chatterjee, Krishnendu
AU - Nowak, Martin A.
ID - 9640
IS - 1
JF - Nature Communications
TI - Fast and strong amplifiers of natural selection
VL - 12
ER -
TY - THES
AB - Deep learning is best known for its empirical success across a wide range of applications
spanning computer vision, natural language processing and speech. Of equal significance,
though perhaps less known, are its ramifications for learning theory: deep networks have
been observed to perform surprisingly well in the high-capacity regime, aka the overfitting
or underspecified regime. Classically, this regime on the far right of the bias-variance curve
is associated with poor generalisation; however, recent experiments with deep networks
challenge this view.
This thesis is devoted to investigating various aspects of underspecification in deep learning.
First, we argue that deep learning models are underspecified on two levels: a) any given
training dataset can be fit by many different functions, and b) any given function can be
expressed by many different parameter configurations. We refer to the second kind of
underspecification as parameterisation redundancy and we precisely characterise its extent.
Second, we characterise the implicit criteria (the inductive bias) that guide learning in the
underspecified regime. Specifically, we consider a nonlinear but tractable classification
setting, and show that given the choice, neural networks learn classifiers with a large margin.
Third, we consider learning scenarios where the inductive bias is not by itself sufficient to
deal with underspecification. We then study different ways of ‘tightening the specification’: i)
In the setting of representation learning with variational autoencoders, we propose a hand-
crafted regulariser based on mutual information. ii) In the setting of binary classification, we
consider soft-label (real-valued) supervision. We derive a generalisation bound for linear
networks supervised in this way and verify that soft labels facilitate fast learning. Finally, we
explore an application of soft-label supervision to the training of multi-exit models.
AU - Bui Thi Mai, Phuong
ID - 9418
TI - Underspecification in Deep Learning
ER -
TY - CONF
AB - We consider the problem ofdistributed mean estimation (DME), in which n machines are each given a local d-dimensional vector xv∈Rd, and must cooperate to estimate the mean of their inputs μ=1n∑nv=1xv, while minimizing total communication cost. DME is a fundamental construct in distributed machine learning, and there has been considerable work on variants of this problem, especially in the context of distributed variance reduction for stochastic gradients in parallel SGD. Previous work typically assumes an upper bound on the norm of the input vectors, and achieves an error bound in terms of this norm. However, in many real applications, the input vectors are concentrated around the correct output μ, but μ itself has large norm. In such cases, previous output error bounds perform poorly. In this paper, we show that output error bounds need not depend on input norm. We provide a method of quantization which allows distributed mean estimation to be performed with solution quality dependent only on the distance between inputs, not on input norm, and show an analogous result for distributed variance reduction. The technique is based on a new connection with lattice theory. We also provide lower bounds showing that the communication to error trade-off of our algorithms is asymptotically optimal. As the lattices achieving optimal bounds under l2-norm can be computationally impractical, we also present an extension which leverages easy-to-use cubic lattices, and is loose only up to a logarithmic factor ind. We show experimentally that our method yields practical improvements for common applications, relative to prior approaches.
AU - Davies, Peter
AU - Gurunanthan, Vijaykrishna
AU - Moshrefi, Niusha
AU - Ashkboos, Saleh
AU - Alistarh, Dan-Adrian
ID - 9543
T2 - 9th International Conference on Learning Representations
TI - New bounds for distributed mean estimation and variance reduction
ER -
TY - CONF
AB - We study the inductive bias of two-layer ReLU networks trained by gradient flow. We identify a class of easy-to-learn (`orthogonally separable') datasets, and characterise the solution that ReLU networks trained on such datasets converge to. Irrespective of network width, the solution turns out to be a combination of two max-margin classifiers: one corresponding to the positive data subset and one corresponding to the negative data subset. The proof is based on the recently introduced concept of extremal sectors, for which we prove a number of properties in the context of orthogonal separability. In particular, we prove stationarity of activation patterns from some time onwards, which enables a reduction of the ReLU network to an ensemble of linear subnetworks.
AU - Bui Thi Mai, Phuong
AU - Lampert, Christoph
ID - 9416
T2 - 9th International Conference on Learning Representations
TI - The inductive bias of ReLU networks on orthogonally separable data
ER -
TY - JOUR
AB - Turbulence in the flow of fluid through a pipe can be suppressed by buoyancy forces. As the suppression of turbulence leads to severe heat transfer deterioration, this is an important and undesirable phenomenon in both heating and cooling applications. Vertical flow is often considered, as the axial buoyancy force can help drive the flow. With heating measured by the buoyancy parameter 𝐶, our direct numerical simulations show that shear-driven turbulence may either be completely laminarised or it transitions to a relatively quiescent convection-driven state. Buoyancy forces cause a flattening of the base flow profile, which in isothermal pipe flow has recently been linked to complete suppression of turbulence (Kühnen et al., Nat. Phys., vol. 14, 2018, pp. 386–390), and the flattened laminar base profile has enhanced nonlinear stability (Marensi et al., J. Fluid Mech., vol. 863, 2019, pp. 50–875). In agreement with these findings, the nonlinear lower-branch travelling-wave solution analysed here, which is believed to mediate transition to turbulence in isothermal pipe flow, is shown to be suppressed by buoyancy. A linear instability of the laminar base flow is responsible for the appearance of the relatively quiescent convection driven state for 𝐶≳4 across the range of Reynolds numbers considered. In the suppression of turbulence, however, i.e. in the transition from turbulence, we find clearer association with the analysis of He et al. (J. Fluid Mech., vol. 809, 2016, pp. 31–71) than with the above dynamical systems approach, which describes better the transition to turbulence. The laminarisation criterion He et al. propose, based on an apparent Reynolds number of the flow as measured by its driving pressure gradient, is found to capture the critical 𝐶=𝐶𝑐𝑟(𝑅𝑒) above which the flow will be laminarised or switch to the convection-driven type. Our analysis suggests that it is the weakened rolls, rather than the streaks, which appear to be critical for laminarisation.
AU - Marensi, Elena
AU - He, Shuisheng
AU - Willis, Ashley P.
ID - 9467
JF - Journal of Fluid Mechanics
SN - 00221120
TI - Suppression of turbulence and travelling waves in a vertical heated pipe
VL - 919
ER -
TY - THES
AB - Most real-world flows are multiphase, yet we know little about them compared to their single-phase counterparts. Multiphase flows are more difficult to investigate as their dynamics occur in large parameter space and involve complex phenomena such as preferential concentration, turbulence modulation, non-Newtonian rheology, etc. Over the last few decades, experiments in particle-laden flows have taken a back seat in favour of ever-improving computational resources. However, computers are still not powerful enough to simulate a real-world fluid with millions of finite-size particles. Experiments are essential not only because they offer a reliable way to investigate real-world multiphase flows but also because they serve to validate numerical studies and steer the research in a relevant direction. In this work, we have experimentally investigated particle-laden flows in pipes, and in particular, examined the effect of particles on the laminar-turbulent transition and the drag scaling in turbulent flows.
For particle-laden pipe flows, an earlier study [Matas et al., 2003] reported how the sub-critical (i.e., hysteretic) transition that occurs via localised turbulent structures called puffs is affected by the addition of particles. In this study, in addition to this known transition, we found a super-critical transition to a globally fluctuating state with increasing particle concentration. At the same time, the Newtonian-type transition via puffs is delayed to larger Reynolds numbers. At an even higher concentration, only the globally fluctuating state is found. The dynamics of particle-laden flows are hence determined by two competing instabilities that give rise to three flow regimes: Newtonian-type turbulence at low, a particle-induced globally fluctuating state at high, and a coexistence state at intermediate concentrations.
The effect of particles on turbulent drag is ambiguous, with studies reporting drag reduction, no net change, and even drag increase. The ambiguity arises because, in addition to particle concentration, particle shape, size, and density also affect the net drag. Even similar particles might affect the flow dissimilarly in different Reynolds number and concentration ranges. In the present study, we explored a wide range of both Reynolds number and concentration, using spherical as well as cylindrical particles. We found that the spherical particles do not reduce drag while the cylindrical particles are drag-reducing within a specific Reynolds number interval. The interval strongly depends on the particle concentration and the relative size of the pipe and particles. Within this interval, the magnitude of drag reduction reaches a maximum. These drag reduction maxima appear to fall onto a distinct power-law curve irrespective of the pipe diameter and particle concentration, and this curve can be considered as the maximum drag reduction asymptote for a given fibre shape. Such an asymptote is well known for polymeric flows but had not been identified for particle-laden flows prior to this work.
AU - Agrawal, Nishchal
ID - 9728
KW - Drag Reduction
KW - Transition to Turbulence
KW - Multiphase Flows
KW - particle Laden Flows
KW - Complex Flows
KW - Experiments
KW - Fluid Dynamics
SN - 2663-337X
TI - Transition to turbulence and drag reduction in particle-laden pipe flows
ER -