In recent years, unprecedented growths in scale and dimensionality of data raise big computational challenges for traditional optimization algorithms; thus it becomes very important to develop efficient and effective optimization algorithms for solving numerous machine learning problems. Many traditional algorithms (e.g., gradient descent method) are black-box algorithms, which are simple to implement but ignore the underlying geometrical property of the objective function. Recent trend in accelerating these traditional black-box algorithms is to leverage geometrical properties of the objective function such as strong convexity. However, most existing methods rely too much on the knowledge of strong convexity, which makes them not applicable to problems without strong convexity or without knowledge of strong convexity. To bridge the gap between traditional black-box algorithms without knowing the problem's geometrical property and accelerated algorithms under strong convexity, how can we develop adaptive algorithms that can be adaptive to the objective function's underlying geometrical property? To answer this question, in this dissertation we focus on convex optimization problems and propose to explore an error bound condition that characterizes the functional growth condition of the objective function around a global minimum. Under this error bound condition, we develop algorithms that (1) can adapt to the problem's geometrical property to enjoy faster convergence in stochastic optimization; (2) can leverage the problem's structural regularizer to further improve the convergence speed; (3) can address both deterministic and stochastic optimization problems with explicit max-structural loss; (4) can leverage the objective function's smoothness property to improve the convergence rate for stochastic optimization. We first considered stochastic optimization problems with general stochastic loss. We proposed two accelerated stochastic subgradient (ASSG) methods with theoretical guarantees by iteratively solving the original problem approximately in a local region around a historical solution with the size of the local region gradually decreasing as the solution approaches the optimal set. Second, we developed a new theory of alternating direction method of multipliers (ADMM) with a new adaptive scheme of the penalty parameter for both deterministic and stochastic optimization problems with structured regularizers. With LEB condition, the proposed deterministic and stochastic ADMM enjoy improved iteration complexities of $\widetilde O(1/\epsilon^{1-\theta})$ and $\widetilde O(1/\epsilon^{2(1-\theta)})$ respectively. Then, we considered a family of optimization problems with an explicit max-structural loss. We developed a novel homotopy smoothing (HOPS) algorithm that employs Nesterov's smoothing technique and accelerated gradient method and runs in stages. Under a generic condition so-called local error bound (LEB) condition, it can improve the iteration complexity of $O(1/\epsilon)$ to $\widetilde O(1/\epsilon^{1-\theta})$ omitting a logarithmic factor with $\theta\in(0,1]$. Next, we proposed new restarted stochastic primal-dual (RSPD) algorithms for solving the problem with stochastic explicit max-structural loss. We successfully got a better iteration complexity than $O(1/\epsilon^2)$ without bilinear structure assumption, which is a big challenge of obtaining faster convergence for the considered problem. Finally, we consider finite-sum optimization problems with smooth loss and simple regularizer. We proposed novel techniques to automatically search for the unknown parameter on the fly of optimization while maintaining almost the same convergence rate as an oracle setting assuming the involved parameter is given. Under the Holderian error bound (HEB) condition with $\theta\in(0,1/2)$, the proposed algorithm also enjoys intermediate faster convergence rates than its standard counterparts with only the smoothness assumption.

The boundary concentrated finite element method is a variant of the hp-version of the FEM that is particularly suited for the numerical treatment of elliptic boundary value problems with smooth coefficients and boundary conditions with low regularity or non-smooth geometries. In this paper we consider the case of the discretization of a Dirichlet problem with exact solution $u \in H^{1+\delta}(\Omega)$ and investigate the local error in various norms. We show that for a $\beta > 0$ these norms behave as $O(N^{−\delta−\beta})$, where $N$ denotes the dimension of the underlying finite element space. Furthermore, we present a new Gauss-Lobatto based interpolation operator that is adapted to the case non-uniform polynomial degree distributions.

The purpose of this study is to determine two types of error gravity in a corpus of texts written by native Chinese learners of English (ELLs)—one that enriches the traditional construct of gravity found in error gravity research by including error frequency, or how often an error occurs in a text relative to others, as an intervening variable, and one that applies the new error gravity data in a practical way to help establish salient grammatical focal points for written corrective feedback (WCF). Previous error gravity research has suggested that the amount of irritation caused by error is determined by the extent to which an utterance departs from "native-like" speech. However, because these studies often neglect the role of frequency in determining gravity—relying on isolated sentences, pre-determined errors, and manipulated texts to define it—a more complete view of error gravity is needed. Forty-eight native English speakers without ESL teaching experience and 10 experienced ESL teachers evaluated a set of 18 timed, 30-minute essays written by high intermediate to advanced native-Chinese ELLs. Errors were identified, verified, tagged, and classified by the level of irritation they produced. Results show the most serious errors included count/non-count (C/NC), insert verb (INSERT V), omit verb (OMIT V), and subject-verb agreement (SV). The most frequent error type was word choice (WC), followed by singular/plural (S/PL), awkward (AWK), and word form (WF). When combined, singular/plural (S/PL), word form (WF), word choice (WC), and awkward (AWK) errors were found to be the most critical. These findings support Burt and Kiparsky's (1972) global/local error distinction in which global errors, or those lexical, grammatical and syntactic errors that affect the overall organization or meaning of the sentence (Burt, 1975) are deemed more grievous than local ones, which affect only "single elements (constituents)" (Burt, 1975, p. 57). Implications are discussed in terms of future research and possible uses in the Dynamic Written Corrective Feedback classroom.

