<p>In this work, we study a class of Markovian information theoretic optimization problems motivated by the recent interests in incorporating mutual information as performance metrics which gives evident success in representation learning, feature extraction and clustering problems. In particular, we focus on the information bottleneck (IB) and privacy funnel (PF) methods and their recent multi-view, multi-source generalizations that gain attention because the performance significantly improved with multi-view, multi-source data. Nonetheless, the generalized problems challenge existing IB and PF solves in terms of the complexity and their abilities to tackle large-scale data. </p> <p>To address this, we study both the IB and PF under a unified framework and propose solving it through splitting methods, including renowned algorithms such as alternating directional method of multiplier (ADMM), Peaceman-Rachford splitting (PRS) and Douglas-Rachford splitting (DRS) as special cases. Our convergence analysis and the locally linear rate of convergence results give rise to new splitting method based IB and PF solvers that can be easily generalized to multi-view IB, multi-source PF. We implement the proposed methods with gradient descent and empirically evaluate the new solvers in both synthetic and real-world datasets. Our numerical results demonstrate improved performance over the state-of-the-art approach with significant reduction in complexity. Furthermore, we consider the practical scenario where there is distribution mismatch between training and testing data generating processes under a known bounded divergence constraint. In analyzing the generalization error, we develop new techniques inspired by the input-output mutual information approach and tighten the existing generalization error bounds.</p>

Cette thèse aborde le sujet de la régression linéaire dans différents cadres, liés notamment à l’apprentissage. Les deux premiers chapitres présentent le contexte des travaux, leurs apports et les outils mathématiques utilisés. Le troisième chapitre est consacré à la construction d’une fonction de régularisation optimale, permettant par exemple d’améliorer sur le plan théorique la régularisation de l’estimateur LASSO. Le quatrième chapitre présente, dans le domaine de l’optimisation convexe séquentielle, des accélérations d’un algorithme récent et prometteur, MetaGrad, et une conversion d’un cadre dit “séquentiel déterministe" vers un cadre dit “batch stochastique" pour cet algorithme. Le cinquième chapitre s’intéresse à des prévisions successives par intervalles, fondées sur l’agrégation de prédicteurs, sans retour d’expérience intermédiaire ni modélisation stochastique. Enfin, le sixième chapitre applique à un jeu de données pétrolières plusieurs méthodes d’agrégation, aboutissant à des prévisions ponctuelles court-terme et des intervalles de prévision long-terme. / This thesis tackles the topic of linear regression, within several frameworks, mainly linked to statistical learning. The first and second chapters present the context, the results and the mathematical tools of the manuscript. In the third chapter, we provide a way of building an optimal regularization function, improving for instance, in a theoretical way, the LASSO estimator. The fourth chapter presents, in the field of online convex optimization, speed-ups for a recent and promising algorithm, MetaGrad, and shows how to transfer its guarantees from a so-called “online deterministic setting" to a “stochastic batch setting". In the fifth chapter, we introduce a new method to forecast successive intervals by aggregating predictors, without intermediate feedback nor stochastic modeling. The sixth chapter applies several aggregation methods to an oil production dataset, forecasting short-term precise values and long-term intervals.

