Descriptor: "Mathematics - Optimization and Control" / Publisher: hal ccsd / Topic: fos: computer and information sciences - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Mathematics - Optimization and Control"' showing total 311 results

Start Over Descriptor "Mathematics - Optimization and Control" Topic fos: computer and information sciences Publisher hal ccsd

311 results on '"Mathematics - Optimization and Control"'

151. Handling correlated and repeated measurements with the smoothed multivariate square-root Lasso

Author: Bertrand, Quentin, Massias, Mathurin, Gramfort, Alexandre, Salmon, Joseph, Modelling brain structure, function and variability based on high-field MRI data (PARIETAL), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Service NEUROSPIN (NEUROSPIN), Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, Institut National de Recherche en Informatique et en Automatique (Inria), Institut Montpelliérain Alexander Grothendieck (IMAG), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Service NEUROSPIN (NEUROSPIN), Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [STAT.AP]Statistics [stat]/Applications [stat.AP], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Optimization and Control (math.OC), FOS: Mathematics, Machine Learning (stat.ML), Applications (stat.AP), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Statistics - Applications, Machine Learning (cs.LG)
Abstract: International audience; Sparsity promoting norms are frequently used in high dimensional regression. A limitation of such Lasso-type estimators is that the optimal regularization parameter depends on the unknown noise level. Estimators such as the concomitant Lasso address this dependence by jointly estimating the noise level and the regression coefficients. Additionally, in many applications, the data is obtained by averaging multiple measurements: this reduces the noise variance, but it dramatically reduces sample sizes and prevents refined noise modeling. In this work, we propose a concomitant estimator that can cope with complex noise structure by using non-averaged measurements. The resulting optimization problem is convex and amenable, thanks to smoothing theory, to state-of-the-art optimization techniques that leverage the sparsity of the solutions. Practical benefits are demonstrated on toy datasets, realistic simulated data and real neuroimaging data.
Published: 2019

152. A Fully Stochastic Primal-Dual Algorithm

Author: Pascal Bianchi, Adil Salim, Walid Hachem, Signal, Statistique et Apprentissage (S2A), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, and Communications Numériques (COMNUM)
Subjects: FOS: Computer and information sciences, Primal dual algorithm, 021103 operations research, Control and Optimization, Optimization problem, Computer science, 0211 other engineering and technologies, Forward–backward algorithm, Monotonic function, Machine Learning (stat.ML), 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Monotone polygon, Optimization and Control (math.OC), Statistics - Machine Learning, Saddle point, Convergence (routing), Convex optimization, FOS: Mathematics, Applied mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 0101 mathematics, [MATH]Mathematics [math], Mathematics - Optimization and Control
Abstract: International audience; A new stochastic primal-dual algorithm for solving a composite optimization problem is proposed. It is assumed that all the functions / operators that enter the optimization problem are given as statistical expectations. These expectations are unknown but revealed across time through i.i.d realizations. The proposed algorithm is proven to converge to a saddle point of the Lagrangian function. In the framework of the monotone operator theory, the convergence proof relies on recent results on the stochastic Forward Backward algorithm involving random monotone operators. An example of convex optimization under stochastic linear constraints is considered.
Published: 2019

153. Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization

Author: Barakat, Anas, Bianchi, Pascal, Signal, Statistique et Apprentissage (S2A), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Département Images, Données, Signal (IDS), Télécom ParisTech, and Institut Mines-Télécom [Paris] (IMT)-Télécom Paris
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, Machine Learning (stat.ML), Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: Although ADAM is a very popular algorithm for optimizing the weights of neural networks, it has been recently shown that it can diverge even in simple convex optimization examples. Several variants of ADAM have been proposed to circumvent this convergence issue. In this work, we study the ADAM algorithm for smooth nonconvex optimization under a boundedness assumption on the adaptive learning rate. The bound on the adaptive step size depends on the Lipschitz constant of the gradient of the objective function and provides safe theoretical adaptive step sizes. Under this boundedness assumption, we show a novel first order convergence rate result in both deterministic and stochastic contexts. Furthermore, we establish convergence rates of the function value sequence using the Kurdyka-Lojasiewicz property., 28 pages, 1 figure, published in ACML2020
Published: 2019

154. Convergence and Dynamical Behavior of the Adam Algorithm for Non Convex Stochastic Optimization

Author: Barakat, Anas, Bianchi, Pascal, Signal, Statistique et Apprentissage (S2A), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Département Images, Données, Signal (IDS), Télécom ParisTech, and Institut Mines-Télécom [Paris] (IMT)-Télécom Paris
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], Machine Learning (stat.ML), Dynamical Systems (math.DS), Machine Learning (cs.LG), [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Mathematics - Classical Analysis and ODEs, Optimization and Control (math.OC), Classical Analysis and ODEs (math.CA), FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Dynamical Systems, [MATH]Mathematics [math], Mathematics - Optimization and Control
Abstract: Adam is a popular variant of stochastic gradient descent for finding a local minimizer of a function. In the constant stepsize regime, assuming that the objective function is differentiable and non-convex, we establish the convergence in the long run of the iterates to a stationary point under a stability condition. The key ingredient is the introduction of a continuous-time version of Adam, under the form of a non-autonomous ordinary differential equation. This continuous-time system is a relevant approximation of the Adam iterates, in the sense that the interpolated Adam process converges weakly towards the solution to the ODE. The existence and the uniqueness of the solution are established. We further show the convergence of the solution towards the critical points of the objective function and quantify its convergence rate under a Lojasiewicz assumption. Then, we introduce a novel decreasing stepsize version of Adam. Under mild assumptions, it is shown that the iterates are almost surely bounded and converge almost surely to critical points of the objective function. Finally, we analyze the fluctuations of the algorithm by means of a conditional central limit theorem., Comment: 30 pages
Published: 2019

155. Quantum and Classical Algorithms for Approximate Submodular Function Minimization

Author: Hamoudi, Yassine, Rebentrost, Patrick, Rosmanis, Ansis, Santha, Miklos, Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Centre for Quantum Technologies [Singapore] (CQT), National University of Singapore (NUS), and Santha, Miklos
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Computer Science - Machine Learning, Quantum Physics, FOS: Physical sciences, Machine Learning (stat.ML), Machine Learning (cs.LG), Statistics - Machine Learning, Optimization and Control (math.OC), Computer Science - Data Structures and Algorithms, FOS: Mathematics, Data Structures and Algorithms (cs.DS), [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Quantum Physics (quant-ph), Mathematics - Optimization and Control
Abstract: Submodular functions are set functions mapping every subset of some ground set of size $n$ into the real numbers and satisfying the diminishing returns property. Submodular minimization is an important field in discrete optimization theory due to its relevance for various branches of mathematics, computer science and economics. The currently fastest strongly polynomial algorithm for exact minimization [LSW15] runs in time $\widetilde{O}(n^3 \cdot \mathrm{EO} + n^4)$ where $\mathrm{EO}$ denotes the cost to evaluate the function on any set. For functions with range $[-1,1]$, the best $\epsilon$-additive approximation algorithm [CLSW17] runs in time $\widetilde{O}(n^{5/3}/\epsilon^{2} \cdot \mathrm{EO})$. In this paper we present a classical and a quantum algorithm for approximate submodular minimization. Our classical result improves on the algorithm of [CLSW17] and runs in time $\widetilde{O}(n^{3/2}/\epsilon^2 \cdot \mathrm{EO})$. Our quantum algorithm is, up to our knowledge, the first attempt to use quantum computing for submodular optimization. The algorithm runs in time $\widetilde{O}(n^{5/4}/\epsilon^{5/2} \cdot \log(1/\epsilon) \cdot \mathrm{EO})$. The main ingredient of the quantum result is a new method for sampling with high probability $T$ independent elements from any discrete probability distribution of support size $n$ in time $O(\sqrt{Tn})$. Previous quantum algorithms for this problem were of complexity $O(T\sqrt{n})$., Comment: 24 pages, Journal version
Published: 2019

156. Mean-Field Langevin Dynamics and Energy Landscape of Neural Networks

Author: Kaitong Hu, David Šiška, Zhenjie Ren, Łukasz Szpruch, Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), School of Mathematics - University of Edinburgh, and University of Edinburgh
Subjects: FOS: Computer and information sciences, Statistics and Probability, Gradient Flow, Neural Networks, Probability (math.PR), 010102 general mathematics, Machine Learning (stat.ML), 01 natural sciences, 010104 statistics & probability, 60H30, 37M25, Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, Mean-Field Langevin Dynamics, 0101 mathematics, Statistics, Probability and Uncertainty, [MATH]Mathematics [math], Humanities, Mathematics - Optimization and Control, Mathematics - Probability, Mathematics
Abstract: Our work is motivated by a desire to study the theoretical underpinning for the convergence of stochastic gradient type algorithms widely used for non-convex learning tasks such as training of neural networks. The key insight, already observed in the works of Mei, Montanari and Nguyen (2018), Chizat and Bach (2018) as well as Rotskoff and Vanden-Eijnden (2018), is that a certain class of the finite-dimensional non-convex problems becomes convex when lifted to infinite-dimensional space of measures. We leverage this observation and show that the corresponding energy functional defined on the space of probability measures has a unique minimiser which can be characterised by a first-order condition using the notion of linear functional derivative. Next, we study the corresponding gradient flow structure in 2-Wasserstein metric, which we call Mean-Field Langevin Dynamics (MFLD), and show that the flow of marginal laws induced by the gradient flow converges to a stationary distribution, which is exactly the minimiser of the energy functional. We observe that this convergence is exponential under conditions that are satisfied for highly regularised learning tasks. Our proof of convergence to stationary probability measure is novel and it relies on a generalisation of LaSalle's invariance principle combined with HWI inequality. Importantly, we assume neither that interaction potential of MFLD is of convolution type nor that it has any particular symmetric structure. Furthermore, we allow for the general convex objective function, unlike, most papers in the literature that focus on quadratic loss. Finally, we show that the error between finite-dimensional optimisation problem and its infinite-dimensional limit is of order one over the number of parameters., 31 pages
Published: 2019

157. Targeting Solutions in Bayesian Multi-Objective Optimization: Sequential and Batch Versions

Author: Victor Picheny, Benoit Enaux, David Gaudrie, Rodolphe Le Riche, Vincent Herbert, École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), Institut Mines-Télécom [Paris] (IMT), PSA Peugeot - Citroën (PSA), PSA Peugeot Citroën (PSA), Institut Henri Fayol (FAYOL-ENSMSE), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Département Génie mathématique et industriel (FAYOL-ENSMSE), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Institut Henri Fayol, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Institut National de la Recherche Agronomique (INRA), Ecole Nationale Supérieure des Mines de St Etienne-Institut Henri Fayol, Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne (UCA)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Mathematical optimization, Computer science, Parallel optimization, Computer experiments, Gaussian processes, Context (language use), Machine Learning (stat.ML), 02 engineering and technology, [STAT.OT]Statistics [stat]/Other Statistics [stat.ML], Multi-objective optimization, Machine Learning (cs.LG), Set (abstract data type), symbols.namesake, Statistics - Machine Learning, Artificial Intelligence, Convergence (routing), 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Mathematics - Optimization and Control, Gaussian process, Bayesian optimization, Applied Mathematics, Pareto principle, Preference-based optimization, Computer experiment, Optimization and Control (math.OC), symbols, 020201 artificial intelligence & image processing, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: International audience; Multi-objective optimization aims at finding trade-off solutions to conflicting objectives. These constitute the Pareto optimal set. In the context of expensive-to-evaluate functions, it is impossible and often non-informative to look for the entire set. As an end-user would typically prefer a certain part of the objective space, we modify the Bayesian multi-objective optimization algorithm which uses Gaussian Processes to maximize the Expected Hypervolume Improvement, to focus the search in the preferred region. The cumulated effects of the Gaussian Processes and the targeting strategy lead to a particularly efficient convergence to the desired part of the Pareto set. To take advantage of parallel computing, a multi-point extension of the targeting criterion is proposed and analyzed.
Published: 2019

