In this thesis we investigate the convergence of Euler's and Yosida approximations of operator semigroups. We obtain asymptotic expansions for Euler's approximations of semigroups with optimal bounds for the remainder terms. We provide various explicit formulas for the coefficients for these expansions. For Yosida approximations of semigroups we obtain two optimal error bounds with optimal constants. We also construct asymptotic expansions for Yosida approximations of semigroups and provide optimal bounds for the remainder terms of these expansions. / Disertacijoje tiriamas operatorių pusgrupių Eulerio ir Josidos approximacijų konvergavimas. Gauti Eulerio aproksimacijų asimptotiniai skleidiniai ir optimalūs liekamųjų narių įverčiai. Taip pat pateiktos įvairios šių skleidinių koeficientų analizinės išraiškos. Josidos aproksimacijoms buvo rasti du optimalūs konvergavimo greičio įverčiai su optimaliomis konstantomis. Taip pat gauti Josidos aproksimacijų asimptotiniai skleidiniai ir liekamųjų narių įverčiai.

Submitted by Jaqueline Silva (jtas29@gmail.com) on 2016-09-12T20:46:48Z No. of bitstreams: 2 Dissertação - Abssan Matuzinhos de Moura - 2016.pdf: 1317960 bytes, checksum: d406a9bf2b4d0bbca0ad6e3b52da498d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2016-09-12T20:47:11Z (GMT) No. of bitstreams: 2 Dissertação - Abssan Matuzinhos de Moura - 2016.pdf: 1317960 bytes, checksum: d406a9bf2b4d0bbca0ad6e3b52da498d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-09-12T20:47:11Z (GMT). No. of bitstreams: 2 Dissertação - Abssan Matuzinhos de Moura - 2016.pdf: 1317960 bytes, checksum: d406a9bf2b4d0bbca0ad6e3b52da498d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-04-29 / The gradient method is a classical optimization methods to minimize a function. This method deserves special mention for its simplicity and easy understanding. This work is based on the study of the gradient method with step size given by the variant Barzilai- Borwein. Our goal is to present the convergence of the method with this variant. First we will study the two-dimensional case, for strictly convex quadratic functions. In this case, besides obtaining the convergence of the method, we see that such convergence occurs with R-superlinear rate. In the final part of the work, we will study the method with the variant Barzilai-Borwein not necessarily quadratic functions, concluding that the method converges. / O Método Gradiente é um dos métodos clássicos de otimização para minimizar uma função. Esse método merece um destaque especial pela sua simplicidade e fácil compreensão. Este trabalho se baseia no estudo do Método Gradiente com tamanho do passo dado pela variante de Barzilai-Borwein. Nosso objetivo é apresentar a convergência do método com esta variante. Primeiro faremos o estudo no caso bidimensional, para funções quadráticas estritamente convexas. Neste caso, além de obtermos a convergência do método, veremos que tal convergência ocorre com taxa R-superlinear. Na parte final do trabalho, faremos o estudo do método com a variante de Barzilai-Borwein para funções não necessariamente quadráticas, concluindo que o método converge.