De nombreux problèmes en Apprentissage Statistique consistent à minimiser une fonction non convexe et non lisse définie sur un espace euclidien. Par exemple, les problèmes de maximisation de la vraisemblance et la minimisation du risque empirique en font partie.Les algorithmes d'optimisation utilisés pour résoudre ce genre de problèmes ont été largement étudié pour des fonctions convexes et grandement utilisés en pratique.Cependant, l'accrudescence du nombre d'observation dans l'évaluation de ce risque empirique ajoutée à l'utilisation de fonctions de perte de plus en plus sophistiquées représentent des obstacles.Ces obstacles requièrent d'améliorer les algorithmes existants avec des mis à jour moins coûteuses, idéalement indépendantes du nombre d'observations, et d'en garantir le comportement théorique sous des hypothèses moins restrictives, telles que la non convexité de la fonction à optimiser.Dans ce manuscrit de thèse, nous nous intéressons à la minimisation de fonctions objectives pour des modèles à données latentes, ie, lorsque les données sont partiellement observées ce qui inclut le sens conventionnel des données manquantes mais est un terme plus général que cela.Dans une première partie, nous considérons la minimisation d'une fonction (possiblement) non convexe et non lisse en utilisant des mises à jour incrémentales et en ligne. Nous proposons et analysons plusieurs algorithmes à travers quelques applications.Dans une seconde partie, nous nous concentrons sur le problème de maximisation de vraisemblance non convexe en ayant recourt à l'algorithme EM et ses variantes stochastiques. Nous en analysons plusieurs versions rapides et moins coûteuses et nous proposons deux nouveaux algorithmes du type EM dans le but d'accélérer la convergence des paramètres estimés. / Many problems in machine learning pertain to tackling the minimization of a possibly non-convex and non-smooth function defined on a Many problems in machine learning pertain to tackling the minimization of a possibly non-convex and non-smooth function defined on a Euclidean space.Examples include topic models, neural networks or sparse logistic regression.Optimization methods, used to solve those problems, have been widely studied in the literature for convex objective functions and are extensively used in practice.However, recent breakthroughs in statistical modeling, such as deep learning, coupled with an explosion of data samples, require improvements of non-convex optimization procedure for large datasets.This thesis is an attempt to address those two challenges by developing algorithms with cheaper updates, ideally independent of the number of samples, and improving the theoretical understanding of non-convex optimization that remains rather limited.In this manuscript, we are interested in the minimization of such objective functions for latent data models, ie, when the data is partially observed which includes the conventional sense of missing data but is much broader than that.In the first part, we consider the minimization of a (possibly) non-convex and non-smooth objective function using incremental and online updates.To that end, we propose several algorithms exploiting the latent structure to efficiently optimize the objective and illustrate our findings with numerous applications.In the second part, we focus on the maximization of non-convex likelihood using the EM algorithm and its stochastic variants.We analyze several faster and cheaper algorithms and propose two new variants aiming at speeding the convergence of the estimated parameters.

