@article{9629,
abstract = {Intestinal organoids derived from single cells undergo complex crypt–villus patterning and morphogenesis. However, the nature and coordination of the underlying forces remains poorly characterized. Here, using light-sheet microscopy and large-scale imaging quantification, we demonstrate that crypt formation coincides with a stark reduction in lumen volume. We develop a 3D biophysical model to computationally screen different mechanical scenarios of crypt morphogenesis. Combining this with live-imaging data and multiple mechanical perturbations, we show that actomyosin-driven crypt apical contraction and villus basal tension work synergistically with lumen volume reduction to drive crypt morphogenesis, and demonstrate the existence of a critical point in differential tensions above which crypt morphology becomes robust to volume changes. Finally, we identified a sodium/glucose cotransporter that is specific to differentiated enterocytes that modulates lumen volume reduction through cell swelling in the villus region. Together, our study uncovers the cellular basis of how cell fate modulates osmotic and actomyosin forces to coordinate robust morphogenesis.},
author = {Yang, Qiutan and Xue, Shi-lei and Chan, Chii Jou and Rempfler, Markus and Vischi, Dario and Maurer-Gutierrez, Francisca and Hiiragi, Takashi and Hannezo, Edouard B and Liberali, Prisca},
issn = {14764679},
journal = {Nature Cell Biology},
publisher = {Springer Nature},
title = {{Cell fate coordinates mechano-osmotic forces in intestinal crypt formation}},
doi = {10.1038/s41556-021-00700-2},
year = {2021},
}
@article{9641,
abstract = {At the encounter with a novel environment, contextual memory formation is greatly enhanced, accompanied with increased arousal and active exploration. Although this phenomenon has been widely observed in animal and human daily life, how the novelty in the environment is detected and contributes to contextual memory formation has lately started to be unveiled. The hippocampus has been studied for many decades for its largely known roles in encoding spatial memory, and a growing body of evidence indicates a differential involvement of dorsal and ventral hippocampal divisions in novelty detection. In this brief review article, we discuss the recent findings of the role of mossy cells in the ventral hippocampal moiety in novelty detection and put them in perspective with other novelty-related pathways in the hippocampus. We propose a mechanism for novelty-driven memory acquisition in the dentate gyrus by the direct projection of ventral mossy cells to dorsal dentate granule cells. By this projection, the ventral hippocampus sends novelty signals to the dorsal hippocampus, opening a gate for memory encoding in dentate granule cells based on information coming from the entorhinal cortex. We conclude that, contrary to the presently accepted functional independence, the dorsal and ventral hippocampi cooperate to link the novelty and contextual information, and this dorso-ventral interaction is crucial for the novelty-dependent memory formation.},
author = {Fredes, Felipe and Shigemoto, Ryuichi},
issn = {10959564},
journal = {Neurobiology of Learning and Memory},
publisher = {Elsevier},
title = {{The role of hippocampal mossy cells in novelty detection}},
doi = {10.1016/j.nlm.2021.107486},
volume = {183},
year = {2021},
}
@article{9679,
abstract = {The relative motion of three impenetrable particles on a ring, in our case two identical fermions and one impurity, is isomorphic to a triangular quantum billiard. Depending on the ratio κ of the impurity and fermion masses, the billiards can be integrable or non-integrable (also referred to in the main text as chaotic). To set the stage, we first investigate the energy level distributions of the billiards as a function of 1/κ ∈ [0, 1] and find no evidence of integrable cases beyond the limiting values 1/κ = 1 and 1/κ = 0. Then, we use machine learning tools to analyze properties of probability distributions of individual quantum states. We find that convolutional neural networks can correctly classify integrable and non-integrable states. The decisive features of the wave functions are the normalization and a large number of zero elements, corresponding to the existence of a nodal line. The network achieves typical accuracies of 97%, suggesting that machine learning tools can be used to analyze and classify the morphology of probability densities obtained in theory or experiment.},
author = {Huber, David and Marchukov, Oleksandr V. and Hammer, Hans Werner and Volosniev, Artem},
issn = {13672630},
journal = {New Journal of Physics},
number = {6},
publisher = {IOP Publishing},
title = {{Morphology of three-body quantum states from machine learning}},
doi = {10.1088/1367-2630/ac0576},
volume = {23},
year = {2021},
}
@article{9657,
abstract = {To overcome nitrogen deficiency, legume roots establish symbiotic interactions with nitrogen-fixing rhizobia that is fostered in specialized organs (nodules). Similar to other organs, nodule formation is determined by a local maximum of the phytohormone auxin at the primordium site. However, how auxin regulates nodule development remains poorly understood. Here, we found that in soybean, (Glycine max), dynamic auxin transport driven by PIN-FORMED (PIN) transporter GmPIN1 is involved in nodule primordium formation. GmPIN1 was specifically expressed in nodule primordium cells and GmPIN1 was polarly localized in these cells. Two nodulation regulators, (iso)flavonoids trigger expanded distribution of GmPIN1b to root cortical cells, and cytokinin rearranges GmPIN1b polarity. Gmpin1abc triple mutants generated with CRISPR-Cas9 showed impaired establishment of auxin maxima in nodule meristems and aberrant divisions in the nodule primordium cells. Moreover, overexpression of GmPIN1 suppressed nodule primordium initiation. GmPIN9d, an ortholog of Arabidopsis thaliana PIN2, acts together with GmPIN1 later in nodule development to acropetally transport auxin in vascular bundles, fine-tuning the auxin supply for nodule enlargement. Our findings reveal how PIN-dependent auxin transport modulates different aspects of soybean nodule development and suggest that establishment of auxin gradient is a prerequisite for the proper interaction between legumes and rhizobia.},
author = {Gao, Z and Chen, Z and Cui, Y and Ke, M and Xu, H and Xu, Q and Chen, J and Li, Y and Huang, L and Zhao, H and Huang, D and Mai, S and Xu, T and Liu, X and Li, S and Guan, Y and Yang, W and Friml, Jiří and Petrášek, J and Zhang, J and Chen, X},
issn = {1532-298x},
journal = {Plant Cell},
publisher = {American Society of Plant Biologists},
title = {{GmPIN-dependent polar auxin transport is involved in soybean nodule development}},
doi = {10.1093/plcell/koab183},
year = {2021},
}
@article{9656,
abstract = {Tropisms, growth responses to environmental stimuli such as light or gravity, are spectacular examples of adaptive plant development. The plant hormone auxin serves as a major coordinative signal. The PIN auxin exporters, through their dynamic polar subcellular localizations, redirect auxin fluxes in response to environmental stimuli and the resulting auxin gradients across organs underly differential cell elongation and bending. In this review, we discuss recent advances concerning regulations of PIN polarity during tropisms, focusing on PIN phosphorylation and trafficking. We also cover how environmental cues regulate PIN actions during tropisms, and a crucial role of auxin feedback on PIN polarity during bending termination. Finally, the interactions between different tropisms are reviewed to understand plant adaptive growth in the natural environment.},
author = {Han, Huibin and Adamowski, Maciek and Qi, Linlin and Alotaibi, SS and Friml, Jiří},
issn = {1469-8137},
journal = {New Phytologist},
publisher = {Wiley},
title = {{PIN-mediated polar auxin transport regulations in plant tropic responses}},
doi = {10.1111/nph.17617},
year = {2021},
}
@article{9627,
abstract = {We compute the deficiency spaces of operators of the form 𝐻𝐴⊗̂ 𝐼+𝐼⊗̂ 𝐻𝐵, for symmetric 𝐻𝐴 and self-adjoint 𝐻𝐵. This enables us to construct self-adjoint extensions (if they exist) by means of von Neumann's theory. The structure of the deficiency spaces for this case was asserted already in Ibort et al. [Boundary dynamics driven entanglement, J. Phys. A: Math. Theor. 47(38) (2014) 385301], but only proven under the restriction of 𝐻𝐵 having discrete, non-degenerate spectrum.},
author = {Lenz, Daniel and Weinmann, Timon and Wirth, Melchior},
issn = {14643839},
journal = {Proceedings of the Edinburgh Mathematical Society},
pages = {1--15},
publisher = {Cambridge University Press},
title = {{Self-adjoint extensions of bipartite Hamiltonians}},
doi = {10.1017/S0013091521000080},
year = {2021},
}
@article{9647,
abstract = {Gene expression is regulated by the set of transcription factors (TFs) that bind to the promoter. The ensuing regulating function is often represented as a combinational logic circuit, where output (gene expression) is determined by current input values (promoter bound TFs) only. However, the simultaneous arrival of TFs is a strong assumption, since transcription and translation of genes introduce intrinsic time delays and there is no global synchronisation among the arrival times of different molecular species at their targets. We present an experimentally implementable genetic circuit with two inputs and one output, which in the presence of small delays in input arrival, exhibits qualitatively distinct population-level phenotypes, over timescales that are longer than typical cell doubling times. From a dynamical systems point of view, these phenotypes represent long-lived transients: although they converge to the same value eventually, they do so after a very long time span. The key feature of this toy model genetic circuit is that, despite having only two inputs and one output, it is regulated by twenty-three distinct DNA-TF configurations, two of which are more stable than others (DNA looped states), one promoting and another blocking the expression of the output gene. Small delays in input arrival time result in a majority of cells in the population quickly reaching the stable state associated with the first input, while exiting of this stable state occurs at a slow timescale. In order to mechanistically model the behaviour of this genetic circuit, we used a rule-based modelling language, and implemented a grid-search to find parameter combinations giving rise to long-lived transients. Our analysis shows that in the absence of feedback, there exist path-dependent gene regulatory mechanisms based on the long timescale of transients. The behaviour of this toy model circuit suggests that gene regulatory networks can exploit event timing to create phenotypes, and it opens the possibility that they could use event timing to memorise events, without regulatory feedback. The model reveals the importance of (i) mechanistically modelling the transitions between the different DNA-TF states, and (ii) employing transient analysis thereof.},
author = {Petrov, Tatjana and Igler, Claudia and Sezgin, Ali and Henzinger, Thomas A and Guet, Calin C},
issn = {03043975},
journal = {Theoretical Computer Science},
publisher = {Elsevier},
title = {{Long lived transients in gene regulation}},
doi = {10.1016/j.tcs.2021.05.023},
year = {2021},
}
@inproceedings{9646,
abstract = {We consider the fundamental problem of deriving quantitative bounds on the probability that a given assertion is violated in a probabilistic program. We provide automated algorithms that obtain both lower and upper bounds on the assertion violation probability. The main novelty of our approach is that we prove new and dedicated fixed-point theorems which serve as the theoretical basis of our algorithms and enable us to reason about assertion violation bounds in terms of pre and post fixed-point functions. To synthesize such fixed-points, we devise algorithms that utilize a wide range of mathematical tools, including repulsing ranking supermartingales, Hoeffding's lemma, Minkowski decompositions, Jensen's inequality, and convex optimization. On the theoretical side, we provide (i) the first automated algorithm for lower-bounds on assertion violation probabilities, (ii) the first complete algorithm for upper-bounds of exponential form in affine programs, and (iii) provably and significantly tighter upper-bounds than the previous approaches. On the practical side, we show our algorithms can handle a wide variety of programs from the literature and synthesize bounds that are remarkably tighter than previous results, in some cases by thousands of orders of magnitude.},
author = {Wang, Jinyi and Sun, Yican and Fu, Hongfei and Chatterjee, Krishnendu and Goharshady, Amir Kafshdar},
booktitle = {Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation},
isbn = {9781450383912},
location = {Online},
pages = {1171--1186},
publisher = {Association for Computing Machinery},
title = {{Quantitative analysis of assertion violations in probabilistic programs}},
doi = {10.1145/3453483.3454102},
year = {2021},
}
@inproceedings{9645,
abstract = {We consider the fundamental problem of reachability analysis over imperative programs with real variables. Previous works that tackle reachability are either unable to handle programs consisting of general loops (e.g. symbolic execution), or lack completeness guarantees (e.g. abstract interpretation), or are not automated (e.g. incorrectness logic). In contrast, we propose a novel approach for reachability analysis that can handle general and complex loops, is complete, and can be entirely automated for a wide family of programs. Through the notion of Inductive Reachability Witnesses (IRWs), our approach extends ideas from both invariant generation and termination to reachability analysis.
We first show that our IRW-based approach is sound and complete for reachability analysis of imperative programs. Then, we focus on linear and polynomial programs and develop automated methods for synthesizing linear and polynomial IRWs. In the linear case, we follow the well-known approaches using Farkas' Lemma. Our main contribution is in the polynomial case, where we present a push-button semi-complete algorithm. We achieve this using a novel combination of classical theorems in real algebraic geometry, such as Putinar's Positivstellensatz and Hilbert's Strong Nullstellensatz. Finally, our experimental results show we can prove complex reachability objectives over various benchmarks that were beyond the reach of previous methods.},
author = {Asadi, Ali and Chatterjee, Krishnendu and Fu, Hongfei and Goharshady, Amir Kafshdar and Mahdavi, Mohammad},
booktitle = {Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation},
isbn = {9781450383912},
location = {Online},
pages = {772--787},
publisher = {Association for Computing Machinery},
title = {{Polynomial reachability witnesses via Stellensätze}},
doi = {10.1145/3453483.3454076},
year = {2021},
}
@inproceedings{9644,
abstract = {We present a new approach to proving non-termination of non-deterministic integer programs. Our technique is rather simple but efficient. It relies on a purely syntactic reversal of the program's transition system followed by a constraint-based invariant synthesis with constraints coming from both the original and the reversed transition system. The latter task is performed by a simple call to an off-the-shelf SMT-solver, which allows us to leverage the latest advances in SMT-solving. Moreover, our method offers a combination of features not present (as a whole) in previous approaches: it handles programs with non-determinism, provides relative completeness guarantees and supports programs with polynomial arithmetic. The experiments performed with our prototype tool RevTerm show that our approach, despite its simplicity and stronger theoretical guarantees, is at least on par with the state-of-the-art tools, often achieving a non-trivial improvement under a proper configuration of its parameters.},
author = {Chatterjee, Krishnendu and Goharshady, Ehsan Kafshdar and Novotný, Petr and Zikelic, Dorde},
booktitle = {Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation},
isbn = {9781450383912},
location = {Online},
pages = {1033--1048},
publisher = {Association for Computing Machinery},
title = {{Proving non-termination by program reversal}},
doi = {10.1145/3453483.3454093},
year = {2021},
}
@article{9649,
abstract = {Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f : Rd → Rd−n. A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation T of the ambient space Rd. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently
fine triangulation T . This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary.},
author = {Boissonnat, Jean-Daniel and Wintraecken, Mathijs},
journal = {Foundations of Computational Mathematics },
publisher = {Springer Nature},
title = {{The topological correctness of PL approximations of isomanifolds}},
doi = {10.1007/s10208-021-09520-0},
year = {2021},
}
@inproceedings{9678,
abstract = {We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.},
author = {Brandt, Sebastian and Keller, Barbara and Rybicki, Joel and Suomela, Jukka and Uitto, Jara},
booktitle = {Annual ACM Symposium on Parallelism in Algorithms and Architectures},
isbn = {9781450380706},
location = { Virtual Event, United States},
pages = {129--139},
title = {{Efficient load-balancing through distributed token dropping}},
doi = {10.1145/3409964.3461785},
year = {2021},
}
@inproceedings{9441,
abstract = {Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation M̂ based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂ is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M̂ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. },
author = {Boissonnat, Jean-Daniel and Kachanovich, Siargey and Wintraecken, Mathijs},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
isbn = {978-3-95977-184-9},
issn = {1868-8969},
location = {Virtual},
pages = {17:1--17:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations}},
doi = {10.4230/LIPIcs.SoCG.2021.17},
volume = {189},
year = {2021},
}
@inproceedings{9620,
abstract = {In this note, we introduce a distributed twist on the classic coupon collector problem: a set of m collectors wish to each obtain a set of n coupons; for this, they can each sample coupons uniformly at random, but can also meet in pairwise interactions, during which they can exchange coupons. By doing so, they hope to reduce the number of coupons that must be sampled by each collector in order to obtain a full set. This extension is natural when considering real-world manifestations of the coupon collector phenomenon, and has been remarked upon and studied empirically (Hayes and Hannigan 2006, Ahmad et al. 2014, Delmarcelle 2019).
We provide the first theoretical analysis for such a scenario. We find that “coupon collecting with friends” can indeed significantly reduce the number of coupons each collector must sample, and raises interesting connections to the more traditional variants of the problem. While our analysis is in most cases asymptotically tight, there are several open questions raised, regarding finer-grained analysis of both “coupon collecting with friends,” and of a long-studied variant of the original problem in which a collector requires multiple full sets of coupons.},
author = {Alistarh, Dan-Adrian and Davies, Peter},
booktitle = {Structural Information and Communication Complexity},
isbn = {9783030795269},
issn = {1611-3349},
location = {Wrocław, Poland},
pages = {3--12},
publisher = {Springer Nature},
title = {{Collecting coupons is faster with friends}},
doi = {10.1007/978-3-030-79527-6_1},
volume = {12810},
year = {2021},
}
@inproceedings{9200,
abstract = {Formal design of embedded and cyber-physical systems relies on mathematical modeling. In this paper, we consider the model class of hybrid automata whose dynamics are defined by affine differential equations. Given a set of time-series data, we present an algorithmic approach to synthesize a hybrid automaton exhibiting behavior that is close to the data, up to a specified precision, and changes in synchrony with the data. A fundamental problem in our synthesis algorithm is to check membership of a time series in a hybrid automaton. Our solution integrates reachability and optimization techniques for affine dynamical systems to obtain both a sufficient and a necessary condition for membership, combined in a refinement framework. The algorithm processes one time series at a time and hence can be interrupted, provide an intermediate result, and be resumed. We report experimental results demonstrating the applicability of our synthesis approach.},
author = {Garcia Soto, Miriam and Henzinger, Thomas A and Schilling, Christian},
booktitle = {HSCC '21: Proceedings of the 24th International Conference on Hybrid Systems: Computation and Control},
isbn = {9781450383394},
keywords = {hybrid automaton, membership, system identification},
location = {Nashville, TN, United States},
pages = {2102.12734},
publisher = {Association for Computing Machinery},
title = {{Synthesis of hybrid automata with affine dynamics from time-series data}},
doi = {10.1145/3447928.3456704},
year = {2021},
}
@inproceedings{9345,
abstract = {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.},
author = {Edelsbrunner, Herbert and Heiss, Teresa and Kurlin , Vitaliy and Smith, Philip and Wintraecken, Mathijs},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
issn = {1868-8969},
location = {Virtual},
pages = {32:1--32:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{The density fingerprint of a periodic point set}},
doi = {10.4230/LIPIcs.SoCG.2021.32},
volume = {189},
year = {2021},
}
@inproceedings{9296,
abstract = { 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.},
author = {Aichholzer, Oswin and Arroyo Guevara, Alan M and Masárová, Zuzana and Parada, Irene and Perz, Daniel and Pilz, Alexander and Tkadlec, Josef and Vogtenhuber, Birgit},
booktitle = {15th International Conference on Algorithms and Computation},
isbn = {9783030682101},
issn = {16113349},
location = {Yangon, Myanmar},
pages = {221--233},
publisher = {Springer Nature},
title = {{On compatible matchings}},
doi = {10.1007/978-3-030-68211-8_18},
volume = {12635},
year = {2021},
}
@inproceedings{9466,
abstract = {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.},
author = {Walter, Michael},
booktitle = {Public-Key Cryptography – PKC 2021},
isbn = {9783030752446},
issn = {16113349},
location = {Virtual},
pages = {45--67},
publisher = {Springer Nature},
title = {{The convergence of slide-type reductions}},
doi = {10.1007/978-3-030-75245-3_3},
volume = {12710},
year = {2021},
}
@inproceedings{9210,
abstract = {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.},
author = {Volhejn, Vaclav and Lampert, Christoph},
booktitle = {42nd German Conference on Pattern Recognition },
isbn = {9783030712778},
issn = {16113349},
location = {Tübingen, Germany},
pages = {246--259},
publisher = {Springer},
title = {{Does SGD implicitly optimize for smoothness?}},
doi = {10.1007/978-3-030-71278-5_18},
volume = {12544 LNCS},
year = {2021},
}
@article{9640,
abstract = {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.},
author = {Tkadlec, Josef and Pavlogiannis, Andreas and Chatterjee, Krishnendu and Nowak, Martin A.},
issn = {20411723},
journal = {Nature Communications},
number = {1},
publisher = {Springer Nature},
title = {{Fast and strong amplifiers of natural selection}},
doi = {10.1038/s41467-021-24271-w},
volume = {12},
year = {2021},
}