158. Multilinear compressive sensing and an application to convolutional linear networks

Author: Malgouyres, François, Landsberg, Joseph, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UPS), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-PRES Université de Toulouse-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics [Texas] (TAMU), and Texas A&M University [College Station]
Subjects: FOS: Computer and information sciences, convolutional networks, convolutional networks AMS subject classifications 68T05, Computer Science - Artificial Intelligence, Mathematics - Statistics Theory, Statistics Theory (math.ST), [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], matrix factorization, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, AMS subject classifications. 68T05, 90C99, 15-02, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], FOS: Mathematics, Mathematics - Optimization and Control, 25 convolutional networks 26 AMS subject classifications 68T05, [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT], Interpretable learning, Artificial Intelligence (cs.AI), deep linear networks, Optimization and Control (math.OC), 15-02 27, stable recovery, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: International audience; We study a deep linear network endowed with a structure. It takes the form of a matrix $X$ obtained by multiplying $K$ matrices (called factors and corresponding to the action of the layers). The action of each layer (i.e. a factor) is obtained by applying a fixed linear operator to a vector of parameters satisfying a constraint. The number of layers is not limited. Assuming that $X$ is given and factors have been estimated, the error between the product of the estimated factors and $X$ (i.e. the reconstruction error) is either the statistical or the empirical risk. In this paper, we provide necessary and sufficient conditions on the network topology under which a stability property holds. The stability property requires that the error on the parameters defining the factors (i.e. the stability of the recovered parameters) scales linearly with the reconstruction error (i.e. the risk). Therefore, under these conditions on the network topology, any successful learning task leads to stably defined features and therefore interpretable layers/network.In order to do so, we first evaluate how the Segre embedding and its inverse distort distances. Then, we show that any deep structured linear network can be cast as a generic multilinear problem (that uses the Segre embedding). This is the {\em tensorial lifting}. Using the tensorial lifting, we provide necessary and sufficient conditions for the identifiability of the factors (up to a scale rearrangement). We finally provide the necessary and sufficient condition called \NSPlong~(because of the analogy with the usual Null Space Property in the compressed sensing framework) which guarantees that the stability property holds. We illustrate the theory with a practical example where the deep structured linear network is a convolutional linear network. As expected, the conditions are rather strong but not empty. A simple test on the network topology can be implemented to test if the condition holds.
Published: 2019

159. Shadow simulated annealing algorithm : a new tool for global optimisation and statistical inference