Le traitement massif et automatique des données requiert le développement de techniques de filtration des informations les plus importantes. Parmi ces méthodes, celles présentant des structures parcimonieuses se sont révélées idoines pour améliorer l’efficacité statistique et computationnelle des estimateurs, dans un contexte de grandes dimensions. Elles s’expriment souvent comme solution de la minimisation du risque empirique régularisé s’écrivant comme une somme d’un terme lisse qui mesure la qualité de l’ajustement aux données, et d’un terme non lisse qui pénalise les solutions complexes. Cependant, une telle manière d’inclure des informations a priori, introduit de nombreuses difficultés numériques pour résoudre le problème d’optimisation sous-jacent et pour calibrer le niveau de régularisation. Ces problématiques ont été au coeur des questions que nous avons abordées dans cette thèse.Une technique récente, appelée «Screening Rules», propose d’ignorer certaines variables pendant le processus d’optimisation en tirant bénéfice de la parcimonie attendue des solutions. Ces règles d’élimination sont dites sûres lorsqu’elles garantissent de ne pas rejeter les variables à tort. Nous proposons un cadre unifié pour identifier les structures importantes dans ces problèmes d’optimisation convexes et nous introduisons les règles «Gap Safe Screening Rules». Elles permettent d’obtenir des gains considérables en temps de calcul grâce à la réduction de la dimension induite par cette méthode. De plus, elles s’incorporent facilement aux algorithmes itératifs et s’appliquent à un plus grand nombre de problèmes que les méthodes précédentes.Pour trouver un bon compromis entre minimisation du risque et introduction d’un biais d’apprentissage, les algorithmes d’homotopie offrent la possibilité de tracer la courbe des solutions en fonction du paramètre de régularisation. Toutefois, ils présentent des instabilités numériques dues à plusieurs inversions de matrice, et sont souvent coûteux en grande dimension. Aussi, ils ont des complexités exponentielles en la dimension du modèle dans des cas défavorables. En autorisant des solutions approchées, une approximation de la courbe des solutions permet de contourner les inconvénients susmentionnés. Nous revisitons les techniques d’approximation des chemins de régularisation pour une tolérance prédéfinie, et nous analysons leur complexité en fonction de la régularité des fonctions de perte en jeu. Il s’ensuit une proposition d’algorithmes optimaux ainsi que diverses stratégies d’exploration de l’espace des paramètres. Ceci permet de proposer une méthode de calibration de la régularisation avec une garantie de convergence globale pour la minimisation du risque empirique sur les données de validation.Le Lasso, un des estimateurs parcimonieux les plus célèbres et les plus étudiés, repose sur une théorie statistique qui suggère de choisir la régularisation en fonction de la variance des observations. Ceci est difficilement utilisable en pratique car, la variance du modèle est une quantité souvent inconnue. Dans de tels cas, il est possible d’optimiser conjointement les coefficients de régression et le niveau de bruit. Ces estimations concomitantes, apparues dans la littérature sous les noms de Scaled Lasso, Square-Root Lasso, fournissent des résultats théoriques aussi satisfaisants que celui du Lasso tout en étant indépendant de la variance réelle. Bien que présentant des avancées théoriques et pratiques importantes, ces méthodes sont aussi numériquement instables et les algorithmes actuellement disponibles sont coûteux en temps de calcul. Nous illustrons ces difficultés et nous proposons à la fois des modifications basées sur des techniques de lissage pour accroitre la stabilité numérique de ces estimateurs, ainsi qu’un algorithme plus efficace pour les obtenir. / Massive and automatic data processing requires the development of techniques able to filter the most important information. Among these methods, those with sparse structures have been shown to improve the statistical and computational efficiency of estimators in a context of large dimension. They can often be expressed as a solution of regularized empirical risk minimization and generally lead to non differentiable optimization problems in the form of a sum of a smooth term, measuring the quality of the fit, and a non-smooth term, penalizing complex solutions. Although it has considerable advantages, such a way of including prior information, unfortunately introduces many numerical difficulties both for solving the underlying optimization problem and to calibrate the level of regularization. Solving these issues has been at the heart of this thesis. A recently introduced technique, called "Screening Rules", proposes to ignore some variables during the optimization process by benefiting from the expected sparsity of the solutions. These elimination rules are said to be safe when the procedure guarantees to not reject any variable wrongly. In this work, we propose a unified framework for identifying important structures in these convex optimization problems and we introduce the "Gap Safe Screening Rules". They allows to obtain significant gains in computational time thanks to the dimensionality reduction induced by this method. In addition, they can be easily inserted into iterative algorithms and apply to a large number of problems.To find a good compromise between minimizing risk and introducing a learning bias, (exact) homotopy continuation algorithms offer the possibility of tracking the curve of the solutions as a function of the regularization parameters. However, they exhibit numerical instabilities due to several matrix inversions and are often expensive in large dimension. Another weakness is that a worst-case analysis shows that they have exact complexities that are exponential in the dimension of the model parameter. Allowing approximated solutions makes possible to circumvent the aforementioned drawbacks by approximating the curve of the solutions. In this thesis, we revisit the approximation techniques of the regularization paths given a predefined tolerance and we propose an in-depth analysis of their complexity w.r.t. the regularity of the loss functions involved. Hence, we propose optimal algorithms as well as various strategies for exploring the parameters space. We also provide calibration method (for the regularization parameter) that enjoys globalconvergence guarantees for the minimization of the empirical risk on the validation data.Among sparse regularization methods, the Lasso is one of the most celebrated and studied. Its statistical theory suggests choosing the level of regularization according to the amount of variance in the observations, which is difficult to use in practice because the variance of the model is oftenan unknown quantity. In such case, it is possible to jointly optimize the regression parameter as well as the level of noise. These concomitant estimates, appeared in the literature under the names of Scaled Lasso or Square-Root Lasso, and provide theoretical results as sharp as that of theLasso while being independent of the actual noise level of the observations. Although presenting important advances, these methods are numerically unstable and the currently available algorithms are expensive in computation time. We illustrate these difficulties and we propose modifications based on smoothing techniques to increase stability of these estimators as well as to introduce a faster algorithm.

