TY - CONF AB - Greedy optimization methods such as Matching Pursuit (MP) and Frank-Wolfe (FW) algorithms regained popularity in recent years due to their simplicity, effectiveness and theoretical guarantees. MP and FW address optimization over the linear span and the convex hull of a set of atoms, respectively. In this paper, we consider the intermediate case of optimization over the convex cone, parametrized as the conic hull of a generic atom set, leading to the first principled definitions of non-negative MP algorithms for which we give explicit convergence rates and demonstrate excellent empirical performance. In particular, we derive sublinear (O(1/t)) convergence on general smooth and convex objectives, and linear convergence (O(e−t)) on strongly convex objectives, in both cases for general sets of atoms. Furthermore, we establish a clear correspondence of our algorithms to known algorithms from the MP and FW literature. Our novel algorithms and analyses target general atom sets and general objective functions, and hence are directly applicable to a large variety of learning settings. AU - Locatello, Francesco AU - Tschannen, Michael AU - Rätsch, Gunnar AU - Jaggi, Martin ID - 14206 SN - 9781510860964 T2 - Advances in Neural Information Processing Systems TI - Greedy algorithms for cone constrained optimization with convergence guarantees ER - TY - CONF AB - Two of the most fundamental prototypes of greedy optimization are the matching pursuit and Frank-Wolfe algorithms. In this paper, we take a unified view on both classes of methods, leading to the first explicit convergence rates of matching pursuit methods in an optimization sense, for general sets of atoms. We derive sublinear (1/t) convergence for both classes on general smooth objectives, and linear convergence on strongly convex objectives, as well as a clear correspondence of algorithm variants. Our presented algorithms and rates are affine invariant, and do not need any incoherence or sparsity assumptions. AU - Locatello, Francesco AU - Khanna, Rajiv AU - Tschannen, Michael AU - Jaggi, Martin ID - 14205 T2 - Proceedings of the 20th International Conference on Artificial Intelligence and Statistics TI - A unified optimization view on generalized matching pursuit and Frank-Wolfe VL - 54 ER - TY - THES AB - Restriction-modification (RM) represents the simplest and possibly the most widespread mechanism of self/non-self discrimination in nature. In order to provide bacteria with immunity against bacteriophages and other parasitic genetic elements, RM systems rely on a balance between two enzymes: the restriction enzyme, which cleaves non-self DNA at specific restriction sites, and the modification enzyme, which tags the host’s DNA as self and thus protects it from cleavage. In this thesis, I use population and single-cell level experiments in combination with mathematical modeling to study different aspects of the interplay between RM systems, bacteria and bacteriophages. First, I analyze how mutations in phage restriction sites affect the probability of phage escape – an inherently stochastic process, during which phages accidently get modified instead of restricted. Next, I use single-cell experiments to show that RM systems can, with a low probability, attack the genome of their bacterial host and that this primitive form of autoimmunity leads to a tradeoff between the evolutionary cost and benefit of RM systems. Finally, I investigate the nature of interactions between bacteria, RM systems and temperate bacteriophages to find that, as a consequence of phage escape and its impact on population dynamics, RM systems can promote acquisition of symbiotic bacteriophages, rather than limit it. The results presented here uncover new fundamental biological properties of RM systems and highlight their importance in the ecology and evolution of bacteria, bacteriophages and their interactions. AU - Pleska, Maros ID - 202 SN - 2663-337X TI - Biology of restriction-modification systems at the single-cell and population level ER - TY - THES AB - The main objects considered in the present work are simplicial and CW-complexes with vertices forming a random point cloud. In particular, we consider a Poisson point process in R^n and study Delaunay and Voronoi complexes of the first and higher orders and weighted Delaunay complexes obtained as sections of Delaunay complexes, as well as the Čech complex. Further, we examine theDelaunay complex of a Poisson point process on the sphere S^n, as well as of a uniform point cloud, which is equivalent to the convex hull, providing a connection to the theory of random polytopes. Each of the complexes in question can be endowed with a radius function, which maps its cells to the radii of appropriately chosen circumspheres, called the radius of the cell. Applying and developing discrete Morse theory for these functions, joining it together with probabilistic and sometimes analytic machinery, and developing several integral geometric tools, we aim at getting the distributions of circumradii of typical cells. For all considered complexes, we are able to generalize and obtain up to constants the distribution of radii of typical intervals of all types. In low dimensions the constants can be computed explicitly, thus providing the explicit expressions for the expected numbers of cells. In particular, it allows to find the expected density of simplices of every dimension for a Poisson point process in R^4, whereas the result for R^3 was known already in 1970's. AU - Nikitenko, Anton ID - 6287 SN - 2663-337X TI - Discrete Morse theory for random complexes ER - TY - THES AB - Plant hormone auxin and its transport between cells belong to the most important mechanisms controlling plant development. Auxin itself could change localization of PINs and thereby control direction of its own flow. We performed an expression profiling experiment in Arabidopsis roots to identify potential regulators of PIN polarity which are transcriptionally regulated by auxin signalling. We identified several novel regulators and performed a detailed characterization of the transcription factor WRKY23 (At2g47260) and its role in auxin feedback on PIN polarity. Gain-of-function and dominant-negative mutants revealed that WRKY23 plays a crucial role in mediating the auxin effect on PIN polarity. In concordance, typical polar auxin transport processes such as gravitropism and leaf vascular pattern formation were disturbed by interfering with WRKY23 function. In order to identify direct targets of WRKY23, we performed consequential expression profiling experiments using a WRKY23 inducible gain-of-function line and dominant-negative WRKY23 line that is defunct in PIN re-arrangement. Among several genes mostly related to the groups of cell wall and defense process regulators, we identified LYSINE-HISTIDINE TRANSPORTER 1 (LHT1; At5g40780), a small amino acid permease gene from the amino acid/auxin permease family (AAAP), we present its detailed characterisation in auxin feedback on PIN repolarization, identified its transcriptional regulation, we propose a potential mechanism of its action. Moreover, we identified also a member of receptor-like protein kinase LRR-RLK (LEUCINE-RICH REPEAT TRANSMEMBRANE PROTEIN KINASE PROTEIN 1; LRRK1; At1g05700), which also affects auxin-dependent PIN re-arrangement. We described its transcriptional behaviour, subcellular localization. Based on global expression data, we tried to identify ligand responsible for mechanism of signalling and suggest signalling partner and interactors. Additionally, we described role of novel phytohormone group, strigolactone, in auxin-dependent PIN re-arrangement, that could be a fundament for future studies in this field. Our results provide first insights into an auxin transcriptional network targeting PIN localization and thus regulating plant development. We highlighted WRKY23 transcriptional network and characterised its mediatory role in plant development. We identified direct effectors of this network, LHT1 and LRRK1, and describe their roles in PIN re-arrangement and PIN-dependent auxin transport processes. AU - Prat, Tomas ID - 1127 SN - 2663-337X TI - Identification of novel regulators of PIN polarity and development of novel auxin sensor ER -