L’opérateur du p-Laplacien non local, l’équation d’évolution et la régularisation variationnelle associées régies par un noyau donné ont des applications dans divers domaines de la science et de l’ingénierie. En particulier, ils sont devenus des outils modernes pour le traitement massif des données (y compris les signaux, les images, la géométrie) et dans les tâches d’apprentissage automatique telles que la classification. En pratique, cependant, ces modèles sont implémentés sous forme discrète (en espace et en temps, ou en espace pour la régularisation variationnelle) comme approximation numérique d’un problème continu, où le noyau est remplacé par la matrice d’adjacence d’un graphe. Pourtant, peu de résultats sur la consistence de ces discrétisations sont disponibles. En particulier, il est largement ouvert de déterminer quand les solutions de l’équation d’évolution ou du problème variationnel des tâches basées sur des graphes convergent (dans un sens approprié) à mesure que le nombre de sommets augmente, vers un objet bien défini dans le domaine continu, et si oui, à quelle vitesse. Dans ce manuscrit, nous posons les bases pour aborder ces questions.En combinant des outils de la théorie des graphes, de l’analyse convexe, de la théorie des semi- groupes non linéaires et des équations d’évolution, nous interprétons rigoureusement la limite continue du problème d’évolution et du problème variationnel du p-Laplacien discrets sur graphes. Plus précisé- ment, nous considérons une suite de graphes (déterministes) convergeant vers un objet connu sous le nom de graphon. Si les problèmes d’évolution et variationnel associés au p-Laplacien continu non local sont discrétisés de manière appropriée sur cette suite de graphes, nous montrons que la suite des solutions des problèmes discrets converge vers la solution du problème continu régi par le graphon, lorsque le nombre de sommets tend vers l’infini. Ce faisant, nous fournissons des bornes d’erreur/consistance.Cela permet à son tour d’établir les taux de convergence pour différents modèles de graphes. En parti- culier, nous mettons en exergue le rôle de la géométrie/régularité des graphons. Pour les séquences de graphes aléatoires, en utilisant des inégalités de déviation (concentration), nous fournissons des taux de convergence nonasymptotiques en probabilité et présentons les différents régimes en fonction de p, de la régularité du graphon et des données initiales. / The non-local p-Laplacian operator, the associated evolution equation and variational regularization, governed by a given kernel, have applications in various areas of science and engineering. In particular, they are modern tools for massive data processing (including signals, images, geometry), and machine learning tasks such as classification. In practice, however, these models are implemented in discrete form (in space and time, or in space for variational regularization) as a numerical approximation to a continuous problem, where the kernel is replaced by an adjacency matrix of a graph. Yet, few results on the consistency of these discretization are available. In particular it is largely open to determine when do the solutions of either the evolution equation or the variational problem of graph-based tasks converge (in an appropriate sense), as the number of vertices increases, to a well-defined object in the continuum setting, and if yes, at which rate. In this manuscript, we lay the foundations to address these questions.Combining tools from graph theory, convex analysis, nonlinear semigroup theory and evolution equa- tions, we give a rigorous interpretation to the continuous limit of the discrete nonlocal p-Laplacian evolution and variational problems on graphs. More specifically, we consider a sequence of (determin- istic) graphs converging to a so-called limit object known as the graphon. If the continuous p-Laplacian evolution and variational problems are properly discretized on this graph sequence, we prove that the solutions of the sequence of discrete problems converge to the solution of the continuous problem governed by the graphon, as the number of graph vertices grows to infinity. Along the way, we provide a consistency/error bounds. In turn, this allows to establish the convergence rates for different graph models. In particular, we highlight the role of the graphon geometry/regularity. For random graph se- quences, using sharp deviation inequalities, we deliver nonasymptotic convergence rates in probability and exhibit the different regimes depending on p, the regularity of the graphon and the initial data.

We investigate the applicability of the method of maximum entropy regularization (MER) including convergence and convergence rates of regularized solutions to the specific inverse problem (SIP) of calibrating a purely time-dependent volatility function. In this context, we extend the results of [16] and [17] in some details. Due to the explicit structure of the forward operator based on a generalized Black-Scholes formula the ill-posedness character of the nonlinear inverse problem (SIP) can be verified. Numerical case studies illustrate the chances and limitations of (MER) versus Tikhonov regularization (TR) for smooth solutions and solutions with a sharp peak.