Cette thèse est dédiée à l'étude de la hiérarchie moments-sommes-de-carrés, une famille de problèmes de programmation semi-définie en optimisation polynomiale, couramment appelée hiérarchie de Lasserre. Nous examinons différents aspects de ses propriétés et applications. Comme application de la hiérarchie, nous approchons certains objets potentiellement compliqués, comme l'abscisse polynomiale et les plans d'expérience optimaux sur des domaines semi-algébriques. L'application de la hiérarchie de Lasserre produit des approximations par des polynômes de degré fixé et donc de complexité bornée. En ce qui concerne la complexité de la hiérarchie elle-même, nous en construisons une modification pour laquelle un taux de convergence amélioré peut être prouvé. Un concept essentiel de la hiérarchie est l'utilisation des modules quadratiques et de leurs duaux pour appréhender de manière flexible le cône des polynômes positifs et le cône des moments. Nous poursuivons cette idée pour construire des approximations étroites d'ensembles semi-algébriques à l'aide de séparateurs polynomiaux. / This thesis is dedicated to investigations of the moment-sums-of-squares hierarchy, a family of semidefinite programming problems in polynomial optimization, commonly called the Lasserre hierarchy. We examine different aspects of its properties and purposes. As applications of the hierarchy, we approximate some potentially complicated objects, namely the polynomial abscissa and optimal designs on semialgebraic domains. Applying the Lasserre hierarchy results in approximations by polynomials of fixed degree and hence bounded complexity. With regard to the complexity of the hierarchy itself, we construct a modification of it for which an improved convergence rate can be proved. An essential concept of the hierarchy is to use quadratic modules and their duals as a tractable characterization of the cone of positive polynomials and the moment cone, respectively. We exploit further this idea to construct tight approximations of semialgebraic sets with polynomial separators.

No description available.

No description available.

Power conservation has become a severe issue in devices since battery capability advancement is not keeping pace with the swift development of other technologies such as processing technologies. This issue becomes critical when both the number of resource-intensive applications and the number of connected devices are rapidly growing. The former results in an increase in power consumption per device, and the latter causes an increase in the total power consumption of devices. Mobile edge computing (MEC) and low power wide area networks (LPWANs) are raised as two important research areas in wireless networks, which can assist devices to save power. On the one hand, devices are being considered as a platform to run resource-intensive applications while they have limited resources such as battery and processing capabilities. On the other hand, LPWANs raised as an important enabler for massive IoT (Internet of Things) to provide long-range and reliable connectivity for low power devices. The scope of this thesis spans over these two main research areas: (1) MEC, where devices can use radio resources to offload their processing tasks to the cloud to save energy. (2) LPWAN, with grant-free radio access where devices from different technology transmit their packets without any handshaking process. In particular, we consider a MEC network, where the processing resources are distributed in the proximity of the users. Hence, devices can save energy by transmitting the data to be processed to the edge cloud provided that the delay requirement is met and transmission power consumption is less than the local processing power consumption. This thesis addresses the question of whether to offload or not to minimize the uplink power consumption in a multi-cell multi-user MEC network. We consider the maximum acceptable delay as the QoS metric to be satisfied in our system. We formulate the problem as a mixed-integer nonlinear problem, which is converted into a convex form using D.C. approximation. To solve the converted optimization problem, we have proposed centralized and distributed algorithms for joint power allocation and channel assignment together with decision-making on job offloading. Our results show that there exists a region in which offloading can save power at mobile devices and increases the battery lifetime. Another focus of this thesis is on LPWANs, which are becoming more and more popular, due to the limited battery capacity and the ever-increasing need for durable battery lifetime for IoT networks. Most studies evaluate the system performance assuming single radio access technology deployment. In this thesis, we study the impact of coexisting competing radio access technologies on the system performance. We consider K technologies, defined by time and frequency activity factors, bandwidth, and power, which share a set of radio resources. Leveraging tools from stochastic geometry, we derive closed-form expressions for the successful transmission probability, expected battery lifetime, experienced delay, and expected number of retransmissions. Our analytical model, which is validated by simulation results, provides a tool to evaluate the coexistence scenarios and analyze how the introduction of a new coexisting technology may degrade the system performance in terms of success probability, delay, and battery lifetime. We further investigate the interplay between traffic load, the density of access points, and reliability/delay of communications, and examine the bounds beyond which, mean delay becomes infinite. / Antalet anslutna enheter till nätverk ökar. Det finns olika trender som mobil edgecomputing (MEC) och low power wide area-nätverk (LPWAN) som har blivit intressantai trådlösa nätverk. Därför står trådlösa nätverk inför nya utmaningar som ökadenergiförbrukning. I den här avhandlingen beaktar vi dessa två mobila nätverk. I MECavlastar mobila enheter sina bearbetningsuppgifter till centraliserad beräkningsresurser (”molnet”). I avhandlingensvarar vi på följande fråga: När det är energieffektivt att avlasta dessa beräkningsuppgifter till molnet?Vi föreslår två algoritmer för att bestämma den rätta tiden för överflyttning av beräkningsuppgifter till molnet.I LPWANs, antar vi att det finns ett mycket stort antal enheter av olika art som kommunicerar mednätverket. De använder s.k. ”Grant-free”-åtkomst för att ansluta till nätverket, där basstationerna inte ger explicita sändningstillstånd till enheterna. Denanalytiska modell som föreslås i avhandlingen utgör ett verktyg för att utvärdera sådana samexistensscenarier.Med verktygen kan vi analysera olika systems prestanda när det gäller framgångssannolikhet, fördröjning och batteriershållbarhetstid. / <p>QC 20200228</p> / SOOGreen