Author: Stoica, R., Deaconu, Madalina, Philippe, Anne, Hurtado, Lluis, Institut Élie Cartan de Lorraine (IECL), Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Processus aléatoires spatio-temporels et leurs applications (PASTA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Élie Cartan de Lorraine (IECL), Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Simuler et calibrer des modèles stochastiques (TOSCA-NGE-POST), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Mathématiques Jean Leray (LMJL), Centre National de la Recherche Scientifique (CNRS)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN), Departamento de Matemática Aplicada y Estadística [Madrid], Universidad San Pablo CEU, The authors are grateful to Elmo Tempel for providing the SDSS data set sample., and Part of the work of the first author was supported by a grant of the Ministry of National Education and Scientific Research, RDI Program for Space Technology and Advanced Research - STAR, project number 513.
Subjects: FOS: Computer and information sciences, [STAT.AP]Statistics [stat]/Applications [stat.AP], Spatial pattern analysis, Point processes, Mathematics - Statistics Theory, Statistics Theory (math.ST), 2000 Mathematics Subject Classification : 60J22, 60G55, [STAT.TH]Statistics [stat]/Statistics Theory [stat.TH], Maximum likelihood estimation, Statistics - Applications, Non-homogeneous Markov chains, Global optimisation, Methodology (stat.ME), [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Optimization and Control (math.OC), [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Computational methods in Markov chains, FOS: Mathematics, Applications (stat.AP), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, [STAT.ME]Statistics [stat]/Methodology [stat.ME], Statistics - Methodology
Abstract: This paper develops a new global optimisation method that applies to a family of criteria that are not entirely known. This family includes the criteria obtained from the class of posteriors that have nor-malising constants that are analytically not tractable. The procedure applies to posterior probability densities that are continuously differen-tiable with respect to their parameters. The proposed approach avoids the re-sampling needed for the classical Monte Carlo maximum likelihood inference, while providing the missing convergence properties of the ABC based methods. Results on simulated data and real data are presented. The real data application fits an inhomogeneous area interaction point process to cosmological data. The obtained results validate two important aspects of the galaxies distribution in our Universe : proximity of the galaxies from the cosmic filament network together with territorial clustering at given range of interactions. Finally, conclusions and perspectives are depicted.
Published: 2019

160. Non-asymptotic Analysis of Biased Stochastic Approximation Scheme

Author: Karimi, Belhal, Miasojedow, Blazej, Moulines, Eric, Wai, Hoi-To, Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Modélisation en pharmacologie de population (XPOP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), Department of Systems Engineering and Engineering Management (SEEM), and The Chinese University of Hong Kong [Hong Kong]
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Biased stochastic approximation, Machine Learning (stat.ML), Policy gradient, Machine Learning (cs.LG), [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Optimization and Control (math.OC), Non-convex optimization, Online expectation-maximization, FOS: Mathematics, State-dependent Markov chain, Mathematics - Optimization and Control
Abstract: Stochastic approximation (SA) is a key method used in statistical learning. Recently, its non-asymptotic convergence analysis has been considered in many papers. However, most of the prior analyses are made under restrictive assumptions such as unbiased gradient estimates and convex objective function, which significantly limit their applications to sophisticated tasks such as online and reinforcement learning. These restrictions are all essentially relaxed in this work. In particular, we analyze a general SA scheme to minimize a non-convex, smooth objective function. We consider update procedure whose drift term depends on a state-dependent Markov chain and the mean field is not necessarily of gradient type, covering approximate second-order method and allowing asymptotic bias for the one-step updates. We illustrate these settings with the online EM algorithm and the policy-gradient method for average reward maximization in reinforcement learning., Comment: Accepted to COLT 2019; 32 pages. Minor updates in Section 3.2
Published: 2019

161. SGD: General Analysis and Improved Rates

Author: Gower, Robert, Loizou, Nicolas, Qian, Xun, Sailanbayev, Alibek, Shulgin, Egor, Richtárik, Peter, Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Signal, Statistique et Apprentissage (S2A), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Département Images, Données, Signal (IDS), Télécom ParisTech, University of Edinburgh, King Abdullah University of Science and Technology (KAUST), School of Science and Technology [Kazakhstan], Nazarbayev University [Kazakhstan], Moscow Institute of Physics and Technology [Moscow] (MIPT), School of Mathematics - University of Edinburgh, Robert M. Gower acknowledges the support by a public grant as part of the Investissement d’avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH, in a joint call with Gaspard Monge Program for optimization, operations research and their interactions with data sciences., Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)
Subjects: FOS: Computer and information sciences, Computer Science::Machine Learning, Computer Science - Machine Learning, Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, Machine Learning (stat.ML), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: We propose a general yet simple theorem describing the convergence of SGD under the arbitrary sampling paradigm. Our theorem describes the convergence of an infinite array of variants of SGD, each of which is associated with a specific probability law governing the data selection rule used to form mini-batches. This is the first time such an analysis is performed, and most of our variants of SGD were never explicitly considered in the literature before. Our analysis relies on the recently introduced notion of expected smoothness and does not rely on a uniform bound on the variance of the stochastic gradients. By specializing our theorem to different mini-batching strategies, such as sampling with replacement and independent sampling, we derive exact expressions for the stepsize as a function of the mini-batch size. With this we can also determine the mini-batch size that optimizes the total complexity, and show explicitly that as the variance of the stochastic gradient evaluated at the minimum grows, so does the optimal mini-batch size. For zero variance, the optimal mini-batch size is one. Moreover, we prove insightful stepsize-switching rules which describe when one should switch from a constant to a decreasing stepsize regime., 23 pages, 6 figures
Published: 2019

162. Metastability in Stochastic Replicator Dynamics

Author: Konstantin Avrachenkov, Vivek S. Borkar, Network Engineering and Operations (NEO ), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Electrical Engineering [IIT-Bombay] (EE-IIT), and Indian Institute of Technology Kanpur (IIT Kanpur)
Subjects: FOS: Computer and information sciences, Statistics and Probability, 0209 industrial biotechnology, Economics and Econometrics, Change of variables, stochastic replicator dynamics, Primary: 91A22, Secondary: 91A25, 60H10, 34F05, 0211 other engineering and technologies, Dynamical Systems (math.DS), 02 engineering and technology, Noise (electronics), Domain (mathematical analysis), law.invention, 020901 industrial engineering & automation, law, Computer Science - Computer Science and Game Theory, small noise asymptotics, Metastability, Intermittency, Replicator equation, metastable states, intermittency, FOS: Mathematics, [INFO]Computer Science [cs], Statistical physics, Mathematics - Dynamical Systems, Mathematics - Optimization and Control, Mathematics, 021103 operations research, Langevin equation on sphere, Applied Mathematics, Probability (math.PR), mean exit time, Computer Graphics and Computer-Aided Design, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], Computer Science Applications, Langevin equation, quasi-stationary distributions, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Computational Mathematics, Computational Theory and Mathematics, Optimization and Control (math.OC), Mathematics - Probability, Computer Science and Game Theory (cs.GT)
Abstract: We consider a novel model of stochastic replicator dynamics for potential games that converts to a Langevin equation on a sphere after a change of variables. This is distinct from the models studied earlier. In particular, it is ill-posed due to non-uniqueness of solutions, but is amenable to a natural selection principle that picks a unique solution. The model allows us to make specific statements regarding metastable states such as small noise asymptotics for mean exit times from their domain of attraction, and quasi-stationary measures. We illustrate the general results by specializing them to replicator dynamics on graphs and demonstrate that the numerical experiments support theoretical predictions., 39 pages, 7 figures
Published: 2019

163. An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration

Author: Hongzhou Lin, Zaid Harchaoui, Julien Mairal, Apprentissage de modèles à partir de données massives (Thoth ), Laboratoire Jean Kuntzmann (LJK ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria), Computer Science and Artificial Intelligence Laboratory [Cambridge] (CSAIL), Massachusetts Institute of Technology (MIT), University of Washington [Seattle], This work was supported by the ERC grant SOLARIS (number 714381), a grant from ANR (MACARON project ANR-14-CE23-0003-01), the program ``Learning in Machines and Brains' (CIFAR), and the project Titan (CNRS-Mastodons)., ANR-14-CE23-0003,MACARON,Apprentissage statistique à grande échelle et applications(2014), European Project: 714381,H2020,SOLARIS(2017), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jean Kuntzmann (LJK ), and Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])
Subjects: FOS: Computer and information sciences, Optimization problem, convex optimization, 0211 other engineering and technologies, Machine Learning (stat.ML), 010103 numerical & computational mathematics, 02 engineering and technology, [STAT.OT]Statistics [stat]/Other Statistics [stat.ML], 01 natural sciences, Regularization (mathematics), Theoretical Computer Science, Statistics - Machine Learning, FOS: Mathematics, 0101 mathematics, large-scale machine learning, Mathematics - Optimization and Control, Mathematics, Variable (mathematics), 021103 operations research, Quasi-Newton, Optimization and Control (math.OC), Broyden–Fletcher–Goldfarb–Shanno algorithm, Metric (mathematics), Convex optimization, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Gradient descent, Convex function, Algorithm, Software
Abstract: We propose an inexact variable-metric proximal point algorithm to accelerate gradient-based optimization algorithms. The proposed scheme, called QNing can be notably applied to incremental first-order methods such as the stochastic variance-reduced gradient descent algorithm (SVRG) and other randomized incremental optimization algorithms. QNing is also compatible with composite objectives, meaning that it has the ability to provide exactly sparse solutions when the objective involves a sparsity-inducing regularization. When combined with limited-memory BFGS rules, QNing is particularly effective to solve high-dimensional optimization problems, while enjoying a worst-case linear convergence rate for strongly convex problems. We present experimental results where QNing gives significant improvements over competing methods for training machine learning methods on large samples and in high dimensions., to appear in SIAM Journal on Optimization
Published: 2019

164. GuSTO: Guaranteed Sequential Trajectory Optimization via Sequential Convex Programming

Author: Marco Pavone, Abhishek Cauligi, Andrew Bylard, Riccardo Bonalli, Department of Aeronautics and Astronautics [Stanford] (AA Stanford), and Stanford University
Subjects: FOS: Computer and information sciences, 020301 aerospace & aeronautics, 0209 industrial biotechnology, Mathematical optimization, Current (mathematics), Computer science, Computation, Context (language use), 02 engineering and technology, Trajectory optimization, Optimal control, Stationary point, Computer Science - Robotics, 020901 industrial engineering & automation, 0203 mechanical engineering, Optimization and Control (math.OC), FOS: Mathematics, Robot, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Robotics (cs.RO), Mathematics - Optimization and Control
Abstract: Sequential Convex Programming (SCP) has recently seen a surge of interest as a tool for trajectory optimization. However, most available methods lack rigorous performance guarantees and they are often tailored to specific optimal control setups. In this paper, we present GuSTO (Guaranteed Sequential Trajectory Optimization), an algorithmic framework to solve trajectory optimization problems for control-affine systems with drift. GuSTO generalizes earlier SCP-based methods for trajectory optimization (by addressing, for example, goal-set constraints and problems with either fixed or free final time) and enjoys theoretical convergence guarantees in terms of convergence to, at least, a stationary point. The theoretical analysis is further leveraged to devise an accelerated implementation of GuSTO, which originally infuses ideas from indirect optimal control into an SCP context. Numerical experiments on a variety of trajectory optimization setups show that GuSTO generally outperforms current state-of-the-art approaches in terms of success rates, solution quality, and computation times., Extended version
Published: 2019

165. Deep Learning Based Online Power Control for Large Energy Harvesting Networks

Author: Merouane Debbah, Mohamad Assaad, Mohit K. Sharma, Alessio Zappone, Laboratoire des signaux et systèmes (L2S), and Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
Subjects: Scheme (programming language), Signal Processing (eess.SP), FOS: Computer and information sciences, Computer Science - Machine Learning, Computer science, 02 engineering and technology, Machine Learning (cs.LG), [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 0203 mechanical engineering, 0202 electrical engineering, electronic engineering, information engineering, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Electrical Engineering and Systems Science - Signal Processing, Mathematics - Optimization and Control, ComputingMilieux_MISCELLANEOUS, computer.programming_language, Stochastic control, Artificial neural network, business.industry, Deep learning, 020206 networking & telecommunications, 020302 automobile design & engineering, Transmitter power output, Optimization and Control (math.OC), State (computer science), Artificial intelligence, Markov decision process, business, computer, Power control
Abstract: In this paper, we propose a deep learning based approach to design online power control policies for large EH networks, which are often intractable stochastic control problems. In the proposed approach, for a given EH network, the optimal online power control rule is learned by training a deep neural network (DNN), using the solution of offline policy design problem. Under the proposed scheme, in a given time slot, the transmit power is obtained by feeding the current system state to the trained DNN. Our results illustrate that the DNN based online power control scheme outperforms a Markov decision process based policy. In general, the proposed deep learning based approach can be used to find solutions to large intractable stochastic control problems., Comment: 5 pages, to appear at ICASSP 2019
Published: 2019

166. Nonlinear mapping and distance geometry

Author: Pierre Blanchard, Olivier Coulaud, Alain Franc, Biodiversité, Gènes & Communautés (BioGeCo), Université de Bordeaux (UB)-Institut National de la Recherche Agronomique (INRA), from patterns to models in computational biodiversity and biotechnology (PLEIADE), Université de Bordeaux (UB)-Institut National de la Recherche Agronomique (INRA)-Université de Bordeaux (UB)-Institut National de la Recherche Agronomique (INRA)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, High-End Parallel Algorithms for Challenging Numerical Simulations (HiePACS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Biodiversité, Gènes & Communautés (BioGeCo), Université de Bordeaux (UB)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Université de Bordeaux (UB)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, Control and Optimization, Optimization problem, Distance Geometry Problem, [SDV]Life Sciences [q-bio], 02 engineering and technology, Astrophysics::Cosmology and Extragalactic Astrophysics, [SDV.BID]Life Sciences [q-bio]/Biodiversity, Least Square Scaling, Matrix (mathematics), 0504 sociology, Mathematics - Metric Geometry, Euclidean geometry, 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Applied mathematics, Nonlinear Mapping, Scaling, Mathematics - Optimization and Control, Mathematics, Euclidean space, 05 social sciences, 050401 social sciences methods, Metric Geometry (math.MG), 020202 computer hardware & architecture, Nonlinear system, Compact space, Optimization and Control (math.OC), Computer Science - Computational Geometry, Realization (systems)
Abstract: International audience; Distance Geometry Problem (DGP) and Nonlinear Mapping (NLM) are two well established questions: DGP is about finding a Euclidean realization of an incomplete set of distances in a Euclidean space, whereas Nonlinear Mapping is a weighted Least Square Scaling (LSS) method. We show how all these methods (LSS, NLM, DGP) can be assembled in a common framework, being each identified as an instance of an optimization problem with a choice of a weight matrix. We study the continuity between the solutions (which are point clouds) when the weight matrix varies, and the compactness of the set of solutions (after centering). We finally study a numerical example, showing that solving the optimization problem is far from being simple and that the numerical solution for a given procedure may be trapped in a local minimum.
Published: 2019

167. Accelerated decentralized optimization with local updates for smooth and strongly convex objectives

Author: Hendrikx, Hadrien, Bach, Francis, Massoulié, Laurent, Microsoft Research - Inria Joint Centre (MSR - INRIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Microsoft Research Laboratory Cambridge-Microsoft Corporation [Redmond, Wash.], Dynamics of Geometric Networks (DYOGENE), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Statistical Machine Learning and Parsimony (SIERRA), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Computer Science - Distributed, Parallel, and Cluster Computing, Optimization and Control (math.OC), TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, FOS: Mathematics, Distributed, Parallel, and Cluster Computing (cs.DC), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: In this paper, we study the problem of minimizing a sum of smooth and strongly convex functions split over the nodes of a network in a decentralized fashion. We propose the algorithm $ESDACD$, a decentralized accelerated algorithm that only requires local synchrony. Its rate depends on the condition number $\kappa$ of the local functions as well as the network topology and delays. Under mild assumptions on the topology of the graph, $ESDACD$ takes a time $O((\tau_{\max} + \Delta_{\max})\sqrt{{\kappa}/{\gamma}}\ln(\epsilon^{-1}))$ to reach a precision $\epsilon$ where $\gamma$ is the spectral gap of the graph, $\tau_{\max}$ the maximum communication delay and $\Delta_{\max}$ the maximum computation time. Therefore, it matches the rate of $SSDA$, which is optimal when $\tau_{\max} = \Omega\left(\Delta_{\max}\right)$. Applying $ESDACD$ to quadratic local functions leads to an accelerated randomized gossip algorithm of rate $O( \sqrt{\theta_{\rm gossip}/n})$ where $\theta_{\rm gossip}$ is the rate of the standard randomized gossip. To the best of our knowledge, it is the first asynchronous gossip algorithm with a provably improved rate of convergence of the second moment of the error. We illustrate these results with experiments in idealized settings.
Published: 2019

168. Regularized Contextual Bandits

Author: Fontaine, Xavier, Berthet, Quentin, Perchet, Vianney, Centre de Mathématiques et de Leurs Applications (CMLA), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS), Statistical Laboratory [Cambridge], Department of Pure Mathematics and Mathematical Statistics (DPMMS), Faculty of mathematics Centre for Mathematical Sciences [Cambridge] (CMS), University of Cambridge [UK] (CAM)-University of Cambridge [UK] (CAM)-Faculty of mathematics Centre for Mathematical Sciences [Cambridge] (CMS), University of Cambridge [UK] (CAM)-University of Cambridge [UK] (CAM), Criteo AI Lab, Criteo [Paris], and Fontaine, Xavier
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Machine Learning (stat.ML), [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], [STAT.ML] Statistics [stat]/Machine Learning [stat.ML], Machine Learning (cs.LG), [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract: We consider the stochastic contextual bandit problem with additional regularization. The motivation comes from problems where the policy of the agent must be close to some baseline policy which is known to perform well on the task. To tackle this problem we use a nonparametric model and propose an algorithm splitting the context space into bins, and solving simultaneously - and independently - regularized multi-armed bandit instances on each bin. We derive slow and fast rates of convergence, depending on the unknown complexity of the problem. We also consider a new relevant margin condition to get problem-independent convergence rates, ending up in intermediate convergence rates interpolating between the aforementioned slow and fast rates., Comment: AISTATS 2019, 23 pages, 2 figures
Published: 2019

169. A Random Block-Coordinate Douglas-Rachford Splitting Method with Low Computational Complexity for Binary Logistic Regression

Author: Luis M. Briceño-Arias, Jean-Christophe Pesquet, Emilie Chouzenoux, Giovanni Chierchia, Centre de modélisation mathématique (CMM), Universitad de Chile-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Centre de vision numérique (CVN), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec, OPtimisation Imagerie et Santé (OPIS), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de vision numérique (CVN), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-CentraleSupélec, and Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM)
Subjects: FOS: Computer and information sciences, Control and Optimization, Computational complexity theory, Computer Science - Artificial Intelligence, 0211 other engineering and technologies, Logistic regression, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], symbols.namesake, Operator (computer programming), Lambert W function, Douglas-Rachford splitting, Block-coordinate descent, FOS: Mathematics, 0101 mathematics, Mathematics - Optimization and Control, Block (data storage), Mathematics, 021103 operations research, Training set, Optimization algorithm, Applied Mathematics, Computational Mathematics, Artificial Intelligence (cs.AI), Proximity operator, Optimization and Control (math.OC), symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Algorithm
Abstract: International audience; In this paper, we propose a new optimization algorithm for sparse logistic regression based on a stochastic version of the Douglas-Rachford splitting method. Our algorithm sweeps the training set by randomly selecting a mini-batch of data at each iteration, and it allows us to update the variables in a block coordinate manner. Our approach leverages the proximity operator of the logistic loss, which is expressed with the generalized Lambert W function. Experiments carried out on standard datasets demonstrate the efficiency of our approach w.r.t. stochastic gradient-like methods.
Published: 2019

170. On Bi-Objective convex-quadratic problems

Author: Anne Auger, Nikolaus Hansen, Dimo Brockhoff, Cheikh Touré, Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Randomized Optimisation (RANDOPT ), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, Hessian matrix, TheoryofComputation_MISCELLANEOUS, Mathematical optimization, Computer science, MathematicsofComputing_NUMERICALANALYSIS, 0102 computer and information sciences, 02 engineering and technology, Convex-quadratic problems, [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], 01 natural sciences, Multi-objective optimization, Convexity, Set (abstract data type), symbols.namesake, Line segment, Quadratic equation, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Neural and Evolutionary Computing (cs.NE), Convex Pareto front, [MATH]Mathematics [math], Pareto set, Mathematics - Optimization and Control, Pareto principle, Computer Science - Neural and Evolutionary Computing, Optimization and Control (math.OC), 010201 computation theory & mathematics, symbols, Rotational invariance, 020201 artificial intelligence & image processing, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Bi-objective optimization
Abstract: In this paper we analyze theoretical properties of bi-objective convex-quadratic problems. We give a complete description of their Pareto set and prove the convexity of their Pareto front. We show that the Pareto set is a line segment when both Hessian matrices are proportional. We then propose a novel set of convex-quadratic test problems, describe their theoretical properties and the algorithm abilities required by those test problems. This includes in particular testing the sensitivity with respect to separability, ill-conditioned problems, rotational invariance, and whether the Pareto set is aligned with the coordinate axis., 12 pages
Published: 2019

171. Learning in games with continuous action spaces and unknown payoff functions

Author: Zhengyuan Zhou, Panayotis Mertikopoulos, Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Department of Electrical Engineering [Stanford], Stanford University, and ANR-16-CE33-0004,ORACLESS,Stratégies adaptatives d'allocation des ressources dans les réseaux sans fil dynamiques(2016)
Subjects: FOS: Computer and information sciences, Class (set theory), Mathematical optimization, Computer Science::Computer Science and Game Theory, General Mathematics, 0211 other engineering and technologies, Stability (learning theory), 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Machine Learning (cs.LG), symbols.namesake, Computer Science - Computer Science and Game Theory, Convergence (routing), FOS: Mathematics, 0101 mathematics, Mathematics - Optimization and Control, ComputingMilieux_MISCELLANEOUS, Mathematics, Sequence, 021103 operations research, Stochastic game, Primary 91A26, 90C15, secondary 90C33, 68Q32, Dual (category theory), Computer Science - Learning, Nash equilibrium, Optimization and Control (math.OC), Bounded function, symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Software, Computer Science and Game Theory (cs.GT)
Abstract: This paper examines the convergence of no-regret learning in games with continuous action sets. For concreteness, we focus on learning via "dual averaging", a widely used class of no-regret learning schemes where players take small steps along their individual payoff gradients and then "mirror" the output back to their action sets. In terms of feedback, we assume that players can only estimate their payoff gradients up to a zero-mean error with bounded variance. To study the convergence of the induced sequence of play, we introduce the notion of variational stability, and we show that stable equilibria are locally attracting with high probability whereas globally stable equilibria are globally attracting with probability 1. We also discuss some applications to mixed-strategy learning in finite games, and we provide explicit estimates of the method's convergence speed., Comment: 36 pages, 2 figures; completely reworked structure of first version and dropped individual concavity assumptions
Published: 2019

172. SPECTRA – a Maple library for solving linear matrix inequalities in exact arithmetic

Author: Din, Mohab Safey El, Henrion, Didier, Naldi, Simone, Safey, Mohab, Din, El, Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Czech Technical University in Prague (CTU), Technische Universität Dortmund [Dortmund] (TU), Polynomial Systems (PolSys), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), European Project: 666981,H2020,ERC-2014-ADG,TAMING(2015), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), and Université Fédérale Toulouse Midi-Pyrénées
Subjects: FOS: Computer and information sciences, Computer Science - Symbolic Computation, Control and Optimization, MathematicsofComputing_NUMERICALANALYSIS, Linear matrix inequalities, 010103 numerical & computational mathematics, Symbolic Computation (cs.SC), Linear matrix, engineering.material, 01 natural sciences, Mathematics - Algebraic Geometry, Polynomial sums of squares, Symbolic computation, Real algebraic geometry, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, Computer Science::Symbolic Computation, Semidefinite programming, 0101 mathematics, Algebra over a field, Arithmetic, Algebraic Geometry (math.AG), Mathematics - Optimization and Control, Mathematics, Discrete mathematics, Maple, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Applied Mathematics, 010102 general mathematics, Degenerate energy levels, Algebra, Optimization and Control (math.OC), engineering, Computer algebra, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Software, Low rank matrices
Abstract: This document describes our freely distributed Maple library {\sc spectra}, for Semidefinite Programming solved Exactly with Computational Tools of Real Algebra. It solves linear matrix inequalities with symbolic computation in exact arithmetic and it is targeted to small-size, possibly degenerate problems for which symbolic infeasibility or feasibility certificates are required., Significantly extended version
Published: 2019