We propose a new method to perform functional principal component analysis (FPCA) for discretely observed functional data by solving successive optimization problems. The new framework can be applied to both regularly and irregularly observed data, and to both dense and sparse data. Our method does not require estimates of the individual sample functions or the covariance functions. Hence, it can be used to analyze functional data with multidimensional arguments (e.g. random surfaces). Furthermore, it can be applied to many processes and models with complicated or nonsmooth covariance functions. In our method, smoothness of eigenfunctions is controlled by directly imposing roughness penalties on eigenfunctions, which makes it more efficient and flexible to tune the smoothness. Efficient algorithms for solving the successive optimization problems are proposed. We provide the existence and characterization of the solutions to the successive optimization problems. The consistency of our method is also proved. Through simulations, we demonstrate that our method performs well in the cases with smooth samples curves, with discontinuous sample curves and nonsmooth covariance and with sample functions having two dimensional arguments (random surfaces), repectively. We apply our method to classification problems of retinal pigment epithelial cells in eyes of mice and to longitudinal CD4 counts data. In the second part of this dissertation, we propose a sparse Fisher’s discriminant analysis method with thresholded linear constraints. Various regularized linear discriminant analysis (LDA) methods have been proposed to address the problems of the LDA in high-dimensional settings. Asymptotic optimality has been established for some of these methods when there are only two classes. A difficulty in the asymptotic study for the multiclass classification is that for the two-class classification, the classification boundary is a hyperplane and an explicit formula for the classification error exists, however, in the case of multiclass, the boundary is usually complicated and no explicit formula for the error generally exists. Another difficulty in proving the asymptotic consistency and optimality for sparse Fisher’s discriminant analysis is that the covariance matrix is involved in the constraints of the optimization problems for high order components. It is not easy to estimate a general high-dimensional covariance matrix. Thus, we propose a sparse Fisher’s discriminant analysis method which avoids the estimation of the covariance matrix, provide asymptotic consistency results and the corresponding convergence rates for all components. To prove the asymptotic optimality, we provide an asymptotic upper bound for a general linear classification rule in the case of muticlass which is applied to our method to obtain the asymptotic optimality and the corresponding convergence rate. In the special case of two classes, our method achieves the same as or better convergence rates compared to the existing method. The proposed method is applied to multivariate functional data with wavelet transformations.

We prove strong convergence of order 1/4 - E for arbitrarily small E > 0 of the Euler-Maruyama method for multidimensional stochastic differential equations (SDEs) with discontinuous drift and degenerate diffusion coefficient. The proof is based on estimating the difference between the Euler-Maruyama scheme and another numerical method, which is constructed by applying the Euler-Maruyama scheme to a transformation of the SDE we aim to solve.