In order to implement privacy preservation for individuals, systems need to utilize privacy mechanisms that privatize sensitive data by randomization. The goal of privacy mechanism design is to find optimal tradeoffs between maximizing the utility of the privatized data while providing a strict sense of privacy defined by a chosen privacy measure. In this thesis, we explore this tradeoff for the pointwise maximal leakage measure. Pointwise maximal leakage (PML) was recently proposed as an operationally meaningful privacy measure that quantifies the guessing advantage of an adversary that is interested in a random function of the private data. Opposite to many other information-theoretic measures, PML considers the privacy loss for every outcome of the privatized view separately, thereby enabling more flexible privacy guarantees that move away from averaging over all outcomes. We start by using PML to analyze the prior distribution-dependent behavior of the established randomized response mechanism designed for local differential privacy. Then, we formulate a general optimization problem for the privacy-utility tradeoff with PML as a privacy measure and utility functions based on sub-linear functions. Using methods from convex optimization, we analyze the valid region of mechanisms satisfying a PML privacy guarantee and show that the optimization can be solved by a linear program. We arrive at extremal formulations that yield closed-form solutions for some important special cases: Binary mechanism, general high-privacy regions, i.e., regions in which the required level of privacy is high, and low-privacy mechanisms for equal priors. We further present an approximate solution for general priors in this setting. Finally, we analyze the loss of optimality of this construction for different prior distributions. / För att kunna implementera integritetsskydd för individer, så behöver system utnyttja integritetsmekanismer som privatiserar känslig data genom randomisering. Målet vid design av integritetsmekanismer är att hitta den optimala balansen mellan att användbarheten av privatiserad data maximeras, samtidigt som det tillhandahålls integritet i strikt mening. Detta definierat av något valt typ av integritetsmått. I den här avhandlingen, så undersöks detta utbyte specifikt med “pointwise maximal leakage”-måttet. Pointwise maximal leakage (PML) har nyligen föreslagits som ett operativt meningsfullt integritetsmått som kvantifierar en gissande motparts informationstillgång om denna är intresserad av en slumpmässig funktion av den privata datan. Till skillnad mot många andra informations-teoretiska mått, så tar PML i åtanke integritetsinskränkningen separat för varje utfall av den privata slumpmässiga variabeln. Därmed möjliggörs mer flexibla försäkringar av integriteten, som strävar bort från genomsnittet av alla utfall. Först, används PML för att analysera det ursprungsberoende beteendet av den etablerade “randomized response”-mekanismen designad för local differential privacy. Därefter formuleras ett generellt optimeringsproblem för integritets-användbarhets-kompromissen med PML som ett integritetsmått och användbarhetsfunktioner baserade på sublinjära funktioner. Genom att utnyttja metoder från konvex optimering, analyseras den giltiga regionen av mekanismer som tillfredsställer en PML-integritetsgaranti och det visas att optimeringen kan lösas av ett linjärt program. Det leder till extremala formuleringar som ger slutna lösningar för några viktiga specialfall: Binär mekanism, allmänna högintegritets-regioner (d.v.s. regioner där kravet på nivån av integritet är hög) och lågintegritets-mekanismer för ekvivalenta ursprungliga distributioner. Vidare presenteras en approximativ lösning för allmänna ursprungliga distributioner i denna miljö. Slutligen, analyseras förlusten av optimalitet hos denna konstruktion för olika ursprungliga distributioner.