173. Non-Asymptotic Analysis of Fractional Langevin Monte Carlo for Non-Convex Optimization

Author: Nguyen, Thanh, Şimşekli, Umut, Richard, Gael, RICHARD, Gaël, Méthodes distribuées et parallèles de Monte-Carlo par chaînes de Markov pour l'Inférence Bayésienne de modèles à factorisation de tenseurs - - FBIMATRIX2016 - ANR-16-CE23-0014 - AAPG2016 - VALID, Département Images, Données, Signal (IDS), Télécom ParisTech, Signal, Statistique et Apprentissage (S2A), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, and ANR-16-CE23-0014,FBIMATRIX,Méthodes distribuées et parallèles de Monte-Carlo par chaînes de Markov pour l'Inférence Bayésienne de modèles à factorisation de tenseurs(2016)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, Machine Learning (stat.ML), [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: International audience; Recent studies on diffusion-based sampling methods have shown that Langevin Monte Carlo (LMC) algorithms can be beneficial for non-convex optimization, and rigorous theoretical guarantees have been proven for both asymp-totic and finite-time regimes. Algorithmically, LMC-based algorithms resemble the well-known gradient descent (GD) algorithm, where the GD recursion is perturbed by an additive Gaussian noise whose variance has a particular form. Fractional Langevin Monte Carlo (FLMC) is a recently proposed extension of LMC, where the Gaussian noise is replaced by a heavy-tailed α-stable noise. As opposed to its Gaussian counterpart , these heavy-tailed perturbations can incur large jumps and it has been empirically demonstrated that the choice of α-stable noise can provide several advantages in modern machine learning problems, both in optimization and sampling contexts. However, as opposed to LMC, only asymptotic convergence properties of FLMC have been yet established. In this study, we analyze the non-asymptotic behavior of FLMC for non-convex optimization and prove finite-time bounds for its expected suboptimality. Our results show that the weak-error of FLMC increases faster than LMC, which suggests using smaller step-sizes in FLMC. We finally extend our results to the case where the exact gradients are replaced by stochas-tic gradients and show that similar results hold in this setting as well.
Published: 2019

174. Gaussian random projections for Euclidean membership problems

Author: Pierre-Louis Poirion, Leo Liberti, Ky Khac Vu, RIKEN Research Center, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), and Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)
Subjects: FOS: Computer and information sciences, Johnson-Lindenstrauss lemma, Gaussian, Dimension (graph theory), 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Set (abstract data type), Machine Learning, symbols.namesake, Computer Science - Data Structures and Algorithms, Euclidean geometry, FOS: Mathematics, Discrete Mathematics and Combinatorics, Countable set, Data Structures and Algorithms (cs.DS), Point (geometry), Almost surely, Mathematics - Optimization and Control, Mathematics, Euclidean Distance Geometry, Discrete mathematics, 021103 operations research, Euclidean space, Applied Mathematics, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Optimization and Control (math.OC), 010201 computation theory & mathematics, symbols, clustering
Abstract: International audience; We discuss the application of Gaussian random projections to the fundamental problem of deciding whether a given point in a Euclidean space belongs to a given set. In particular, we consider the two cases, when the target set is either at most countable or of low doubling dimension. We show that, under a number of different assumptions, the feasibility (or infeasibility) of this problem is preserved almost surely when the problem data is projected to a lower dimensional space. We also consider the threshold version of this problem, in which we require that the projected point and the projected set are separated by a certain distance error. As a consequence of these results, we are able to improve the bound of Indyk-Naor on the Nearest Neigbour preserving embeddings. Our results are applicable to any algorithmic setting which needs to solve Euclidean membership problems in a high-dimensional space.
Published: 2019

175. Safe Grid Search with Optimal Complexity

Author: Ndiaye, Eugene, Le, Tam, Fercoq, Olivier, Salmon, Joseph, Takeuchi, Ichiro, Laboratoire Traitement et Communication de l'Information (LTCI), Télécom ParisTech-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), RIKEN Center for Advanced Intelligence Project [Tokyo] (RIKEN AIP), RIKEN - Institute of Physical and Chemical Research [Japon] (RIKEN), Signal, Statistique et Apprentissage (S2A), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Département Images, Données, Signal (IDS), Télécom ParisTech, Institut Montpelliérain Alexander Grothendieck (IMAG), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), and Nagoya Institute of Technology (NIT)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, Machine Learning (stat.ML), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [STAT.OT]Statistics [stat]/Other Statistics [stat.ML], Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: International audience; Popular machine learning estimators involve regularization parameters that can be challenging to tune, and standard strategies rely on grid search for this task. In this paper, we revisit the techniques of approximating the regularization path up to predefined tolerance $\epsilon$ in a unified framework and show that its complexity is $O(1/\sqrt[d]{\epsilon})$ for uniformly convex loss of order $d>0$ and $O(1/\sqrt{\epsilon})$ for Generalized Self-Concordant functions. This framework encompasses least-squares but also logistic regression (a case that as far as we know was not handled as precisely by previous works). We leverage our technique to provide refined bounds on the validation error as well as a practical algorithm for hyperparameter tuning. The later has global convergence guarantee when targeting a prescribed accuracy on the validation set. Last but not least, our approach helps relieving the practitioner from the (often neglected) task of selecting a stopping criterion when optimizing over the training set: our method automatically calibrates it based on the targeted accuracy on the validation set.
Published: 2019

176. A differential game on Wasserstein space. Application to weak approachability with partial monitoring

Author: Vianney Perchet, Marc Quincampoix, Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Criteo AI Lab, Criteo [Paris], Laboratoire de Mathématiques de Bretagne Atlantique (LMBA), and Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Statistics and Probability, FOS: Computer and information sciences, Computer Science::Computer Science and Game Theory, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Computer science, Applied Mathematics, Approachability, Discrete time and continuous time, Computer Science - Computer Science and Game Theory, Optimization and Control (math.OC), Modeling and Simulation, Euclidean geometry, Differential game, Repeated game, FOS: Mathematics, Probability distribution, Applied mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Game theory, Computer Science and Game Theory (cs.GT)
Abstract: International audience; Studying continuous time counterpart of some discrete time dynamics is now a standard and fruitful technique, as some properties hold in both setups. In game theory, this is usually done by considering differential games on Euclidean spaces. This allows to infer properties on the convergence of values of a repeated game, to deal with the various concepts of approachability, etc. In this paper, we introduce a specific but quite abstract differential game defined on the Wasserstein space of probability distributions and we prove the existence of its value. Going back to the discrete time dynamics, we derive results on weak approachability with partial monitoring: we prove that any set satisfying a suitable compatibility condition is either weakly approachable or weakly excludable. We also obtain that the value for differential games with nonanticipative strategies is the same that those defined with a new concept of strategies very suitable to make links with repeated games.
Published: 2019