The boundary concentrated finite element method is a variant of the hp-version of the FEM that is particularly suited for the numerical treatment of elliptic boundary value problems with smooth coefficients and boundary conditions with low regularity or non-smooth geometries. In this paper we consider the case of the discretization of a Dirichlet problem with exact solution $u \in H^{1+\delta}(\Omega)$ and investigate the local error in various norms. We show that for a $\beta > 0$ these norms behave as $O(N^{−\delta−\beta})$, where $N$ denotes the dimension of the underlying finite element space. Furthermore, we present a new Gauss-Lobatto based interpolation operator that is adapted to the case non-uniform polynomial degree distributions.

Une grande part des muqueuses à l’intérieur du corps humain sont recouvertes de cils qui, par leurs mouvements coordonnés, conduisent à une circulation de la couche de fluide nappant la muqueuse. Dans le cas de la paroi interne des bronches, ce processus permet l’évacuation des impuretés inspirées à l’extérieur de l’appareil respiratoire.Dans cette thèse, nous nous intéressons aux effets du ou des cils sur le fluide, en nous plaçant à l’échelle du cil, et on considère pour cela les équations de Stokes incompressible. Due à la finesse du cil, une simulation directe demanderait un raffinement important du maillage au voisinage du cil, pour un maillage qui évoluerait à chaque pas de temps. Cette approche étant trop onéreuse en terme de coûts de calculs, nous avons considéré l’asymptotique d’un diamètre du cil tendant vers 0 et d’une vitesse qui tend vers l’infini : le cil est modélisé par un Dirac linéique de forces en terme source. Nous avons montré qu’il était possible de remplacer ce Dirac linéique par une somme de Dirac ponctuels distribués le long du cil. Ainsi, nous nous sommes ramenés, par linéarité, à étudier le problème de Stokes avec en terme source une force ponctuelle. Si les calculs sont ainsi simplifiés (et leurs coûts réduits), le problème final est lui plus singulier, ce qui motive une analyse numérique fine et l’élaboration d’une nouvelle méthode de résolution.Nous avons d’abord étudié une version scalaire de ce problème : le problème de Poisson avec une masse de Dirac en second membre. La solution exacte étant singulière, la solution éléments finis est à définir avec précaution. La convergence de la méthode étant dégradée dans ce cas-là, par rapport à celle dans le cas régulier, nous nous sommes intéressés à des estimations locales. Nous avons démontré une convergence quasi-optimale en norme Hs (s ě 1) sur un sous-domaine qui exclut la singularité. Des résultats analogues ont été obtenus dans le cas du problème de Stokes.Pour palier les problèmes liés à une mauvais convergence sur l’ensemble du domaine, nous avons élaboré une méthode pour résoudre des problème elliptiques avec une masse de Dirac ou une force ponctuelle en terme source. Basée sur celle des éléments finis standard, elle s’appuie sur la connaissance explicite de la singularité de la solution exacte. Une fois données la position de chacun des cils et leur paramétrisation, notre méthode rend possible la simulation directe en 3d d’un très grand nombre de cils. Nous l’avons donc appliquée au cas du transport mucociliaire dans les poumons. Cet outil numérique nous donne accès à des informations que l’on ne peut avoir par l’expérience, et permet de simuler des cas pathologiques comme par exemple une distribution éparse des cils. / Numerous mucous membranes inside the human body are covered with cilia which, by their coordinated movements, lead to a circulation of the layer of fluid coating the mucous membrane, which allows, for example, in the case of the internal wall of the bronchi, the evacuation of the impurities inspired outside the respiratory system.In this thesis, we integrate the effects of the cilia on the fluid, at the scale of the cilium. For this, we consider the incompressible Stokes equations. Due to the very small thickness of the cilia, the direct computation would request a time-varying mesh grading around the cilia. To avoid too prohibitive computational costs, we consider the asymptotic of a zero diameter cilium with an infinite velocity: the cilium is modelled by a lineic Dirac of force in source term. In order to ease the computations, the lineic Dirac of forces can be approached by a sum of punctual Dirac masses distributed along the cilium. Thus, by linearity, we have switched our initial problem with the Stokes problem with a punctual force in source term. Thus, we simplify the computations, but the final problem is more singular than the initial problem. The loss of regularity involves a deeper numerical analysis and the development of a new method to solve the problem.We have first studied a scalar version of this problem: Poisson problem with a Dirac right-hand side. The exact solution is singular, therefore the finite element solution has to be defined with caution. In this case, the convergence is not as good as in the regular case, and thus we focused on local error estimates. We have proved a quasi-optimal convergence in H1-norm (s ď 1) on a sub-domain which does not contain the singularity. Similar results have been shown for the Stokes problem too.In order to recover an optimal convergence on the whole domain, we have developped a numerical method to solve elliptic problems with a Dirac mass or a punctual force in source term. It is based on the standard finite element method and the explicit knowl- edge of the singularity of the exact solution. Given the positions of the cilia and their parametrisations, this method permits to compute in 3d a very high number of cilia. We have applied this to the study of the mucociliary transport in the lung. This numerical tool gives us information we do not have with the experimentations and pathologies can be computed and studied by this way, like for example a small number of cilia.