[pt] Nesse trabalho, estudamos online packing integer programs, cujas colunas são reveladas uma a uma. Já que algoritmos ótimos foram encontrados para o modelo RANDOMORDER– onde a ordem na qual as colunas são reveladas para o algoritmo é aleatória – o foco da área se voltou para modelo menos otimistas. Um desses modelos é o modelo MIXED, no qual algumas colunas são ordenadas de forma adversária, enquanto outras chegam em ordem aleatória. Pouquíssimos resultados são conhecidos para online packing IPs no modelo MIXED, que é o objeto do nosso estudo. Consideramos problemas de online packing com d dimensões de ocupação (d restrições de empacotamento), cada uma com capacidade B. Assumimos que todas as recompensas e ocupações dos itens estão no intervalo [0, 1]. O objetivo do estudo é projetar um algoritmo no qual a presença de alguns itens adversários tenha um efeito limitado na competitividade do algoritmo relativa às colunas de ordem aleatória. Portanto, usamos como benchmark OPTStoch, que é o valor da solução ótima offline que considera apenas a parte aleatória da instância. Apresentamos um algoritmo que obtém recompensas de pelo menos (1 − 5lambda − Ó de epsilon)OPTStoch com alta probabilidade, onde lambda é a fração de colunas em ordem adversária. Para conseguir tal garantia, projetamos um algoritmo primal-dual onde as decisões são tomadas pelo algoritmo pela avaliação da recompensa e ocupação de cada item, de acordo com as variáveis duais do programa inteiro. Entretanto, diferentemente dos algoritmos primais-duais para o modelo RANDOMORDER, não podemos estimar as variáveis duais pela resolução de um problema reduzido. A causa disso é que, no modelo MIXED, um adversário pode facilmente manipular algumas colunas, para atrapalhar nossa estimação. Para contornar isso, propomos o uso de tecnicas conhecidas de online learning para aprender as variáveis duais do problema de forma online, conforme o problema progride. / [en] We study online packing integer programs, where the columns arrive one by one. Since optimal algorithms were found for the RANDOMORDER model – where columns arrive in random order – much focus of the area has been on less optimistic models. One of those models is the MIXED model, where some columns are adversarially ordered, while others come in random-order. Very few results are known for packing IPs in the MIXED model, which is the object of our study. We consider online IPs with d occupation dimensions (d packing constraints), each one with capacity (or right-hand side) B. We also assume all items rewards and occupations to be less or equal to 1. Our goal is to design an algorithm where the presence of adversarial columns has a limited effect on the algorithm s competitiveness relative to the random-order columns. Thus, we use OPTStoch – the offline optimal solution considering only the random-order part of the input – as a benchmark.We present an algorithm that, relative to OPTStoch, is (1−5 lambda− OBig O of epsilon)-competitive with high probability, where lambda is the fraction of adversarial columns. In order to achieve such a guarantee, we make use of a primal-dual algorithm where the decision variables are set by evaluating each item s reward and occupation according to the dual variables of the IP, like other algorithms for the RANDOMORDER model do. However, we can t hope to estimate those dual variables by solving a scaled version of problem, because they could easily be manipulated by an adversary in the MIXED model. Our solution was to use online learning techniques to learn all aspects of the dual variables in an online fashion, as the problem progresses.