177. Decomposition of games: some strategic considerations

Author: Abdou, Joseph, Pnevmatikos, Nikolaos, Scarsini, Marco, Venel, Xavier, Venel, Xavier, Modèles Mathématiques et Economiques de la Dynamique, de l'Incertitude et des Interactions - - MME-DII2011 - ANR-11-LABX-0023 - LABX - VALID, DS0806 - Révolution numérique et mutations sociales - Communication et Information dans des Jeux dans des Réseaux - - CIGNE2015 - ANR-15-CE38-0007 - AAPG2015 - VALID, Centre d'économie de la Sorbonne (CES), Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS), Paris School of Economics (PSE), École des Ponts ParisTech (ENPC)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS)-École des hautes études en sciences sociales (EHESS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Laboratoire d'économie mathématique et de microéconomie appliquée (LEMMA), Université Panthéon-Assas (UP2)-Sorbonne Université (SU), Libera Università Internazionale degli Studi Sociali Guido Carli [Roma] (LUISS), Nikos Pnevmatikos’s research was supported by Labex MME-DII. Part of this research wascarried out when he was visiting the Engineering Systems andDesign pillar at Singapore Univer-sity of Technology and Design. Marco Scarsini is a member of GNAMPA-INdAM. Xavier Venelacknowledges the support of the Agence Nationale de la Recherche [ANR CIGNE ANR-15-CE38-0007-01]. This work was partially supported by GAMENET COSTAction CA 16228., ANR-11-LABX-0023,MME-DII,Modèles Mathématiques et Economiques de la Dynamique, de l'Incertitude et des Interactions(2011), and ANR-15-CE38-0007,CIGNE,Communication et Information dans des Jeux dans des Réseaux(2015)
Subjects: FOS: Computer and information sciences, Computer Science::Computer Science and Game Theory, Optimization and Control (math.OC), Computer Science - Computer Science and Game Theory, FOS: Mathematics, ComputingMilieux_PERSONALCOMPUTING, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 91A70, 91A10, [SHS.ECO]Humanities and Social Sciences/Economics and Finance, [SHS.ECO] Humanities and Social Sciences/Economics and Finance, Mathematics - Optimization and Control, Computer Science and Game Theory (cs.GT)
Abstract: Candogan et al. (2011) provide an orthogonal direct-sum decomposition of finite games into potential, harmonic and nonstrategic components. In this paper we study the issue of decomposing games that are strategically equivalent from a game-theoretical point of view, for instance games obtained via transformations such as duplications of strategies or positive affine mappings of of payoffs. We show the need to define classes of decompositions to achieve commutativity of game transformations and decompositions., 43 pages
Published: 2019

178. Mixed Integer Linear Programming for Feature Selection in Support Vector Machine

Author: Martine Labbé, Luisa I. Martínez-Merino, Antonio M. Rodríguez-Chía, Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Departamento de Estadística e Investigación Operativa, Universidad Rey Juan Carlos [Madrid] (URJC), and Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Mathematical optimization, Support vector machine, 0211 other engineering and technologies, Machine Learning (stat.ML), Feature selection, 02 engineering and technology, Machine Learning (cs.LG), Statistics - Machine Learning, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Limit (mathematics), Mathematics - Optimization and Control, Integer programming, Budget constraint, Mathematics, 021103 operations research, Applied Mathematics, Process (computing), Mathematical programming, Construct (python library), [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 90C11, Mathématiques, Hyperplane, Optimization and Control (math.OC), Supervised classification, 020201 artificial intelligence & image processing, Kernel search algorithm
Abstract: This work focuses on support vector machine (SVM)with feature selection. A MILP formulation is proposed for the problem. The choice of suitable features to construct the separating hyperplanes has been modeled in this formulation by including a budget constraint that sets in advance a limit on the number of features to be used in the classification process. We propose both an exact and a heuristic procedure to solve this formulation in an efficient way. Finally, the validation of the model is done by checking it with some well-known data sets and comparing it with classical classification methods., SCOPUS: ar.j, info:eu-repo/semantics/published
Published: 2019

179. Finding the bandit in a graph: Sequential search-and-stop

Author: Perrault, Pierre, Perchet, Vianney, Valko, Michal, Sequential Learning (SEQUEL), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Mathématiques et de Leurs Applications (CMLA), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS), and DeepMind [Paris]
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Optimization and Control (math.OC), FOS: Mathematics, Machine Learning (stat.ML), Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: We consider the problem where an agent wants to find a hidden object that is randomly located in some vertex of a directed acyclic graph (DAG) according to a fixed but possibly unknown distribution. The agent can only examine vertices whose in-neighbors have already been examined. In this paper, we address a learning setting where we allow the agent to stop before having found the object and restart searching on a new independent instance of the same problem. Our goal is to maximize the total number of hidden objects found given a time budget. The agent can thus skip an instance after realizing that it would spend too much time on it. Our contributions are both to the search theory and multi-armed bandits. If the distribution is known, we provide a quasi-optimal and efficient stationary strategy. If the distribution is unknown, we additionally show how to sequentially approximate it and, at the same time, act near-optimally in order to collect as many hidden objects as possible., Comment: in International Conference on Artificial Intelligence and Statistics (AISTATS 2019), April 2019, Naha, Okinawa, Japan
Published: 2019

180. Routing Game on Parallel Networks: the Convergence of Atomic to Nonatomic

Author: Cheng Wan, Paulin Jacquot, TROPICAL (TROPICAL), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Optimisation, Simulation, Risque et Statistiques pour les Marchés de l’Energie (EDF R&D OSIRIS), EDF R&D (EDF R&D), EDF (EDF)-EDF (EDF), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Dynamics of Geometric Networks (DYOGENE), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), IEEE, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)
Subjects: FOS: Computer and information sciences, TheoryofComputation_MISCELLANEOUS, 0209 industrial biotechnology, Mathematical optimization, Computer Science::Computer Science and Game Theory, Computer science, Infinitesimal, Mathematics::General Topology, 02 engineering and technology, 01 natural sciences, Set (abstract data type), 010104 statistics & probability, symbols.namesake, 020901 industrial engineering & automation, Computer Science - Computer Science and Game Theory, Convergence (routing), FOS: Mathematics, 0101 mathematics, Mathematics - Optimization and Control, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], TheoryofComputation_GENERAL, Optimization and Control (math.OC), Nash equilibrium, symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Routing (electronic design automation), Computer Science and Game Theory (cs.GT)
Abstract: We consider an instance of a nonatomic routing game. We assume that the network is parallel, that is, constituted of only two nodes, an origin and a destination. We consider infinitesimal players that have a symmetric network cost, but are heterogeneous through their set of feasible strategies and their individual utilities. We show that if an atomic routing game instance is correctly defined to approximate the nonatomic instance, then an atomic Nash Equilibrium will approximate the nonatomic Wardrop Equilibrium. We give explicit bounds on the distance between the equilibria according to the parameters of the atomic instance. This approximation gives a method to compute the Wardrop equilibrium at an arbitrary precision., 20 pages, one figure, submitted to CDC 2018
Published: 2018

181. Impulsive Control for G-AIMD Dynamics with Relaxed and Hard Constraints

Author: Alexei B. Piunovskiy, Konstantin Avrachenkov, Yi Zhang, Network Engineering and Operations (NEO ), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Mathematical Sciences [Liverpool], University of Liverpool, and Huawei Research
Subjects: FOS: Computer and information sciences, 0209 industrial biotechnology, Mathematical optimization, business.product_category, Computer science, Control (management), 02 engineering and technology, Computer Science - Networking and Internet Architecture, Power control problems, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 020901 industrial engineering & automation, Electric vehicle, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Additive increase/multiplicative decrease, Mathematics - Optimization and Control, Networking and Internet Architecture (cs.NI), Heuristic, Whittle index, 020206 networking & telecommunications, Internet congestion control, Electric vehicle charging, Constraint (information theory), Smart grid, Optimization and Control (math.OC), Impulsive control problem, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], business, Power control
Abstract: Motivated by various applications from Internet congestion control to power control in smart grids and electric vehicle charging, we study Generalized Additive Increase Multiplicative Decrease (G-AIMD) dynamics under impulsive control in continuous time with the time average alpha-fairness criterion. We first show that the control under relaxed constraints can be described by a threshold. Then, we propose a Whittle-type index heuristic for the hard constraint problem. We prove that in the homogeneous case the index policy is asymptotically optimal when the number of users is large., Comment: 8 pages
Published: 2018

182. Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes

Author: Pillaud-Vivien, Loucas, Rudi, Alessandro, Bach, Francis, Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Machine Learning (stat.ML), Mathematics - Statistics Theory, Statistics Theory (math.ST), Machine Learning (cs.LG), Stochastic gradient descent, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Optimization and Control (math.OC), Statistics - Machine Learning, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract: International audience; We consider stochastic gradient descent (SGD) for least-squares regression with potentially several passes over the data. While several passes have been widely reported to perform practically better in terms of predictive performance on unseen data, the existing theoretical analysis of SGD suggests that a single pass is statistically optimal. While this is true for low-dimensional easy problems, we show that for hard problems, multiple passes lead to statistically optimal predictions while single pass does not; we also show that in these hard models, the optimal number of passes over the data increases with sample size. In order to define the notion of hardness and show that our predictive performances are optimal, we consider potentially infinite-dimensional models and notions typically associated to kernel methods, namely, the decay of eigenvalues of the covariance matrix of the features and the complexity of the optimal predictor as measured through the covariance matrix. We illustrate our results on synthetic experiments with non-linear kernel methods and on a classical benchmark with a linear model.
Published: 2018

183. Budgeted Multi-Objective Optimization with a Focus on the Central Part of the Pareto Front - Extended Version

