Gradient descent methods and especially their stochastic variants have become highly popular in the last decade due to their efficiency on big data optimization problems. In this thesis we present the development of data sampling strategies for these methods. In the first four chapters we focus on four views on the sampling for convex problems, developing and analyzing new state-of-the-art methods using non-standard data sampling strategies. Finally, in the last chapter we present a more flexible framework, which generalizes to more problems as well as more sampling rules. In the first chapter we propose an adaptive variant of stochastic dual coordinate ascent (SDCA) for solving the regularized empirical risk minimization (ERM) problem. Our modification consists in allowing the method to adaptively change the probability distribution over the dual variables throughout the iterative process. AdaSDCA achieves a provably better complexity bound than SDCA with the best fixed probability distribution, known as importance sampling. However, it is of a theoretical character as it is expensive to implement. We also propose AdaSDCA+: a practical variant which in our experiments outperforms existing non-adaptive methods. In the second chapter we extend the dual-free analysis of SDCA, to arbitrary mini-batching schemes. Our method is able to better utilize the information in the data defining the ERM problem. For convex loss functions, our complexity results match those of QUARTZ, which is a primal-dual method also allowing for arbitrary mini-batching schemes. The advantage of a dual-free analysis comes from the fact that it guarantees convergence even for non-convex loss functions, as long as the average loss is convex. We illustrate through experiments the utility of being able to design arbitrary mini-batching schemes. In the third chapter we study importance sampling of minibatches. Minibatching is a well studied and highly popular technique in supervised learning, used by practitioners due to its ability to accelerate training through better utilization of parallel processing power and reduction of stochastic variance. Another popular technique is importance sampling { a strategy for preferential sampling of more important examples also capable of accelerating the training process. However, despite considerable effort by the community in these areas, and due to the inherent technical difficulty of the problem, there is no existing work combining the power of importance sampling with the strength of minibatching. In this chapter we propose the first importance sampling for minibatches and give simple and rigorous complexity analysis of its performance. We illustrate on synthetic problems that for training data of certain properties, our sampling can lead to several orders of magnitude improvement in training time. We then test the new sampling on several popular datasets, and show that the improvement can reach an order of magnitude. In the fourth chapter we ask whether randomized coordinate descent (RCD) methods should be applied to the ERM problem or rather to its dual. When the number of examples (n) is much larger than the number of features (d), a common strategy is to apply RCD to the dual problem. On the other hand, when the number of features is much larger than the number of examples, it makes sense to apply RCD directly to the primal problem. In this paper we provide the first joint study of these two approaches when applied to L2-regularized ERM. First, we show through a rigorous analysis that for dense data, the above intuition is precisely correct. However, we find that for sparse and structured data, primal RCD can significantly outperform dual RCD even if d ≪ n, and vice versa, dual RCD can be much faster than primal RCD even if n ≫ d. Moreover, we show that, surprisingly, a single sampling strategy minimizes both the (bound on the) number of iterations and the overall expected complexity of RCD. Note that the latter complexity measure also takes into account the average cost of the iterations, which depends on the structure and sparsity of the data, and on the sampling strategy employed. We confirm our theoretical predictions using extensive experiments with both synthetic and real data sets. In the last chapter we introduce two novel generalizations of the theory for gradient descent type methods in the proximal setting. Firstly, we introduce the proportion function, which we further use to analyze all the known block-selection rules for coordinate descent methods under a single framework. This framework includes randomized methods with uniform, non-uniform or even adaptive sampling strategies, as well as deterministic methods with batch, greedy or cyclic selection rules. We additionally introduce a novel block selection technique called greedy minibatches, for which we provide competitive convergence guarantees. Secondly, the whole theory of strongly-convex optimization was recently generalized to a specific class of non-convex functions satisfying the so-called Polyak- Lojasiewicz condition. To mirror this generalization in the weakly convex case, we introduce the Weak Polyak- Lojasiewicz condition, using which we give global convergence guarantees for a class of non-convex functions previously not considered in theory. Additionally, we give local convergence guarantees for an even larger class of non-convex functions satisfying only a certain smoothness assumption. By combining the two above mentioned generalizations we recover the state-of-the-art convergence guarantees for a large class of previously known methods and setups as special cases of our framework. Also, we provide new guarantees for many previously not considered combinations of methods and setups, as well as a huge class of novel non-convex objectives. The flexibility of our approach offers a lot of potential for future research, as any new block selection procedure will have a convergence guarantee for all objectives considered in our framework, while any new objective analyzed under our approach will have a whole fleet of block selection rules with convergence guarantees readily available.

Nous avons étudiés des fils quantiques dopés de semi-conducteurs gravés par spectroscopie de diffusion Raman. Nous avons observés les excitations du gaz d'électrons. Celles-ci présentent des règles de sélection différentes de celles établies pour les systèmes bi-dimensionnels. Nous avons montré théoriquement qu'elles proviennent de la modification de la structure du champ électromagnétique local provoquée par la géométrie particulière des fils gravés. Pour cela nous avons dû calculer le champ local et l'introduire dans la section efficace de diffusion Raman pour en déduire les règles de sélection de toutes les excitations. Cela a permis de déterminer sans équivoque la nature des excitations qui sont des plasmons. Aucune excitations à une particule ni fluctuations de densité de spin n'a été observées. Nous avons étudié l'évolution continue des dispersions de ces plasmons lorsque la largeur du fil est réduite de 1 micromètre à 30 nm. Jusqu'à 60 nm, celles-ci sont en très bon accord avec les résultats d'un modèle hydrodynamique. Au dessous de 60 nm, la comparaison avec un modèle RPA s'impose. Le plasmon intra-bande dispersif est observé jusqu'à 45 nm, largeur en dessous de laquelle les spectres Raman sont dominés par des excitations localisées qui nécessitent une analyse ultérieure pour en déterminer clairement leur nature. Nous montrons à l'aide du modèle RPA que nous avons atteint la limite quantique pour un fil de largeur 55 nm. Une gamme étroite de fils dont les largeurs sont comprises entre 55 nm à 45 nm permet donc l'étude de gaz strictement unidimensionnel.<br />Nous avons cherché à déterminer la contribution de la forte illumination dans les conclusions précédentes. Nous avons utilisé pour cela la spectroscopie de magnéto-transmission infra-rouge qui ne modifie pas les conditions d'équilibre du gaz d'électrons. Une largeur critique de 130 nm a été extraite, en dessous de laquelle nous n'avons plus aucun signe de la présence d'électrons libres. La comparaison des mesures Raman et infra-rouge a permis l'établissement et la validation d'un modèle microscopique du potentiel de confinement présent dans les fils. Enfin nous avons fabriqués des échantillons de géométries plus complexes. L'observation et l'analyse par diffusion Raman des plasmons dans ces fils a montré que nous pouvions contrôler la géométrie du potentiel confinant les électrons et a mis en évidence des effets nouveaux tels que le repliement et le confinement de plasmons unidimensionnels.

This thesis is devoted to the optical properties of low-dimensional structures based on such two-dimensional materials as graphene, silicene and phosphorene. We investigate optical properties of a variety of quasi-one dimensional and quasi-zero-dimensional structures, which are promising for future optoelectronics. Primarily we focus on their low-energy optical properties and how these properties are influenced by the structures’ geometry, external fields, intrinsic strain and edge disorder. As a consequence of this endeavor, we find several interesting effects such as correlation between the optical properties of tubes and ribbons whose periodic and ‘hard wall’ boundary conditions are matched and a universal value of matrix element in narrow-gap tubes and ribbons characterizing probability of transitions across the band gap opened up by intrinsic strain originating from the tube’s surface curvature or ribbon’s edge relaxation. The analytical study of the gapped 2D Dirac materials such as silicene and germanene, which have some similarity to the aforementioned quasi-one-dimensional systems in terms of physical description, reveals a valley- and polarization-dependent selection rules. It was also found that absorption coefficient should change in gapped materials with increasing frequency and become a half of its value for gap edge transitions when the spectrum is linear. Our analysis of the electronic properties of flat clusters of silicene and phosphorene relates the emergence and the number of the peculiar edge states localized at zero energy, so-called zero-energy states, which are know to be of topological origin, to the cluster’s structural characteristics such as shape and size. This allows to predict the presence and the number of such states avoiding complicated topological arguments and provides a recipes for design of metallic and dielectric clusters. We show that zero-energy states are optically active and can be efficiently manipulated by external electric field. However, the edge disorder is important to take into account. We present a new fractal-based methodology to study the effects of the edge disorder which can be applied also to modeling of composite materials. These finding should be useful in design of optoelectronic devices such as tunable emitters and detectors in a wide region of electromagnetic spectrum ranging form the mid-infrared and THz to the optical frequencies.

We study Cheeger-Simons differential characters in order to define higher form U(1) gauge fields and their Wilson lines. We then go on to define generalized global symmetries. This is a topological formulation of symmetries which has interesting consequences when the charged operators extend through space. Our main source of such charged operators are the generalized Wilson lines. A higher form Noether theorem and a Ward identity are given for transformations of Wilson lines. As examples of quantum field theories with generalized symmetries we cover Sigma models, Maxwell theory and BF-theory. These are examples of Z, U(1) and Zn symmetries respectively. Finally we discuss spontaneous symmetry breaking for higher dimensional symmetries and a Goldstone theorem is provided. These massless Goldstone bosons are shown to have internal structure corresponding to non-zero spin. The photon is identified as the spin one Goldstone boson in QED. Our review of generalized symmetries is more formal than the ones in other papers. This makes various points explicit and leads to general selection rules. Many results of previous papers are reproduced in detail.

No description available.

La Spectroscopie par Effet Tunnel Inélastique (IETS) avec un Microscope à Effet Tunnel (STM) est une nouvelle technique de spectroscopie vibrationnelle, qui permet de caractériser des propriétés très fines de molécules adsorbées sur des surfaces métalliques. Des règles de selection d’excitation vibrationnelle basées sur la symétrie ont été proposées, cependant, elles ne semblent pas exhaustives pour expliquer la totalité du mécanisme et des facteurs en jeu; elles ne sont pas directement transposables pour les propriétés d'un adsorbat et sont lourdes d'utilisation. Le but de cette thèse est donc d'améliorer ces règles de selection par une étude théorique. Un protocole de simulation de l'IETS a été développé, paramétré, et évalué, puis appliqué pour calculer des spectres IETS pour différentes petites molécules, qui sont systématiquement liées, sur une surface de cuivre. Des principes additifs de l'IETS ont été developpés, notamment concernant l’extension dans le vide de l’état de tunnel, l'activation/ quench sélectif de certains modes du aux propriétés électroniques de certains fragments moléculaires, et l'application de certaines règles d'addition de signaux IETS. De plus, des empreintes vibrationnelles par des signaux IETS ont été determinées pour permettre de différentier entre les orientations des adsorbats, la nature chimique des atomes et les isomères de structures. Une stratégie simple utilisant les propriétés de distribution de la densité électronique de la molécule isolée pour prédire les activités IETS sans des couts importants de calculs a aussi été développée. Cette expertise a été utilisée pour rationaliser et interpréter les mesures expérimentales des spectres IETS pour des métalloporphyrines et métallophtalocyanines adsorbées. Ces études sont les premières études IETS pour des molécules aussi larges et complexes. L'approche expérimentale a permis de déterminer les limitations actuelles des simulations IETS. Les défauts associés à l'identification ont été résolus en faisant des simulations d'images STM complémentaires. / Inelastic Electron Tunneling Spectroscopy (IETS) with the Scanning Tunneling Microscope (STM) is a novel vibrational spectroscopy technique that permits to characterize very subtle properties of molecules adsorbed on metallic surfaces. Its proposed symmetry-based propensity selection rules, however, fail to fully capture its exact mechanism and influencing factors; are not directly retraceable to an adsorbate property and are cumbersome. In this thesis, a theoretical approach was taken to improve them. An IETS simulation protocol has been developed, parameterized and benchmarked, and consequently used to calculate IETS spectra for a set of systematically related small molecules on copper surfaces. Extending IETS principles were deduced that refer to the tunneling state’s vacuum extension, the selective activating/quenching of certain types of modes due to the moieties’ electronic properties, and the applicability of a sum rule of IETS signals. Also, fingerprinting IETS-signals that enable discrimination between adsorbate orientations, the chemical nature of atoms and structural isomers were determined and a strategy using straightforward electronic density distribution properties of the isolated molecule to predict IETS activity without (large) computational cost was developed. This expertise was used to rationalize and interpret experimentally measured IETS spectra for adsorbed metalloporphyrins and metallophthalocyanines, being the first IETS studies of this large size. This experimental approach permitted to determine the current limitations of IETS-simulations. The associated identification shortcomings were resolved by conducting complementary STM-image simulations.