Stochastic and data-distributed optimization algorithms have received lots of attention from the machine learning community due to the tremendous demand from the large-scale learning and the big-data related optimization. A lot of stochastic and deterministic learning algorithms are proposed recently under various application scenarios. Nevertheless, many of these algorithms are based on heuristics and their optimality in terms of the generalization error is not sufficiently justified. In this talk, I will explain the concept of an optimal learning algorithm, and show that given a time budget and proper hypothesis space, only those achieving the lower bounds of the estimation error and the optimization error are optimal. Guided by this concept, we investigated the stochastic minimization of nonsmooth convex loss functions, a central problem in machine learning. We proposed a novel algorithm named Accelerated Nonsmooth Stochastic Gradient Descent, which exploits the structure of common nonsmooth loss functions to achieve optimal convergence rates for a class of problems including SVMs. It is the first stochastic algorithm that can achieve the optimal O(1/t) rate for minimizing nonsmooth loss functions. The fast rates are confirmed by empirical comparisons with state-of-the-art algorithms including the averaged SGD. The Alternating Direction Method of Multipliers (ADMM) is another flexible method to explore function structures. In the second part we proposed stochastic ADMM that can be applied to a general class of convex and nonsmooth functions, beyond the smooth and separable least squares loss used in lasso. We also demonstrate the rates of convergence for our algorithm under various structural assumptions of the stochastic function: O(1/sqrt{t}) for convex functions and O(log t/t) for strongly convex functions. A novel application named Graph-Guided SVM is proposed to demonstrate the usefulness of our algorithm. We also extend the scalability of stochastic algorithms to nonlinear kernel machines, where the problem is formulated as a constrained dual quadratic optimization. The simplex constraint can be handled by the classic Frank-Wolfe method. The proposed stochastic Frank-Wolfe methods achieve comparable or even better accuracies than state-of-the-art batch and online kernel SVM solvers, and are significantly faster. The last part investigates the problem of data-distributed learning. We formulate it as a consensus-constrained optimization problem and solve it with ADMM. It turns out that the underlying communication topology is a key factor in achieving a balance between a fast learning rate and computation resource consumption. We analyze the linear convergence behavior of consensus ADMM so as to characterize the interplay between the communication topology and the penalty parameters used in ADMM. We observe that given optimal parameters, the complete bipartite and the master-slave graphs exhibit the fastest convergence, followed by bi-regular graphs.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19123号 / 情博第569号 / 新制||情||100(附属図書館) / 32074 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 山下 信雄, 教授 中村 佳正, 教授 田中 利幸 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Les méthodes de Monte Carlo par chaîne de Markov (MCMC) sont des outils très populaires pour l’échantillonnage de lois de probabilité complexes et/ou en grandes dimensions. Étant donné leur facilité d’application, ces méthodes sont largement répandues dans plusieurs communautés scientifiques et bien certainement en statistique, particulièrement en analyse bayésienne. Depuis l’apparition de la première méthode MCMC en 1953, le nombre de ces algorithmes a considérablement augmenté et ce sujet continue d’être une aire de recherche active. Un nouvel algorithme MCMC avec ajustement directionnel a été récemment développé par Bédard et al. (IJSS, 9 :2008) et certaines de ses propriétés restent partiellement méconnues. L’objectif de ce mémoire est de tenter d’établir l’impact d’un paramètre clé de cette méthode sur la performance globale de l’approche. Un second objectif est de comparer cet algorithme à d’autres méthodes MCMC plus versatiles afin de juger de sa performance de façon relative. / Markov Chain Monte Carlo algorithms (MCMC) have become popular tools for sampling from complex and/or high dimensional probability distributions. Given their relative ease of implementation, these methods are frequently used in various scientific areas, particularly in Statistics and Bayesian analysis. The volume of such methods has risen considerably since the first MCMC algorithm described in 1953 and this area of research remains extremely active. A new MCMC algorithm using a directional adjustment has recently been described by Bédard et al. (IJSS, 9:2008) and some of its properties remain unknown. The objective of this thesis is to attempt determining the impact of a key parameter on the global performance of the algorithm. Moreover, another aim is to compare this new method to existing MCMC algorithms in order to evaluate its performance in a relative fashion.

Les méthodes de Monte Carlo par chaîne de Markov (MCMC) sont des outils très populaires pour l’échantillonnage de lois de probabilité complexes et/ou en grandes dimensions. Étant donné leur facilité d’application, ces méthodes sont largement répandues dans plusieurs communautés scientifiques et bien certainement en statistique, particulièrement en analyse bayésienne. Depuis l’apparition de la première méthode MCMC en 1953, le nombre de ces algorithmes a considérablement augmenté et ce sujet continue d’être une aire de recherche active. Un nouvel algorithme MCMC avec ajustement directionnel a été récemment développé par Bédard et al. (IJSS, 9 :2008) et certaines de ses propriétés restent partiellement méconnues. L’objectif de ce mémoire est de tenter d’établir l’impact d’un paramètre clé de cette méthode sur la performance globale de l’approche. Un second objectif est de comparer cet algorithme à d’autres méthodes MCMC plus versatiles afin de juger de sa performance de façon relative. / Markov Chain Monte Carlo algorithms (MCMC) have become popular tools for sampling from complex and/or high dimensional probability distributions. Given their relative ease of implementation, these methods are frequently used in various scientific areas, particularly in Statistics and Bayesian analysis. The volume of such methods has risen considerably since the first MCMC algorithm described in 1953 and this area of research remains extremely active. A new MCMC algorithm using a directional adjustment has recently been described by Bédard et al. (IJSS, 9:2008) and some of its properties remain unknown. The objective of this thesis is to attempt determining the impact of a key parameter on the global performance of the algorithm. Moreover, another aim is to compare this new method to existing MCMC algorithms in order to evaluate its performance in a relative fashion.