Author: Gaudrie, David, Riche, Rodolphe Le, Picheny, Victor, Enaux, Benoit, Herbert, Vincent, École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), Institut Mines-Télécom [Paris] (IMT), PSA Peugeot - Citroën (PSA), PSA Peugeot Citroën (PSA), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne (UCA)-Centre National de la Recherche Scientifique (CNRS), Institut Henri Fayol (FAYOL-ENSMSE), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Département Génie mathématique et industriel (FAYOL-ENSMSE), Ecole Nationale Supérieure des Mines de St Etienne-Institut Henri Fayol, Centre National de la Recherche Scientifique (CNRS), Institut National de la Recherche Agronomique (INRA), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Institut Henri Fayol, and Breuil, Florent
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Bayesian Optimization, Multi-Objective Optimization, Machine Learning (stat.ML), [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, [STAT.ML] Statistics [stat]/Machine Learning [stat.ML], Machine Learning (cs.LG), [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, [INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation, Mathematics - Optimization and Control, Computer Experiments
Abstract: Optimizing nonlinear systems involving expensive computer experiments with regard to conflicting objectives is a common challenge. When the number of experiments is severely restricted and/or when the number of objectives increases, uncovering the whole set of Pareto optimal solutions is out of reach, even for surrogate-based approaches: the proposed solutions are sub-optimal or do not cover the front well. As non-compromising optimal solutions have usually little point in applications, this work restricts the search to solutions that are close to the Pareto front center. The article starts by characterizing this center, which is defined for any type of front. Next, a Bayesian multi-objective optimization method for directing the search towards it is proposed. Targeting a subset of the Pareto front allows an improved optimality of the solutions and a better coverage of this zone, which is our main concern. A criterion for detecting convergence to the center is described. If the criterion is triggered, a widened central part of the Pareto front is targeted such that sufficiently accurate convergence to it is forecasted within the remaining budget. Numerical experiments show how the resulting algorithm, C-EHI, better locates the central part of the Pareto front when compared to state-of-the-art Bayesian algorithms., Submission pre-print, extended version
Published: 2018

184. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile

Author: Mertikopoulos, Panayotis, Lecouat, Bruno, Zenati, Houssam, Foo, Chuan-Sheng, Chandrasekhar, Vijay, Piliouras, Georgios, Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Institute for Infocomm Research - I²R [Singapore], Agency for science, technology and research [Singapore] (A*STAR), Nanyang Technological University [Singapour], Singapore University of Technology and Design (SUTD), and ANR-16-CE33-0004,ORACLESS,Stratégies adaptatives d'allocation des ressources dans les réseaux sans fil dynamiques(2016)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Optimization and Control (math.OC), Computer Science - Computer Science and Game Theory, Statistics - Machine Learning, FOS: Mathematics, Machine Learning (stat.ML), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [STAT.OT]Statistics [stat]/Other Statistics [stat.ML], Mathematics - Optimization and Control, Machine Learning (cs.LG), Computer Science and Game Theory (cs.GT)
Abstract: Owing to their connection with generative adversarial networks (GANs), saddle-point problems have recently attracted considerable interest in machine learning and beyond. By necessity, most theoretical guarantees revolve around convex-concave (or even linear) problems; however, making theoretical inroads towards efficient GAN training depends crucially on moving beyond this classic framework. To make piecemeal progress along these lines, we analyze the behavior of mirror descent (MD) in a class of non-monotone problems whose solutions coincide with those of a naturally associated variational inequality - a property which we call coherence. We first show that ordinary, "vanilla" MD converges under a strict version of this condition, but not otherwise; in particular, it may fail to converge even in bilinear models with a unique solution. We then show that this deficiency is mitigated by optimism: by taking an "extra-gradient" step, optimistic mirror descent (OMD) converges in all coherent problems. Our analysis generalizes and extends the results of Daskalakis et al. (2018) for optimistic gradient descent (OGD) in bilinear problems, and makes concrete headway for establishing convergence beyond convex-concave games. We also provide stochastic analogues of these results, and we validate our analysis by numerical experiments in a wide array of GAN models (including Gaussian mixture models, as well as the CelebA and CIFAR-10 datasets)., 26 pages, 14 figures
Published: 2018

185. Distributed Estimation of State and Parameters in Multi-Agent Cooperative Load Manipulation

Author: Antonio Petitti, Antonio Franchi, Alessandro Rizzo, Équipe Robotique et InteractionS (LAAS-RIS), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Istituto di studi sui sistemi intelligenti per l'automazione (ISSIA), Consiglio Nazionale delle Ricerche (CNR), Politecnico di Torino = Polytechnic of Turin (Polito), ANR-17-CE33-0007,MUROPHEN,Controle de systèmes multi-robots pour l'observation de phenomenes dynamiques(2017), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and National Research Council of Italy | Consiglio Nazionale delle Ricerche (CNR)
Subjects: FOS: Computer and information sciences, 0209 industrial biotechnology, Control and Optimization, cooperative manipulation, Computer Networks and Communications, Computer science, robotic networks, Monte Carlo method, Systems and Control (eess.SY), 02 engineering and technology, Kinematics, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Computer Science - Robotics, 020901 industrial engineering & automation, Control theory, Robustness (computer science), [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO], Computer Science - Multiagent Systems, Observability, Mathematics - Optimization and Control, Estimation theory, Rigid body, distributed estimation, Nonlinear system, Optimization and Control (math.OC), Control and Systems Engineering, Signal Processing, Computer Science - Systems and Control, Graph (abstract data type), 020201 artificial intelligence & image processing, Robotics (cs.RO), Multiagent Systems (cs.MA)
Abstract: We present two distributed methods for the estimation of the kinematic parameters, the dynamic parameters, and the kinematic state of an unknown planar body manipulated by a decentralized multi-agent system. The proposed approaches rely on the rigid body kinematics and dynamics, on nonlinear observation theory, and on consensus algorithms. The only three requirements are that each agent can exert a 2D wrench on the load, it can measure the velocity of its contact point, and that the communication graph is connected. Both theoretical nonlinear observability analysis and convergence proofs are provided. The first method assumes constant parameters while the second one can deal with time-varying parameters and can be applied in parallel to any task-oriented control law. For the cases in which a control law is not provided, we propose a distributed and safe control strategy satisfying the observability condition. The effectiveness and robustness of the estimation strategy is showcased by means of realistic MonteCarlo simulations., Accepted for publication to the IEEE Transactions on Control of Network Systems
Published: 2018

186. Riemannian game dynamics

Author: Panayotis Mertikopoulos, William H. Sandholm, Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), and University of Wisconsin-Madison
Subjects: FOS: Computer and information sciences, Hessian matrix, 0209 industrial biotechnology, Economics and Econometrics, Computer Science::Computer Science and Game Theory, Population, Evolutionary game theory, Motion (geometry), Primary 91A22, 92D25, secondary 91A26, 37N40, Dynamical Systems (math.DS), 02 engineering and technology, Projection (linear algebra), symbols.namesake, 020901 industrial engineering & automation, Computer Science - Computer Science and Game Theory, 0502 economics and business, Replicator equation, FOS: Mathematics, Applied mathematics, Reinforcement learning, Mathematics - Dynamical Systems, 050207 economics, education, Mathematics - Optimization and Control, Mathematics, education.field_of_study, 05 social sciences, Optimization and Control (math.OC), Metric (mathematics), symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Computer Science and Game Theory (cs.GT)
Abstract: We study a class of evolutionary game dynamics defined by balancing a gain determined by the game's payoffs against a cost of motion that captures the difficulty with which the population moves between states. Costs of motion are represented by a Riemannian metric, i.e., a state-dependent inner product on the set of population states. The replicator dynamics and the (Euclidean) projection dynamics are the archetypal examples of the class we study. Like these representative dynamics, all Riemannian game dynamics satisfy certain basic desiderata, including positive correlation and global convergence in potential games. Moreover, when the underlying Riemannian metric satisfies a Hessian integrability condition, the resulting dynamics preserve many further properties of the replicator and projection dynamics. We examine the close connections between Hessian game dynamics and reinforcement learning in normal form games, extending and elucidating a well-known link between the replicator dynamics and exponential reinforcement learning., Comment: 47 pages, 12 figures; added figures and further simplified the derivation of the dynamics
Published: 2018

187. Constant Step Size Stochastic Gradient Descent for Probabilistic Modeling

Author: Babichev, Dmitry, Bach, Francis, Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'informatique de l'école normale supérieure (LIENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), European Project: 642685,H2020 Pilier Excellent Science,H2020-MSCA-ITN-2014,MacSeNet(2015), European Project: 724063,ERC-2016-COG,SEQUOIA(2017), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, Machine Learning (stat.ML), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: Stochastic gradient methods enable learning probabilistic models from large amounts of data. While large step-sizes (learning rates) have shown to be best for least-squares (e.g., Gaussian noise) once combined with parameter averaging, these are not leading to convergent algorithms in general. In this paper, we consider generalized linear models, that is, conditional models based on exponential families. We propose averaging moment parameters instead of natural parameters for constant-step-size stochastic gradient descent. For finite-dimensional models, we show that this can sometimes (and surprisingly) lead to better predictions than the best linear model. For infinite-dimensional models, we show that it always converges to optimal predictions, while averaging natural parameters never does. We illustrate our findings with simulations on synthetic data and classical benchmarks with many observations., Published in Proc. UAI 2018, was accepted as oral presentation Camera ready
Published: 2018

188. On Representer Theorems and Convex Regularization

Author: Vincent Duval, Yohann De Castro, Antonin Chambolle, Claire Boyer, Pierre Weiss, Frédéric de Gournay, Département de Mathématiques et Applications - ENS Paris ( DMA ), École normale supérieure - Paris ( ENS Paris ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire de Probabilités, Statistique et Modélisation ( LPSM UMR 8001 ), Université Paris Diderot - Paris 7 ( UPD7 ) -Sorbonne Université-Centre National de la Recherche Scientifique ( CNRS ), Centre de Mathématiques Appliquées - Ecole Polytechnique ( CMAP ), École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire de Mathématiques d'Orsay ( LMO ), Université Paris-Saclay-Centre National de la Recherche Scientifique ( CNRS ), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales ( MOKAPLAN ), CEntre de REcherches en MAthématiques de la DEcision ( CEREMADE ), Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ) -Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ) -Inria de Paris, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ), Institut de Mathématiques de Toulouse UMR5219 ( IMT ), Université Toulouse 1 Capitole ( UT1 ) -Université Toulouse - Jean Jaurès ( UT2J ) -Université Toulouse III - Paul Sabatier ( UPS ), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-PRES Université de Toulouse-Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Centre National de la Recherche Scientifique ( CNRS ), Institut des Technologies Avancées en sciences du Vivant ( ITAV ), Centre National de la Recherche Scientifique ( CNRS ), Département de Mathématiques et Applications - ENS Paris (DMA), École normale supérieure - Paris (ENS Paris)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Probabilités, Statistique et Modélisation (LPSM (UMR_8001)), Université Paris Diderot - Paris 7 (UPD7)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Institut des Technologies Avancées en sciences du Vivant (ITAV), Université Toulouse III - Paul Sabatier (UT3), The work of Antonin Chambolle was partially supported by a grant of the Simons Foundation., Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Laboratoire de Probabilités, Statistiques et Modélisations (LPSM (UMR_8001)), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Université de Toulouse (UT)-Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), and École normale supérieure - Paris (ENS Paris)
Subjects: FOS: Computer and information sciences, Inverse problems, [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], Class (set theory), Computer Science - Information Theory, 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, [ MATH.MATH-IT ] Mathematics [math]/Information Theory [math.IT], 01 natural sciences, Theoretical Computer Science, FOS: Mathematics, Applied mathematics, 0101 mathematics, Extreme point, Mathematics - Optimization and Control, Mathematics, Representer theorem, Total variation, 021103 operations research, Vector space, Information Theory (cs.IT), Regular polygon, [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT], Extension (predicate logic), Inverse problem, Optimization and Control (math.OC), Convex regularization, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Convex function, Software
Abstract: International audience; We establish a general principle which states that regularizing an inverse problem with a convex function yields solutions which are convex combinations of a small number of atoms. These atoms are identified with the extreme points and elements of the extreme rays of the regularizer level sets. An extension to a broader class of quasi-convex regularizers is also discussed. As a side result, we characterize the minimizers of the total gradient variation, which was still an unresolved problem.
Published: 2018

189. Frank-Wolfe with Subsampling Oracle

Author: Kerdreux, Thomas, Pedregosa, Fabian, d'Aspremont, Alexandre, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Modelling brain structure, function and variability based on high-field MRI data (PARIETAL), Service NEUROSPIN (NEUROSPIN), Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Statistical Machine Learning and Parsimony (SIERRA), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'informatique de l'école normale supérieure (LIENS), d'Aspremont, Alexandre, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Service NEUROSPIN (NEUROSPIN), Direction de Recherche Fondamentale (CEA) (DRF (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris
Subjects: FOS: Computer and information sciences, [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Machine Learning (stat.ML), [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [STAT.ML] Statistics [stat]/Machine Learning [stat.ML], Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Computer Science - Learning, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Optimization and Control (math.OC), FOS: Mathematics, Mathematics - Optimization and Control
Abstract: International audience; We analyze two novel randomized variants of the Frank-Wolfe (FW) or conditional gradient algorithm. While classical FW algorithms require solving a linear minimization problem over the domain at each iteration, the proposed method only requires to solve a linear minimization problem over a small \emph{subset} of the original domain. The first algorithm that we propose is a randomized variant of the original FW algorithm and achieves a $\mathcal{O}(1/t)$ sublinear convergence rate as in the deterministic counterpart. The second algorithm is a randomized variant of the Away-step FW algorithm, and again as its deterministic counterpart, reaches linear (i.e., exponential) convergence rate making it the first provably convergent randomized variant of Away-step FW. In both cases, while subsampling reduces the convergence rate by a constant factor, the linear minimization step can be a fraction of the cost of that of the deterministic versions, especially when the data is streamed. We illustrate computational gains of the algorithms on regression problems, involving both $\ell_1$ and latent group lasso penalties.
Published: 2018

190. Surprising strategies obtained by stochastic optimization in partially observable games

Author: Marie-Liesse Cauwet, Olivier Teytaud, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), TAckling the Underspecified (TAU), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Sequence, Theoretical computer science, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], 010102 general mathematics, ComputingMilieux_PERSONALCOMPUTING, Context (language use), 010501 environmental sciences, 01 natural sciences, Evolutionary computation, Optimization and Control (math.OC), Computer Science - Computer Science and Game Theory, Complete information, FOS: Mathematics, Spite, Benchmark (computing), Stochastic optimization, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 0101 mathematics, Mathematics - Optimization and Control, Computer Science and Game Theory (cs.GT), 0105 earth and related environmental sciences, Parametric statistics
Abstract: International audience; This paper studies the optimization of strategies in the context of possibly randomized two players zero-sum games with incomplete information. We compare 5 algorithms for tuning the parameters of strategies over a benchmark of 12 games. A first evolutionary approach consists in designing a highly randomized opponent (called naive opponent) and optimizing the parametric strategy against it; a second one is optimizing iteratively the strategy, i.e. constructing a sequence of strategies starting from the naive one. 2 versions of coevolutions, real and approximate, are also tested as well as a seed method. The coevolution methods were performing well, but results were not stable from one game to another. In spite of its simplicity, the seed method, which can be seen as an extremal version of coevolution, works even when nothing else works. Incidentally, these methods brought out some unexpected strategies for some games, such as Batawaf or the game of War, which seem, at first view, purely random games without any structured actions possible for the players or Guess Who, where a dichotomy between the characters seems to be the most reasonable strategy. All source codes of games are written in Matlab/Octave and are freely available for download.
Published: 2018

191. Online shortest paths with confidence intervals for routing in a time varying random network

Author: Stéphane Chrétien, Christophe Guyeux, National Physical Laboratory [Teddington] (NPL), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), Université de Franche-Comté (UFC)-Centre National de la Recherche Scientifique (CNRS)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Technologie de Belfort-Montbeliard (UTBM), Laboratoire de Mathématiques de Besançon (UMR 6623) (LMB), Université de Bourgogne (UB)-Université de Franche-Comté (UFC), Université de Franche-Comté (UFC), and Université Bourgogne Franche-Comté [COMUE] (UBFC)
Subjects: FOS: Computer and information sciences, Mathematical optimization, Computer science, Population, 02 engineering and technology, [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], [INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing, [SPI]Engineering Sciences [physics], [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 0502 economics and business, 11. Sustainability, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Data Structures and Algorithms (cs.DS), education, Intelligent transportation system, Mathematics - Optimization and Control, Random graph, 050210 logistics & transportation, education.field_of_study, Stochastic process, [SPI.PLASMA]Engineering Sciences [physics]/Plasmas, 05 social sciences, Approximation algorithm, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Stochastic gradient descent, Optimization and Control (math.OC), [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA], Shortest path problem, 020201 artificial intelligence & image processing, [INFO.INFO-ET]Computer Science [cs]/Emerging Technologies [cs.ET], Routing (electronic design automation), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: International audience; The increase in the world's population and rising standards of living is leading to an ever-increasing number of vehicles on the roads, and with it ever-increasing difficulties in traffic management. This traffic management in transport networks can be clearly optimized by using information and communication technologies referred as Intelligent Transport Systems (ITS). This management problem is usually reformulated as finding the shortest path in a time varying random graph. In this article, an online shortest path computation using stochastic gradient descent is proposed. This routing algorithm for ITS traffic management is based on the online Frank-Wolfe approach. Our improvement enables to find a confidence interval for the shortest path, by using the stochastic gradient algorithm for approximate Bayesian inference. The theory required to understand our approach is provided, as well as the implementation details.
Published: 2018

192. Efficient Global Optimization using Deep Gaussian Processes

Author: Ali Hebbal, Ei-Ghazali Taibi, Mathieu Balesdent, Loïc Brevault, Nouredine Melab, DTIS, ONERA, Université Paris Saclay (COmUE) [Palaiseau], ONERA-Université Paris Saclay (COmUE), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Optimisation de grande taille et calcul large échelle (BONUS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Mathematical optimization, Computer science, 010501 environmental sciences, Deep Gaussian Processes, 01 natural sciences, Machine Learning (cs.LG), symbols.namesake, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Kriging, FOS: Mathematics, Neural and Evolutionary Computing (cs.NE), 0101 mathematics, Non-stationary Kriging, Mathematics - Optimization and Control, Gaussian process, Global optimization, 0105 earth and related environmental sciences, Computer Science - Neural and Evolutionary Computing, Covariance, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Efficient Global Optimization, 010101 applied mathematics, Optimization and Control (math.OC), symbols
Abstract: Efficient Global Optimization (EGO) is widely used for the optimization of computationally expensive black-box functions. It uses a surrogate modeling technique based on Gaussian Processes (Kriging). However, due to the use of a stationary covariance, Kriging is not well suited for approximating non stationary functions. This paper explores the integration of Deep Gaussian processes (DGP) in EGO framework to deal with the non-stationary issues and investigates the induced challenges and opportunities. Numerical experimentations are performed on analytical problems to highlight the different aspects of DGP and EGO., Comment: 12 pages, 11 Figures, 2 Tables, presented to the IEEE Congress on Evolutionary Computation (IEEE CEC 2018)
Published: 2018

193. Averaging Stochastic Gradient Descent on Riemannian Manifolds

Author: Tripuraneni, Nilesh, Flammarion, Nicolas, Bach, Francis, Jordan, Michael I., Department of Electrical Engineering and Computer Sciences (Berkeley EECS), Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)
Subjects: FOS: Computer and information sciences, Computer Science - Learning, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, Optimization and Control (math.OC), FOS: Mathematics, Machine Learning (stat.ML), Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: We consider the minimization of a function defined on a Riemannian manifold $\mathcal{M}$ accessible only through unbiased estimates of its gradients. We develop a geometric framework to transform a sequence of slowly converging iterates generated from stochastic gradient descent (SGD) on $\mathcal{M}$ to an averaged iterate sequence with a robust and fast $O(1/n)$ convergence rate. We then present an application of our framework to geodesically-strongly-convex (and possibly Euclidean non-convex) problems. Finally, we demonstrate how these ideas apply to the case of streaming $k$-PCA, where we show how to accelerate the slow rate of the randomized power method (without requiring knowledge of the eigengap) into a robust algorithm achieving the optimal rate of convergence., Comment: COLT 2018
Published: 2018

194. Asymptotically Optimal Pilot Allocation Over Markovian Fading Channels

Author: Apostolos Destounis, Maialen Larranaga, Mohamad Assaad, Georgios S. Paschos, Laboratoire des signaux et systèmes (L2S), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), CentraleSupélec, Huawei Technologies France [Boulogne-Billancour], and Huawei Technologies | European Union through the Horizon 2020 Project ONE5G (ICT-760809)
Subjects: FOS: Computer and information sciences, Mathematical optimization, Whittle's index, Computer science, Computer Science - Information Theory, Throughput, 02 engineering and technology, Library and Information Sciences, 01 natural sciences, asymptotic optimal, pilot allocation, 010104 statistics & probability, Base station, symbols.namesake, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Telecommunications link, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Wireless, Fading, 0101 mathematics, Mathematics - Optimization and Control, Restless bandits, ComputingMilieux_MISCELLANEOUS, Computer Science::Information Theory, business.industry, Wireless network, Information Theory (cs.IT), 020206 networking & telecommunications, Computer Science Applications, CSI acquisition, Optimization and Control (math.OC), Channel state information, Lagrangian relaxation, [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT], symbols, Partially Observable Markov Decision Pro, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], business, Information Systems, Communication channel
Abstract: International audience; We investigate a pilot allocation problem in wireless networks over Markovian fading channels. In wireless systems, the channel state information (CSI) is collected at the base station, in particular, this paper considers a pilot-aided channel estimation method (TDD mode). Typically, there are less available pilots than users, hence at each slot the scheduler needs to decide an allocation of pilots to users with the goal of maximizing the long-term average throughput. There is an inherent tradeoff in how the limited pilots are used: assign a pilot to a user with up-to-date CSI and good channel condition for exploitation, or assign a pilot to a user with outdated CSI for exploration. As we show, the arising pilot allocation problem is a restless bandit problem and thus its optimal solution is out of reach. In this paper, we propose an approximation based on the Lagrangian relaxation method, which provides a low-complexity Whittle index policy. We prove this policy to be asymptotically optimal in the many users regime (when the number of users in the system and the available pilots for channel sensing grow large). We evaluate the performance of Whittle's index policy in various scenarios and illustrate its remarkably good performance for small number of users, where it is not guaranteed to be optimal.
Published: 2018

195. A Distributed Flexible Delay-tolerant Proximal Gradient Algorithm

Author: Konstantin Mishchenko, Jérôme Malick, Franck Iutzeler, King Abdullah University of Science and Technology (KAUST), Données, Apprentissage et Optimisation (DAO), Laboratoire Jean Kuntzmann (LJK ), Institut polytechnique de Grenoble - Grenoble Institute of Technology [2007-2019] (Grenoble INP [2007-2019])-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology [2007-2019] (Grenoble INP [2007-2019])-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Laboratoire Jean Kuntzmann (LJK), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), and ANR-19-P3IA-0003,MIAI,MIAI @ Grenoble Alpes(2019)
Subjects: FOS: Computer and information sciences, 021103 operations research, 0211 other engineering and technologies, Machine Learning (stat.ML), 010103 numerical & computational mathematics, 02 engineering and technology, Function (mathematics), 01 natural sciences, Theoretical Computer Science, Asynchronous algorithms, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Optimization and Control (math.OC), Convex optimization, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 0101 mathematics, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Mathematics - Optimization and Control, Algorithm, Computer Science::Databases, Software, Mathematics
Abstract: We develop and analyze an asynchronous algorithm for distributed convex optimization when the objective writes a sum of smooth functions, local to each worker, and a non-smooth function. Unlike many existing methods, our distributed algorithm is adjustable to various levels of communication cost, delays, machines computational power, and functions smoothness. A unique feature is that the stepsizes do not depend on communication delays nor number of machines, which is highly desirable for scalability. We prove that the algorithm converges linearly in the strongly convex case, and provide guarantees of convergence for the non-strongly convex case. The obtained rates are the same as the vanilla proximal gradient algorithm over some introduced epoch sequence that subsumes the delays of the system. We provide numerical results on large-scale machine learning problems to demonstrate the merits of the proposed method., Comment: to appear in SIAM Journal on Optimization
Published: 2018

196. Accélération Nonlinéaire des réseaux de neurones convolutionnels

Author: Scieur, Damien, Oyallon, Edouard, d'Aspremont, Alexandre, Bach, Francis, Statistical Machine Learning and Parsimony ( SIERRA ), Département d'informatique de l'École normale supérieure ( DI-ENS ), École normale supérieure - Paris ( ENS Paris ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre National de la Recherche Scientifique ( CNRS ) -École normale supérieure - Paris ( ENS Paris ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Centre National de la Recherche Scientifique ( CNRS ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria de Paris, Institut National de Recherche en Informatique et en Automatique ( Inria ), PSL Research University ( PSL ), Centre de vision numérique ( CVN ), CentraleSupélec, Organ Modeling through Extraction, Representation and Understanding of Medical Image Content ( GALEN ), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Ecole Centrale Paris, Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL), Centre de vision numérique (CVN), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec, Organ Modeling through Extraction, Representation and Understanding of Medical Image Content (GALEN), Ecole Centrale Paris-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Ecole Centrale Paris
Subjects: FOS: Computer and information sciences, [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], Computer Science - Learning, Statistics - Machine Learning, Optimization and Control (math.OC), FOS: Mathematics, Machine Learning (stat.ML), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: International audience; The Regularized Nonlinear Acceleration (RNA) algorithm is an acceleration method capable of improving the rate of convergence of many optimization schemes such as gradient descend, SAGA or SVRG. Until now, its analysis is limited to convex problems, but empirical observations shows that RNA may be extended to wider settings. In this paper, we investigate further the benefits of RNA when applied to neural networks, in particular for the task of image recognition on CIFAR10 and ImageNet. With very few modifications of exiting frameworks, RNA improves slightly the optimization process of CNNs, after training.
Published: 2018

197. Modélisation du VRP avec dépendance temporelle à travers l'Open Data

Author: Lombard, A., Simon Tamayo, Fontane, F., Centre de Robotique (CAOR), MINES ParisTech - École nationale supérieure des mines de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), and Université Paris sciences et lettres (PSL)
Subjects: FOS: Computer and information sciences, open data, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], time-dependency modeling, Computer Science - Robotics, [SPI.GCIV.IT]Engineering Sciences [physics]/Civil Engineering/Infrastructures de transport, Optimization and Control (math.OC), GRASP, FOS: Mathematics, vehicle routing problem, Optimisation, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Robotics (cs.RO), Mathematics - Optimization and Control
Abstract: International audience; This paper presents an open data approach to model and solve the vehicle routing problem with time-dependent travel times (TDVRP). The proposed model is based on a multi-layer matrix composed of travel times, replacing the traditional distance matrix. Online cartography services are queried in order to build this matrix. Travel times are obtained for every step in the time discretization. Thus, the model integrates the fact that the travel time between two points is modified during the time horizon. This model is applied to a medium-sized problem in the urban area of Paris using an enhanced Greedy Randomized Adaptive Search Procedure (GRASP). This work intends to build on the current state of the art by proposing a straightforward and open-access method to model and solve the VRP with traffic variability.
Published: 2018

198. Whittle Index Policy for Crawling Ephemeral Content

Author: Konstantin Avrachenkov, Vivek S. Borkar, Network Engineering and Operations (NEO ), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Electrical Engineering [IIT-Bombay] (EE-IIT), Indian Institute of Technology Kanpur (IIT Kanpur), MALENA, Models for the performance analysis and the control of networks (MAESTRO), Cefipra 5100-IT1, Inria Sophia Antipolis, and INRIA
Subjects: FOS: Computer and information sciences, 0209 industrial biotechnology, Mathematical optimization, Theoretical computer science, Control and Optimization, Computer Networks and Communications, Computer science, Stochastic modelling, InformationSystems_INFORMATIONSTORAGEANDRETRIEVAL, 02 engineering and technology, Systems and Control (eess.SY), Crawling, Scheduling (computing), Computer Science - Information Retrieval, Search engine, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 020901 industrial engineering & automation, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], 0202 electrical engineering, electronic engineering, information engineering, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Mathematics - Optimization and Control, Restless bandits, Crawler, Ephemeral Content, business.industry, Ephemeral key, Web crawling, Whittle index, 020206 networking & telecommunications, Optimal control, Dynamic programming, Search Engine, Control and Systems Engineering, Optimization and Control (math.OC), [INFO.INFO-IR]Computer Science [cs]/Information Retrieval [cs.IR], Signal Processing, Computer Science - Systems and Control, Artificial intelligence, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, Web crawler, business, Information Retrieval (cs.IR), Curse of dimensionality
Abstract: International audience; We consider the task of scheduling a crawler to retrieve from several sites their ephemeral content. This is content, such as news or posts at social network groups, for which a user typically loses interest after some days or hours. Thus development of a timely crawling policy for ephemeral information sources is very important. We first formulate this problem as an optimal control problem with average reward. The reward can be measured in terms of the number of clicks or relevant search requests. The problem in its exact formulation suffers from the curse of dimensionality and quickly becomes intractable even with moderate number of information sources. Fortunately, this problem admits a Whittle index, a celebrated heuristics which leads to problem decomposition and to a very simple and efficient crawling policy. We derive the Whittle index for a simple deterministic model and provide its theoretical justification. We also outline an extension to a fully stochastic model.
Published: 2018

199. Online Leader Selection for Improved Collective Tracking and Formation Maintenance

Author: Antonio Franchi, Paolo Robuffo Giordano, Équipe Robotique et InteractionS ( LAAS-RIS ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Visual servoing in robotics, computer vision, and augmented reality ( Lagadic ), Inria Sophia Antipolis - Méditerranée ( CRISAM ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique ( Inria ) -SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE ( IRISA_D5 ), Institut de Recherche en Informatique et Systèmes Aléatoires ( IRISA ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Institut National des Sciences Appliquées - Rennes ( INSA Rennes ) -Université de Bretagne Sud ( UBS ) -École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -CentraleSupélec-Centre National de la Recherche Scientifique ( CNRS ) -IMT Atlantique Bretagne-Pays de la Loire ( IMT Atlantique ) -Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Institut National des Sciences Appliquées - Rennes ( INSA Rennes ) -Université de Bretagne Sud ( UBS ) -École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -CentraleSupélec-Centre National de la Recherche Scientifique ( CNRS ) -IMT Atlantique Bretagne-Pays de la Loire ( IMT Atlantique ) -Institut de Recherche en Informatique et Systèmes Aléatoires ( IRISA ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Institut National des Sciences Appliquées - Rennes ( INSA Rennes ) -Université de Bretagne Sud ( UBS ) -École normale supérieure - Rennes ( ENS Rennes ) -CentraleSupélec-Centre National de la Recherche Scientifique ( CNRS ) -IMT Atlantique Bretagne-Pays de la Loire ( IMT Atlantique ), Équipe Robotique et InteractionS (LAAS-RIS), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Sensor-based and interactive robotics (RAINBOW), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique)
Subjects: FOS: Computer and information sciences, 0209 industrial biotechnology, Control and Optimization, Decentralized control, [ INFO ] Computer Science [cs], Computer Networks and Communications, Computer science, Distributed computing, 02 engineering and technology, Systems and Control (eess.SY), Maintenance engineering, Distributed agent Systems, 020901 industrial engineering & automation, 0202 electrical engineering, electronic engineering, information engineering, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO], Computer Science - Multiagent Systems, [INFO]Computer Science [cs], Mathematics - Optimization and Control, Multi-agent system, Multi-agent systems, [ INFO.INFO-RB ] Computer Science [cs]/Robotics [cs.RO], Directed graph, Decentralised system, Control and Systems Engineering, Distributed algorithm, Optimization and Control (math.OC), Control system, Signal Processing, Metric (mathematics), Identity (object-oriented programming), Computer Science - Systems and Control, Distributed algorithms, 020201 artificial intelligence & image processing, Mobile agents, Multiagent Systems (cs.MA)
Abstract: The goal of this paper is to propose an extension of the popular leader-follower framework for multiagent collective tracking and formation maintenance in the presence of a time-varying leader. In particular, the leader is persistently selected online in order to optimize the tracking performance of an exogenous collective velocity command while also maintaining a desired formation via a (possibly time-varying) communication-graph topology. The effects of a change in the leader identity are theoretically analyzed and exploited for defining a suitable error metric that is able to capture the tracking performance of the multiagent group. Both the group performance and the metric design are found to depend upon the spectral properties of a special directed graph induced by the identity of the chosen leader. By exploiting these results, as well as distributed estimation techniques, we are then able to detail a fully decentralized adaptive strategy that is able to periodically select online the best leader among the neighbors of the current leader. Numerical simulations show that the application of the proposed technique results in an improvement of the overall performance of the group behavior with regard to other possible strategies.
Published: 2018

200. Variations on Memetic Algorithms for Graph Coloring Problems

Author: Alexandre Gondran, Laurent Moalic, Laboratoire Systèmes et Transports (IRTES - SET), Université de Technologie de Belfort-Montbeliard (UTBM)-Institut de Recherche sur les Transports, l'Energie et la Société - IRTES, Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA)), ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien (MAIAA), Ecole Nationale de l'Aviation Civile (ENAC), and ANR-12-JS02-0009,ATOMIC,Optimisation du trafic aérien via des méthodes mixtes (discretes-continus)(2012)
Subjects: FOS: Computer and information sciences, Control and Optimization, Theoretical computer science, Computer Science - Artificial Intelligence, Computer Networks and Communications, Computer science, Population, 0211 other engineering and technologies, Evolutionary algorithm, 02 engineering and technology, Management Science and Operations Research, Artificial Intelligence, evolutionary, 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, memetic, tabu search, Local search (optimization), Graph coloring, Neural and Evolutionary Computing (cs.NE), education, Mathematics - Optimization and Control, Metaheuristic, coloring, education.field_of_study, 021103 operations research, business.industry, Computer Science - Neural and Evolutionary Computing, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], graph, Tabu search, Artificial Intelligence (cs.AI), Optimization and Control (math.OC), Memetic algorithm, Combinatorial optimization, 020201 artificial intelligence & image processing, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], business, Software, Information Systems
Abstract: Graph vertex coloring with a given number of colors is a well-known and much-studied NP-complete problem.The most effective methods to solve this problem are proved to be hybrid algorithms such as memetic algorithms or quantum annealing. Those hybrid algorithms use a powerful local search inside a population-based algorithm.This paper presents a new memetic algorithm based on one of the most effective algorithms: the Hybrid Evolutionary Algorithm HEA from Galinier and Hao (1999).The proposed algorithm, denoted HEAD - for HEA in Duet - works with a population of only two individuals.Moreover, a new way of managing diversity is brought by HEAD.These two main differences greatly improve the results, both in terms of solution quality and computational time.HEAD has produced several good results for the popular DIMACS benchmark graphs, such as 222-colorings for \textless{}dsjc1000.9\textgreater{}, 81-colorings for \textless{}flat1000\_76\_0\textgreater{} and even 47-colorings for \textless{}dsjc500.5\textgreater{} and 82-colorings for \textless{}dsjc1000.5\textgreater{}., Comment: 11 pages, 8 figures, 3 tables, 2 algorithms
Published: 2018

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Database

311 results on '"Mathematics - Optimization and Control"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources