@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},
}
@unpublished{9695,
abstract = {Real-world data typically contain a large number of features that are often heterogeneous in nature, relevance, and also units of measure. When assessing the similarity between data points, one can build various distance measures using subsets of these features. Using the fewest features but still retaining sufficient information about the system is crucial in many statistical learning approaches, particularly when data are sparse. We introduce a statistical test that can assess the relative information retained when using two different distance measures, and determine if they are equivalent, independent, or if one is more informative than the other. This in turn allows finding the most informative distance measure out of a pool of candidates. The approach is applied to find the most relevant policy variables for controlling the Covid-19 epidemic and to find compact yet informative representations of atomic structures, but its potential applications are wide ranging in many branches of science.},
author = {Glielmo, Aldo and Zeni, Claudio and Cheng, Bingqing and Csanyi, Gabor and Laio, Alessandro},
booktitle = {arXiv},
title = {{Ranking the information content of distance measures}},
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},
}
@unpublished{9696,
abstract = {Most water in the universe may be superionic, and its thermodynamic and transport properties are crucial for planetary science but difficult to probe experimentally or theoretically. We use machine learning and free energy methods to overcome the limitations of quantum mechanical simulations, and characterize hydrogen diffusion, superionic transitions, and phase behaviors of water at extreme conditions. We predict that a close-packed superionic phase with mixed stacking is stable over a wide temperature and pressure range, while a body-centered cubic phase is only thermodynamically stable in a small window but is kinetically favored. Our phase boundaries, which are consistent with the existing-albeit scarce-experimental observations, help resolve the fractions of insulating ice, different superionic phases, and liquid water inside of ice giants.},
author = {Cheng, Bingqing and Bethkenhagen, Mandy and Pickard, Chris J. and Hamel, Sebastien},
booktitle = {arXiv},
title = {{Predicting the phase behaviors of superionic water at planetary conditions}},
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},
}
@unpublished{9698,
abstract = {Machine learning models are poised to make a transformative impact on chemical sciences by dramatically accelerating computational algorithms and amplifying insights available from computational chemistry methods. However, achieving this requires a confluence and coaction of expertise in computer science and physical sciences. This review is written for new and experienced researchers working at the intersection of both fields. We first provide concise tutorials of computational chemistry and machine learning methods, showing how insights involving both can be achieved. We then follow with a critical review of noteworthy applications that demonstrate how computational chemistry and machine learning can be used together to provide insightful (and useful) predictions in molecular and materials modeling, retrosyntheses, catalysis, and drug design.},
author = {Keith, John A. and Valentin Vassilev-Galindo, Valentin and Cheng, Bingqing and Chmiela, Stefan and Gastegger, Michael and Müller, Klaus-Robert and Tkatchenko, Alexandre},
booktitle = {arXiv},
title = {{Combining machine learning and computational chemistry for predictive insights into chemical systems}},
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},
}