Dans cette thèse, nous nous étudions des algorithmes d’optimisation non linéaire. D’une part nous proposons des techniques de détection rapide de la non-réalisabilité d’un problème à résoudre. D’autre part, nous analysons le comportement local des algorithmes pour la résolution de problèmes singuliers. Dans la première partie, nous présentons une modification d’un algorithme de lagrangien augmenté pour l’optimisation avec contraintes d’égalité. La convergence quadratique du nouvel algorithme dans le cas non-réalisable est démontrée théoriquement et numériquement. La seconde partie est dédiée à l’extension du résultat précédent aux problèmes d’optimisation non linéaire généraux avec contraintes d’égalité et d’inégalité. Nous proposons une modification d’un algorithme de pénalisation mixte basé sur un lagrangien augmenté et une barrière logarithmique. Les résultats théoriques de l’analyse de convergence et quelques tests numériques montrent l’avantage du nouvel algorithme dans la détection de la non-réalisabilité. La troisième partie est consacrée à étudier le comportement local d’un algorithme primal-dual de points intérieurs pour l’optimisation sous contraintes de borne. L’analyse locale est effectuée sans l’hypothèse classique des conditions suffisantes d’optimalité de second ordre. Celle-ci est remplacée par une hypothèse plus faible basée sur la notion de borne d’erreur locale. Nous proposons une technique de régularisation de la jacobienne du système d’optimalité à résoudre. Nous démontrons ensuite des propriétés de bornitude de l’inverse de ces matrices régularisées, ce qui nous permet de montrer la convergence superlinéaire de l’algorithme. La dernière partie est consacrée à l’analyse de convergence locale de l’algorithme primal-dual qui est utilisé dans les deux premières parties de la thèse. En pratique, il a été observé que cet algorithme converge rapidement même dans le cas où les contraintes ne vérifient l’hypothèse de qualification de Mangasarian-Fromovitz. Nous démontrons la convergence superlinéaire et quadratique de cet algorithme, sans hypothèse de qualification des contraintes. / This thesis is devoted to the study of numerical algorithms for nonlinear optimization. On the one hand, we propose new strategies for the rapid infeasibility detection. On the other hand, we analyze the local behavior of primal-dual algorithms for the solution of singular problems. In the first part, we present a modification of an augmented Lagrangian algorithm for equality constrained optimization. The quadratic convergence of the new algorithm in the infeasible case is theoretically and numerically demonstrated. The second part is dedicated to extending the previous result to the solution of general nonlinear optimization problems with equality and inequality constraints. We propose a modification of a mixed logarithmic barrier-augmented Lagrangian algorithm. The theoretical convergence results and the numerical experiments show the advantage of the new algorithm for the infeasibility detection. In the third part, we study the local behavior of a primal-dual interior point algorithm for bound constrained optimization. The local analysis is done without the standard assumption of the second-order sufficient optimality conditions. These conditions are replaced by a weaker assumption based on a local error bound condition. We propose a regularization technique of the Jacobian matrix of the optimality system. We then demonstrate some boundedness properties of the inverse of these regularized matrices, which allow us to prove the superlinear convergence of our algorithm. The last part is devoted to the local convergence analysis of the primal-dual algorithm used in the first two parts of this thesis. In practice, it has been observed that this algorithm converges rapidly even in the case where the constraints do not satisfy the Mangasarian-Fromovitz constraint qualification. We demonstrate the superlinear and quadratic convergence of this algorithm without any assumption of constraint qualification.