Descriptor: "Mathematics - Optimization and Control" / Publisher: hal ccsd / Topic: fos: computer and information sciences and machine learning (stat.ml) - Searchworks@Jio Institute Digital Library Search Results

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

Start Over Descriptor "Mathematics - Optimization and Control" Topic fos: computer and information sciences Topic machine learning (stat.ml) Publisher hal ccsd

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

1. Implicit Differentiation for Hyperparameter Tuning the Weighted Graphical Lasso

Author: Pouliquen, Can, Gonçalves, Paulo, Massias, Mathurin, Vayer, Titouan, Optimisation, Connaissances pHysiques, Algorithmes et Modèles (OCKHAM), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Droit des Affaires et Nouvelles Technologies (DANTE), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), ANR-19-CHIA-0009,AllegroAssai,Algorithmes, Approximations, Parcimonie et Plongements pour l'IA(2019), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), 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 de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)
Subjects: FOS: Computer and information sciences, Optimization, Computer Science - Machine Learning, Implicit differentiation, Machine Learning (stat.ML), Hyperparameter Selection, Machine Learning (cs.LG), Graphical Lasso, Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, [INFO]Computer Science [cs], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract: International audience; We provide a framework and algorithm for tuning the hyperparameters of the Graphical Lasso via a bilevel optimizationproblem solved with a first-order method. In particular, we derive the Jacobian of the Graphical Lasso solution with respect to itsregularization hyperparameters.
Published: 2023

2. PENDANTSS: PEnalized Norm-ratios Disentangling Additive Noise, Trend and Sparse Spikes

Author: Paul Zheng, Emilie Chouzenoux, Laurent Duval, Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH), 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-Université Paris-Saclay-CentraleSupélec-Université Paris-Saclay, IFP Energies nouvelles (IFPEN), European Project: ERC-2019-STG-850925,MAJORIS(2020), Zheng, Paul, and ERC-2019-STG-850925 - MAJORIS - ERC-2019-STG-850925 - INCOMING
Subjects: Signal Processing (eess.SP), FOS: Computer and information sciences, Computer Science - Machine Learning, non-convex optimization, Blind deconvolution, forward-backward splitting, FOS: Physical sciences, Machine Learning (stat.ML), Machine Learning (cs.LG), trend estimation, Statistics - Machine Learning, alternating minimization, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Electrical and Electronic Engineering, Electrical Engineering and Systems Science - Signal Processing, Mathematics - Optimization and Control, [SPI.SIGNAL] Engineering Sciences [physics]/Signal and Image processing, Applied Mathematics, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Optimization and Control (math.OC), Physics - Data Analysis, Statistics and Probability, Signal Processing, source separation, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Data Analysis, Statistics and Probability (physics.data-an), sparse signal
Abstract: International audience; Denoising, detrending, deconvolution: usual restoration tasks, traditionally decoupled. Coupled formulations entail complex ill-posed inverse problems. We propose PENDANTSS for joint trend removal and blind deconvolution of sparse peak-like signals. It blends a parsimonious prior with the hypothesis that smooth trend and noise can somewhat be separated by low-pass filtering. We combine the generalized quasi-norm ratio SOOT/SPOQ sparse penalties $\ell_p/\ell_q$ with the BEADS ternary assisted source separation algorithm. This results in a both convergent and efficient tool, with a novel Trust-Region block alternating variable metric forward-backward approach. It outperforms comparable methods, when applied to typically peaked analytical chemistry signals. Reproducible code is provided.
Published: 2023

3. Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning

Author: Dieuleveut, Aymeric, Fort, Gersende, Moulines, Eric, Wai, Hoi-To, Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Toulouse UMR5219 (IMT), 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), The Chinese University of Hong Kong [Hong Kong], Fondation Simone et Cino Del Duca Institut de France (author G. Fort), HKRGC Project 23203520 (author H-T. Wai), and Hi!Paris FLAG project (authors A. Dieuleveut and E. Moulines)
Subjects: FOS: Computer and information sciences, Stochastic approximation, Machine Learning (stat.ML), TD-learning, Convergence Analysis, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Compressed Stochastic Gradient, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Statistics - Machine Learning, Optimization and Control (math.OC), [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Expectation Maximization
Abstract: Stochastic Approximation (SA) is a classical algorithm that has had since the early days a huge impact on signal processing, and nowadays on machine learning, due to the necessity to deal with a large amount of data observed with uncertainties. An exemplar special case of SA pertains to the popular stochastic (sub)gradient algorithm which is the working horse behind many important applications. A lesser-known fact is that the SA scheme also extends to non-stochastic-gradient algorithms such as compressed stochastic gradient, stochastic expectation-maximization, and a number of reinforcement learning algorithms. The aim of this article is to overview and introduce the non-stochastic-gradient perspectives of SA to the signal processing and machine learning audiences through presenting a design guideline of SA algorithms backed by theories. Our central theme is to propose a general framework that unifies existing theories of SA, including its non-asymptotic and asymptotic convergence results, and demonstrate their applications on popular non-stochastic-gradient algorithms. We build our analysis framework based on classes of Lyapunov functions that satisfy a variety of mild conditions. We draw connections between non-stochastic-gradient algorithms and scenarios when the Lyapunov function is smooth, convex, or strongly convex. Using the said framework, we illustrate the convergence properties of the non-stochastic-gradient algorithms using concrete examples. Extensions to the emerging variance reduction techniques for improved sample complexity will also be discussed., Comment: Accepted for publication at IEEE Transactions on Signal Processing; 31 pages, 7 pages of supplementary materials
Published: 2023

4. Optimistic Dynamic Regret Bounds

Author: Haddouche, Maxime, Guedj, Benjamin, Wintenberger, Olivier, University College of London [London] (UCL), Department of Computer science [University College of London] (UCL-CS), Institut National de Recherche en Informatique et en Automatique (Inria), Inria Lille - Nord Europe, The Alan Turing Institute, The Inria London Programme (Inria-London), University College of London [London] (UCL)-University College of London [London] (UCL)-Institut National de Recherche en Informatique et en Automatique (Inria), MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), and Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)
Subjects: FOS: Computer and information sciences, Computer Science - Machine 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: Online Learning (OL) algorithms have originally been developed to guarantee good performances when comparing their output to the best fixed strategy. The question of performance with respect to dynamic strategies remains an active research topic. We develop in this work dynamic adaptations of classical OL algorithms based on the use of experts' advice and the notion of optimism. We also propose a constructivist method to generate those advices and eventually provide both theoretical and experimental guarantees for our procedures.
Published: 2023

5. Margin theory for the scenario-based approach to robust optimization in high dimension

Author: Lauer, Fabien, Machine Learning and Computational Biology (ABC), Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Optimization and Control (math.OC), Statistics - Machine Learning, Randomized algorithms, FOS: Mathematics, Machine Learning (stat.ML), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Robust optimization, Mathematics - Optimization and Control, Scenario approach, Statistical learning
Abstract: This paper deals with the scenario approach to robust optimization. This relies on a random sampling of the possibly infinite number of constraints induced by uncertainties in the parameters of an optimization problem. Solving the resulting random program yields a solution for which the quality is measured in terms of the probability of violating the constraints for a random value of the uncertainties, typically unseen before. Another central issue is the determination of the sample complexity, i.e., the number of random constraints (or scenarios) that one must consider in order to guarantee a certain level of reliability. In this paper, we introduce the notion of margin to improve upon standard results in this field. In particular, using tools from statistical learning theory, we show that the sample complexity of a class of random programs does not explicitly depend on the number of variables. In addition, within the considered class, that includes polynomial constraints among others, this result holds for both convex and nonconvex instances with the same level of guarantees. We also derive a posteriori bounds on the probability of violation and sketch a regularization approach that could be used to improve the reliability of computed solutions on the basis of these bounds.
Published: 2023

6. Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data

Author: Bars, Batiste Le, Bellet, Aurélien, Tommasi, Marc, Lavoie, Erick, Kermarrec, Anne-Marie, Machine Learning in Information Networks (MAGNET), 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), Ecole Polytechnique Fédérale de Lausanne (EPFL), and ANR-20-CE23-0015,PRIDE,Apprentissage automatique décentralisé et préservant la vie privée(2020)
Subjects: Computer Science::Machine Learning, FOS: Computer and information sciences, Computer Science - Machine Learning, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [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: One of the key challenges in decentralized and federated learning is to design algorithms that efficiently deal with highly heterogeneous data distributions across agents. In this paper, we revisit the analysis of the popular Decentralized Stochastic Gradient Descent algorithm (D-SGD) under data heterogeneity. We exhibit the key role played by a new quantity, called neighborhood heterogeneity, on the convergence rate of D-SGD. By coupling the communication topology and the heterogeneity, our analysis sheds light on the poorly understood interplay between these two concepts. We then argue that neighborhood heterogeneity provides a natural criterion to learn data-dependent topologies that reduce (and can even eliminate) the otherwise detrimental effect of data heterogeneity on the convergence time of D-SGD. For the important case of classification with label skew, we formulate the problem of learning such a good topology as a tractable optimization problem that we solve with a Frank-Wolfe algorithm. As illustrated over a set of simulated and real-world experiments, our approach provides a principled way to design a sparse topology that balances the convergence speed and the per-iteration communication costs of D-SGD under data heterogeneity.
Published: 2022

7. Efficient Gradient Flows in Sliced-Wasserstein Space

Author: Bonet, Clément, Courty, Nicolas, Septier, François, Drumetz, Lucas, Observation de l’environnement par imagerie complexe (OBELIX), SIGNAL, IMAGE ET LANGAGE (IRISA-D6), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), 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), 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 Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Laboratoire de Mathématiques de Bretagne Atlantique (LMBA), Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Centre National de la Recherche Scientifique (CNRS), Equipe Observations Signal & Environnement (Lab-STICC_OSE), Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT), Département Mathematical and Electrical Engineering (IMT Atlantique - MEE), and IMT Atlantique (IMT Atlantique)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, [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, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], Machine Learning (cs.LG)
Abstract: Minimizing functionals in the space of probability distributions can be done with Wasserstein gradient flows. To solve them numerically, a possible approach is to rely on the Jordan-Kinderlehrer-Otto (JKO) scheme which is analogous to the proximal scheme in Euclidean spaces. However, it requires solving a nested optimization problem at each iteration, and is known for its computational challenges, especially in high dimension. To alleviate it, very recent works propose to approximate the JKO scheme leveraging Brenier's theorem, and using gradients of Input Convex Neural Networks to parameterize the density (JKO-ICNN). However, this method comes with a high computational cost and stability issues. Instead, this work proposes to use gradient flows in the space of probability measures endowed with the sliced-Wasserstein (SW) distance. We argue that this method is more flexible than JKO-ICNN, since SW enjoys a closed-form differentiable approximation. Thus, the density at each step can be parameterized by any generative model which alleviates the computational burden and makes it tractable in higher dimensions., Comment: Published in Transactions on Machine Learning Research (November 2022)
Published: 2022

8. Information Theory with Kernel Methods

Author: Francis Bach, 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), ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), and European Project: 724063,ERC-2016-COG,SEQUOIA(2017)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Information Theory (cs.IT), Computer Science - Information Theory, Machine Learning (stat.ML), Library and Information Sciences, Machine Learning (cs.LG), Computer Science Applications, [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, [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT], FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Information Systems
Abstract: We consider the analysis of probability distributions through their associated covariance operators from reproducing kernel Hilbert spaces. We show that the von Neumann entropy and relative entropy of these operators are intimately related to the usual notions of Shannon entropy and relative entropy, and share many of their properties. They come together with efficient estimation algorithms from various oracles on the probability distributions. We also consider product spaces and show that for tensor product kernels, we can define notions of mutual information and joint entropies, which can then characterize independence perfectly, but only partially conditional independence. We finally show how these new notions of relative entropy lead to new upper-bounds on log partition functions, that can be used together with convex optimization within variational inference methods, providing a new family of probabilistic inference methods.
Published: 2022

9. Sum-of-Squares Relaxations for Information Theory and Variational Inference

Author: 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), ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), and European Project: 724063,ERC-2016-COG,SEQUOIA(2017)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Information Theory (cs.IT), Computer Science - Information Theory, Machine Learning (stat.ML), Machine Learning (cs.LG), [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, [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT], FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract: We consider extensions of the Shannon relative entropy, referred to as f-divergences. Three classical related computational problems are typically associated with these divergences: (a) estimation from moments, (b) computing normalizing integrals, and (c) variational inference in probabilistic models. These problems are related to one another through convex duality, and for all them, there are many applications throughout data science, and we aim for computationally tractable approximation algorithms that preserve properties of the original problem such as potential convexity or monotonicity. In order to achieve this, we derive a sequence of convex relaxations for computing these divergences from non-centered covariance matrices associated with a given feature vector: starting from the typically non-tractable optimal lower-bound, we consider an additional relaxation based on "sums-of-squares", which is is now computable in polynomial time as a semidefinite program, as well as further computationally more efficient relaxations based on spectral information divergences from quantum information theory. For all of the tasks above, beyond proposing new relaxations, we derive tractable algorithms based on augmented Lagrangians and first-order methods, and we present illustrations on multivariate trigonometric polynomials and functions on the Boolean hypercube.
Published: 2022

10. Benchmarking learned non-Cartesian k-space trajectories and reconstruction networks

Author: Giliyar Radhakrishna, Chaithya, Ciuciu, Philippe, 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), Modelling brain structure, function and variability based on high-field MRI data (PARIETAL), 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), Modèles et inférence pour les données de Neuroimagerie (MIND), IFR49 - Neurospin - CEA, ISMRM, and European Project: 800945,NUMERICS
Subjects: Signal Processing (eess.SP), FOS: Computer and information sciences, Computer Science - Machine Learning, acquisition, Machine Learning (stat.ML), Machine Learning (cs.LG), joint optimization, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, Optimization and Control (math.OC), FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Electrical Engineering and Systems Science - Signal Processing, Mathematics - Optimization and Control, non-Cartesian trajectories, MRI
Abstract: International audience; We benchmark the current existing methods to jointly learn non-Cartesian k-space trajectory and reconstruction: PILOT, BJORK, and compare them with those obtained from the recently developed generalized hybrid learning (HybLearn) framework. We present the advantages of using projected gradient descent to enforce MR scanner hardware constraints as compared to using added penalties in the cost function. Further, we use the novel HybLearn scheme to jointly learn and compare our results through a retrospective study on fastMRI validation dataset.
Published: 2022

11. Efficient Approximations of the Fisher Matrix in Neural Networks using Kronecker Product Singular Value Decomposition

Author: Koroko, Abdoulaye, Anciaux-Sedrakian, Ani, Gharbia, Ibtihel, Garès, Valérie, Haddou, Mounir, Tran, Quang Huy, IFP Energies nouvelles (IFPEN), Institut de Recherche Mathématique de Rennes (IRMAR), INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-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)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES), Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES)-AGROCAMPUS OUEST, Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-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)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), 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)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest
Subjects: FOS: Computer and information sciences, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, Computer Science - Neural and Evolutionary Computing, Machine Learning (stat.ML), Neural and Evolutionary Computing (cs.NE), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], Mathematics - Optimization and Control
Abstract: Several studies have shown the ability of natural gradient descent to minimize the objective function more efficiently than ordinary gradient descent based methods. However, the bottleneck of this approach for training deep neural networks lies in the prohibitive cost of solving a large dense linear system corresponding to the Fisher Information Matrix (FIM) at each iteration. This has motivated various approximations of either the exact FIM or the empirical one. The most sophisticated of these is KFAC, which involves a Kronecker-factored block diagonal approximation of the FIM. With only a slight additional cost, a few improvements of KFAC from the standpoint of accuracy are proposed. The common feature of the four novel methods is that they rely on a direct minimization problem, the solution of which can be computed via the Kronecker product singular value decomposition technique. Experimental results on the three standard deep auto-encoder benchmarks showed that they provide more accurate approximations to the FIM. Furthermore, they outperform KFAC and state-of-the-art first-order methods in terms of optimization speed.
Published: 2022

12. Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy, and Multi-fidelity Feedback

Author: Wang, Junxiong, Basu, Debabrota, Trummer, Immanuel, Cornell University [New York], Scool (Scool), 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, Multifidelity optimization, Black-box Optimization, Noisy Feedback, Stochastic optimization, Machine Learning (stat.ML), General Medicine, Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Delayed Feedback, [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, FOS: Mathematics, Bandit algorithms, Bandit algorithm Tree search Concentration inequality Stochastic optimization, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Bandit Based Monte-Carlo Tree-Search, Mathematics - Optimization and Control, Monte-Carlo Tree-Search
Abstract: In black-box optimization problems, we aim to maximize an unknown objective function, where the function is only accessible through feedbacks of an evaluation or simulation oracle. In real-life, the feedbacks of such oracles are often noisy and available after some unknown delay that may depend on the computation time of the oracle. Additionally, if the exact evaluations are expensive but coarse approximations are available at a lower cost, the feedbacks can have multi-fidelity. In order to address this problem, we propose a generic extension of hierarchical optimistic tree search (HOO), called ProCrastinated Tree Search (PCTS), that flexibly accommodates a delay and noise-tolerant bandit algorithm. We provide a generic proof technique to quantify regret of PCTS under delayed, noisy, and multi-fidelity feedbacks. Specifically, we derive regret bounds of PCTS enabled with delayed-UCB1 (DUCB1) and delayed-UCB-V (DUCBV) algorithms. Given a horizon $T$, PCTS retains the regret bound of non-delayed HOO for expected delay of $O(\log T)$ and worsens by $O(T^{\frac{1-\alpha}{d+2}})$ for expected delays of $O(T^{1-\alpha})$ for $\alpha \in (0,1]$. We experimentally validate on multiple synthetic functions and hyperparameter tuning problems that PCTS outperforms the state-of-the-art black-box optimization methods for feedbacks with different noise levels, delays, and fidelity.
Published: 2022

13. An end-to-end data-driven optimisation framework for constrained trajectories

Author: Florent Dewez, Benjamin Guedj, Arthur Talpaert, Vincent Vandewalle, MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), University College of London [London] (UCL), Department of Computer science [University College of London] (UCL-CS), Inria-CWI (Inria-CWI), Centrum Wiskunde & Informatica (CWI)-Institut National de Recherche en Informatique et en Automatique (Inria), The Inria London Programme (Inria-London), University College of London [London] (UCL)-University College of London [London] (UCL)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut National de Recherche en Informatique et en Automatique (Inria), Inria Lille - Nord Europe, The Alan Turing Institute, Université de Lille, Laboratoire Paul Painlevé - UMR 8524 (LPP), and Computer science department [University College London] (UCL-CS)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [STAT.AP]Statistics [stat]/Applications [stat.AP], Constrained optimisation Contents, Machine Learning (stat.ML), Statistics - Applications, Functional data, Machine Learning (cs.LG), [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Optimization and Control (math.OC), FOS: Mathematics, Applications (stat.AP), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Statistical modelling, Mathematics - Optimization and Control
Abstract: Many real-world problems require to optimise trajectories under constraints. Classical approaches are based on optimal control methods but require an exact knowledge of the underlying dynamics, which could be challenging or even out of reach. In this paper, we leverage data-driven approaches to design a new end-to-end framework which is dynamics-free for optimised and realistic trajectories. We first decompose the trajectories on function basis, trading the initial infinite dimension problem on a multivariate functional space for a parameter optimisation problem. A maximum \emph{a posteriori} approach which incorporates information from data is used to obtain a new optimisation problem which is regularised. The penalised term focuses the search on a region centered on data and includes estimated linear constraints in the problem. We apply our data-driven approach to two settings in aeronautics and sailing routes optimisation, yielding commanding results. The developed approach has been implemented in the Python library PyRotor., Comment: 28 pages
Published: 2022

14. Implicit differentiation for fast hyperparameter selection in non-smooth convex learning

Author: Bertrand, Quentin, Klopfenstein, Quentin, Massias, Mathurin, Blondel, Mathieu, Vaiter, Samuel, Gramfort, Alexandre, Salmon, Joseph, Bertrand, Quentin, Apprentissage automatique et optimisation coopératifs. - - CAMELOT2020 - ANR-20-CHIA-0001 - PNIA - VALID, APPEL À PROJETS GÉNÉRIQUE 2018 - Méthodes variationnelles pour les signaux sur graphe - - GraVa2018 - ANR-18-CE40-0005 - AAPG2018 - VALID, Intelligence Artificielle et Neurosciences - - BrAIN2020 - ANR-20-CHIA-0016 - PNIA - VALID, Signal processing and Learning Applied to Brain data - SLAB - - H20202016-09-01 - 2021-08-31 - 676943 - VALID, 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), Institut de Mathématiques de Bourgogne [Dijon] (IMB), Université de Bourgogne (UB)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), Dipartimento di Informatica, Bioingegneria, Robotica e Ingegneria dei Sistemi [Genova] (DIBRIS), Università degli studi di Genova = University of Genoa (UniGe), Réseaux dynamiques : approche structurelle et temporelle (DANTE), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Google Research [Paris], Institut Montpelliérain Alexander Grothendieck (IMAG), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Financial support of the European Research Council (grant SLING 819789)., ANR-20-CHIA-0001,CAMELOT,Apprentissage automatique et optimisation coopératifs.(2020), ANR-18-CE40-0005,GraVa,Méthodes variationnelles pour les signaux sur graphe(2018), ANR-20-CHIA-0016,BrAIN,Intelligence Artificielle et Neurosciences(2020), European Project: 676943,H2020,SLAB(2016), 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, Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Bourgogne (UB), Universita degli studi di Genova, Brain team [Paris], Research at Google, Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Université de Bourgogne (UB)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), and Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)
Subjects: FOS: Computer and information sciences, bilevel optimization, Computer Science - Machine Learning, hyperparameter selec- tion, Machine Learning (stat.ML), [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], generalized linear models, Machine Learning (cs.LG), Convex optimization, Statistics - Machine Learning, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], hyperparameter optimization, Lasso, Mathematics - Optimization and Control, [MATH.MATH-ST] Mathematics [math]/Statistics [math.ST]
Abstract: International audience; Finding the optimal hyperparameters of a model can be cast as a bilevel optimization problem, typically solved using zero-order techniques. In this work we study first-order methods when the inner optimization problem is convex but non-smooth. We show that the forward-mode differentiation of proximal gradient descent and proximal coordinate descent yield sequences of Jacobians converging toward the exact Jacobian. Using implicit differentiation, we show it is possible to leverage the non-smoothness of the inner problem to speed up the computation. Finally, we provide a bound on the error made on the hypergradient when the inner optimization problem is solved approximately. Results on regression and classification problems reveal computational benefits for hyperparameter optimization, especially when multiple hyperparameters are required.
Published: 2022

15. TREGO: a Trust-Region Framework for Efficient Global Optimization

Author: Youssef Diouane, Victor Picheny, Rodolophe Le Riche, Alexandre Scotto Di Perrotolo, Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO), secondmind, 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), Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE), Centre National de la Recherche Scientifique (CNRS), 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
Subjects: FOS: Computer and information sciences, Control and Optimization, Applied Mathematics, [INFO.INFO-CE]Computer Science [cs]/Computational Engineering, Finance, and Science [cs.CE], Gaussian processes, Machine Learning (stat.ML), Management Science and Operations Research, nonlinear optimization, Computer Science Applications, [SPI.MECA.GEME]Engineering Sciences [physics]/Mechanics [physics.med-ph]/Mechanical engineering [physics.class-ph], trust-region, Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, Business, Management and Accounting (miscellaneous), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Bayesian optimization
Abstract: International audience; Efficient Global Optimization (EGO) is the canonical form of Bayesian optimization that has been successfully applied to solve global optimization of expensive-to-evaluate black-box problems. However, EGO struggles to scale with dimension, and offers limited theoretical guarantees. In this work, we propose and analyze a trust-region-like EGO method (TREGO). TREGO alternates between regular EGO steps and local steps within a trust region. By following a classical scheme for the trust region (based on a sufficient decrease condition), we demonstrate that our algorithm enjoys strong global convergence properties, while departing from EGO only for a subset of optimization steps. Using extensive numerical experiments based on the well-known COCO benchmark, we first analyze the sensitivity of TREGO to its own parameters, then show that the resulting algorithm is consistently outperforming EGO and getting competitive with other state-of-the-art global optimization methods. The method is available both in the R package DiceOptim 1 and python library trieste 2 .
Published: 2022

16. Unbalanced Optimal Transport through Non-negative Penalized Linear Regression

Author: Chapel, Laetitia, Flamary, Rémi, Wu, Haoran, Févotte, Cédric, Gasso, Gilles, Université de Bretagne Sud (UBS), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), 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), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), École polytechnique (X), Signal et Communications (IRIT-SC), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-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)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Centre National de la Recherche Scientifique (CNRS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA), ANR-17-CE23-0012,OATMIL,Apprentissage statistique avec transport optimal(2017), ANR-18-EURE-0006,E4C,Energy for Climate Interdisciplinary Instute(2018), ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: CoG-6681839,ERC FACTORY, 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), 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)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), and Normandie Université (NU)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, machine learning, optimal transport, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, Machine Learning (stat.ML), out-of-distribution samples, regularization path, Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: This paper addresses the problem of Unbalanced Optimal Transport (UOT) in which the marginal conditions are relaxed (using weighted penalties in lieu of equality) and no additional regularization is enforced on the OT plan. In this context, we show that the corresponding optimization problem can be reformulated as a non-negative penalized linear regression problem. This reformulation allows us to propose novel algorithms inspired from inverse problems and nonnegative matrix factorization. In particular, we consider majorization-minimization which leads in our setting to efficient multiplicative updates for a variety of penalties. Furthermore, we derive for the first time an efficient algorithm to compute the regularization path of UOT with quadratic penalties. The proposed algorithm provides a continuity of piece-wise linear OT plans converging to the solution of balanced OT (corresponding to infinite penalty weights). We perform several numerical experiments on simulated and real data illustrating the new algorithms, and provide a detailed discussion about more sophisticated optimization tools that can further be used to solve OT problems thanks to our reformulation., Laetitia Chapel and R\'emi Flamary have equal contribution
Published: 2021

17. Indexed Minimum Empirical Divergence for Unimodal Bandits

Author: Saber, Hassan, Ménard, Pierre, Maillard, Odalric-Ambrym, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS), Scool (Scool), 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), Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS), Otto-von-Guericke University [Magdeburg] (OVGU), ANR-16-CE40-0002,BADASS,BANDITS MANCHOTS POUR SIGNAUX NON-STATIONNAIRES ET STRUCTURES(2016), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), and Otto-von-Guericke-Universität Magdeburg = Otto-von-Guericke University [Magdeburg] (OVGU)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Artificial Intelligence (cs.AI), Optimization and Control (math.OC), Computer Science - Artificial Intelligence, Statistics - Machine Learning, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], 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 consider a multi-armed bandit problem specified by a set of one-dimensional family exponential distributions endowed with a unimodal structure. We introduce IMED-UB, a algorithm that optimally exploits the unimodal-structure, by adapting to this setting the Indexed Minimum Empirical Divergence (IMED) algorithm introduced by Honda and Takemura [2015]. Owing to our proof technique, we are able to provide a concise finite-time analysis of IMED-UB algorithm. Numerical experiments show that IMED-UB competes with the state-of-the-art algorithms., NeurIPS 2021 - International Conference on Neural Information Processing Systems, Dec 2021, Virtual-only Conference, United States. arXiv admin note: substantial text overlap with arXiv:2006.16569, arXiv:2007.03224
Published: 2021

18. Subspace Detours Meet Gromov-Wasserstein

Author: Clément Bonet, Titouan Vayer, Nicolas Courty, François Septier, Lucas Drumetz, Université de Bretagne Sud (UBS), Laboratoire de Mathématiques de Bretagne Atlantique (LMBA), Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), 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), Equipe Observations Signal & Environnement (Lab-STICC_OSE), Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT), Département Mathematical and Electrical Engineering (IMT Atlantique - MEE), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), École normale supérieure de Lyon (ENS de Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Dynamic Networks : Temporal and Structural Capture Approach (DANTE), 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 de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Observation de l’environnement par imagerie complexe (OBELIX), SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5), 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), 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), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique (IMT Atlantique), IMT Atlantique (IMT Atlantique), ANR-16-IDEX-0005,IDEXLYON,IDEXLYON(2016), École normale supérieure - Lyon (ENS Lyon), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Institut Rhône-Alpin des systèmes complexes (IXXI), Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Université Grenoble Alpes (UGA)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon, 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), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and ANR-11-LABX-0020,LEBESGUE,Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation(2011)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Industrial engineering. Management engineering, Machine Learning (stat.ML), 010103 numerical & computational mathematics, T55.4-60.8, 01 natural sciences, Machine Learning (cs.LG), Theoretical Computer Science, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Knothe-Rosenblatt, FOS: Mathematics, Gromov-Wasserstein, subspace detours, 0101 mathematics, [STAT.CO]Statistics [stat]/Computation [stat.CO], Mathematics - Optimization and Control, Gromov–Wasserstein, Knothe–Rosenblatt, Numerical Analysis, [STAT.AP]Statistics [stat]/Applications [stat.AP], 010102 general mathematics, QA75.5-76.95, optimal transport, Computational Mathematics, Computational Theory and Mathematics, Optimization and Control (math.OC), Electronic computers. Computer science, [STAT.ME]Statistics [stat]/Methodology [stat.ME], [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing
Abstract: International audience; In the context of optimal transport methods, the subspace detour approach was recently presented by Muzellec and Cuturi (2019). It consists in building a nearly optimal transport plan in the measures space from an optimal transport plan in a wisely chosen subspace, onto which the original measures are projected. The contribution of this paper is to extend this category of methods to the Gromov-Wasserstein problem, which is a particular type of transport distance involving the inner geometry of the compared distributions. After deriving the associated formalism and properties, we also discuss a specific cost for which we can show connections with the Knothe-Rosenblatt rearrangement. We finally give an experimental illustration on a shape matching problem.
Published: 2021

19. Federated Multi-Task Learning under a Mixture of Distributions

Author: Marfoq, Othmane, Neglia, Giovanni, Bellet, Aurélien, Kameni, Laetitia, Vidal, Richard, Université Côte d'Azur (UCA), Accenture Labs [Sophia Antipolis], 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), Machine Learning in Information Networks (MAGNET), 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), ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019), ANR-16-CE23-0016,PAMELA,Apprentissage automatique décentralisé et personnalisé sous contraintes(2016), and ANR-20-CE23-0015,PRIDE,Apprentissage automatique décentralisé et préservant la vie privée(2020)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Computer Science - Artificial Intelligence, Machine Learning (stat.ML), Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Artificial Intelligence (cs.AI), [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], 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: The increasing size of data generated by smartphones and IoT devices motivated the development of Federated Learning (FL), a framework for on-device collaborative training of machine learning models. First efforts in FL focused on learning a single global model with good average performance across clients, but the global model may be arbitrarily bad for a given client, due to the inherent heterogeneity of local data distributions. Federated multi-task learning (MTL) approaches can learn personalized models by formulating an opportune penalized optimization problem. The penalization term can capture complex relations among personalized models, but eschews clear statistical assumptions about local data distributions. In this work, we propose to study federated MTL under the flexible assumption that each local data distribution is a mixture of unknown underlying distributions. This assumption encompasses most of the existing personalized FL approaches and leads to federated EM-like algorithms for both client-server and fully decentralized settings. Moreover, it provides a principled way to serve personalized models to clients not seen at training time. The algorithms' convergence is analyzed through a novel federated surrogate optimization framework, which can be of general interest. Experimental results on FL benchmarks show that our approach provides models with higher accuracy and fairness than state-of-the-art methods., Comment: 77 pages, NeurIPS 2021
Published: 2021

20. A comparison of mixed-variables Bayesian optimization approaches

Author: Jhouben Cuesta Ramirez, Rodolphe Le Riche, Olivier Roustant, Guillaume Perrin, Cédric Durantin, Alain Glière, Commissariat à l'énergie atomique et aux énergies alternatives - Laboratoire d'Electronique et de Technologie de l'Information (CEA-LETI), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), Institut Mines-Télécom [Paris] (IMT), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), 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 des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA), Département Composants et Systèmes (COSYS), Université Gustave Eiffel, Centre d'Études de Limeil-Valenton (CEA-DAM), Direction des Applications Militaires (DAM), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Institut Henri Fayol, and Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Applied Mathematics, Machine Learning (stat.ML), Statistics - Applications, Statistics - Computation, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Computer Science Applications, Machine Learning (cs.LG), Machine Learning, Optimization and Control (math.OC), Statistics - Machine Learning, Modeling and Simulation, Applications, Computation, FOS: Mathematics, Applications (stat.AP), Engineering (miscellaneous), Mathematics - Optimization and Control, Computation (stat.CO)
Abstract: Most real optimization problems are defined over a mixed search space where the variables are both discrete and continuous. In engineering applications, the objective function is typically calculated with a numerically costly black-box simulation.General mixed and costly optimization problems are therefore of a great practical interest, yet their resolution remains in a large part an open scientific question. In this article, costly mixed problems are approached through Gaussian processes where the discrete variables are relaxed into continuous latent variables. The continuous space is more easily harvested by classical Bayesian optimization techniques than a mixed space would. Discrete variables are recovered either subsequently to the continuous optimization, or simultaneously with an additional continuous-discrete compatibility constraint that is handled with augmented Lagrangians. Several possible implementations of such Bayesian mixed optimizers are compared. In particular, the reformulation of the problem with continuous latent variables is put in competition with searches working directly in the mixed space. Among the algorithms involving latent variables and an augmented Lagrangian, a particular attention is devoted to the Lagrange multipliers for which a local and a global estimation techniques are studied. The comparisons are based on the repeated optimization of three analytical functions and a beam design problem., Accepted for publication in Advanced Modeling and Simulation in Engineering Sciences, march 2022
Published: 2021

21. Factored couplings in multi-marginal optimal transport via difference of convex programming

Author: Tran, Huy Quang, Janati, Hicham, Redko, Ievgen, Flamary, Rémi, Courty, Nicolas, Environment observation with complex imagery (OBELIX), Université de Bretagne Sud (UBS)-SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), 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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-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 Hubert Curien (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-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)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-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)-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), Laboratoire Hubert Curien [Saint Etienne] (LHC), Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS)-Institut d'Optique Graduate School (IOGS), SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5), and Institut d'Optique Graduate School (IOGS)-Université Jean Monnet [Saint-Étienne] (UJM)-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], 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: Optimal transport (OT) theory underlies many emerging machine learning (ML) methods nowadays solving a wide range of tasks such as generative modeling, transfer learning and information retrieval. These latter works, however, usually build upon a traditional OT setup with two distributions, while leaving a more general multi-marginal OT formulation somewhat unexplored. In this paper, we study the multi-marginal OT (MMOT) problem and unify several popular OT methods under its umbrella by promoting structural information on the coupling. We show that incorporating such structural information into MMOT results in an instance of a different of convex (DC) programming problem allowing us to solve it numerically. Despite high computational cost of the latter procedure, the solutions provided by DC optimization are usually as qualitative as those obtained using currently employed optimization schemes., Comment: Revision of notation and proofs
Published: 2021

22. Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Data

Author: Antoine Godichon-Baggioni, Nicklas Werge, Olivier Wintenberger, Laboratoire de Probabilités, Statistiques et Modélisations (LPSM (UMR_8001)), and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)
Subjects: FOS: Computer and information sciences, Statistics and Probability, Computer Science - Machine Learning, Machine Learning (stat.ML), stochastic optimization, streaming data, Machine Learning (cs.LG), machine learning, [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, large-scale, stochastic approximation, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract: Motivated by the high-frequency data streams continuously generated, real-time learning is becoming increasingly important. These data streams should be processed sequentially with the property that the stream may change over time. In this streaming setting, we propose techniques for minimizing a convex objective through unbiased estimates of its gradients, commonly referred to as stochastic approximation problems. Our methods rely on stochastic approximation algorithms due to their computationally advantage as they only use the previous iterate as a parameter estimate. The reasoning includes iterate averaging that guarantees optimal statistical efficiency under classical conditions. Our non-asymptotic analysis shows accelerated convergence by selecting the learning rate according to the expected data streams. We show that the average estimate converges optimally and robustly to any data stream rate. In addition, noise reduction can be achieved by processing the data in a specific pattern, which is advantageous for large-scale machine learning. These theoretical results are illustrated for various data streams, showing the effectiveness of the proposed algorithms.
Published: 2021

23. Making the most of your day: online learning for optimal allocation of time

Author: Boursier, E., Garrec, T., Perchet, V., Scarsini, Marco, CB - Centre Borelli - UMR 9010 (CB), Service de Santé des Armées-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay)-Université de Paris (UP), EDF Lab, Ecole Nationale de la Statistique et de l'Analyse Economique (ENSAE), Ecole Nationale de la Statistique et de l'Analyse Economique, and Libera Università Internazionale degli Studi Sociali Guido Carli [Roma] (LUISS)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Other Statistics (stat.OT), online learning, online learning, scheduling, Machine Learning (stat.ML), Machine Learning (cs.LG), Statistics - Other Statistics, Statistics - Machine Learning, Optimization and Control (math.OC), FOS: Mathematics, scheduling, [MATH]Mathematics [math], Mathematics - Optimization and Control
Abstract: We study online learning for optimal allocation when the resource to be allocated is time. %Examples of possible applications include job scheduling for a computing server, a driver filling a day with rides, a landlord renting an estate, etc. An agent receives task proposals sequentially according to a Poisson process and can either accept or reject a proposed task. If she accepts the proposal, she is busy for the duration of the task and obtains a reward that depends on the task duration. If she rejects it, she remains on hold until a new task proposal arrives. We study the regret incurred by the agent, first when she knows her reward function but does not know the distribution of the task duration, and then when she does not know her reward function, either. This natural setting bears similarities with contextual (one-armed) bandits, but with the crucial difference that the normalized reward associated to a context depends on the whole distribution of contexts., Comment: NeurIPS 2021 camera ready
Published: 2021

24. Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth

Author: Xu, Keyulu, Zhang, Mozhi, Jegelka, Stefanie, Kawaguchi, Kenji, Massachusetts Institute of Technology (MIT), Harvard University [Cambridge], and Kawaguchi, Kenji
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], FOS: Computer and information sciences, Computer Science - Machine Learning, Computer Vision and Pattern Recognition (cs.CV), [INFO.INFO-NE] Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], Computer Science - Computer Vision and Pattern Recognition, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Machine Learning (stat.ML), [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], [STAT.ML] Statistics [stat]/Machine Learning [stat.ML], Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], 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: International audience; Graph Neural Networks (GNNs) have been studied through the lens of expressive power and generalization. However, their optimization properties are less well understood. We take the first step towards analyzing GNN training by studying the gradient dynamics of GNNs. First, we analyze linearized GNNs and prove that despite the non-convexity of training, convergence to a global minimum at a linear rate is guaranteed under mild assumptions that we validate on real-world graphs. Second, we study what may affect the GNNs' training speed. Our results show that the training of GNNs is implicitly accelerated by skip connections, more depth, and/or a good label distribution. Empirical results confirm that our theoretical results for linearized GNNs align with the training behavior of nonlinear GNNs. Our results provide the first theoretical support for the success of GNNs with skip connections in terms of optimization, and suggest that deep GNNs with skip connections would be promising in practice.
Published: 2021

25. Online A-optimal design and active linear regression

Author: Fontaine, Xavier, Perrault, Pierre, Valko, Michal, Perchet, Vianney, CB - Centre Borelli - UMR 9010 (CB), Service de Santé des Armées-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay)-Université de Paris (UP), Idemia, DeepMind [Paris], Ecole Nationale de la Statistique et de l'Analyse Economique (ENSAE), Ecole Nationale de la Statistique et de l'Analyse Economique, Criteo AI Lab, and Criteo [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 in this paper the problem of optimal experiment design where a decision maker can choose which points to sample to obtain an estimate $\hat{\beta}$ of the hidden parameter $\beta^{\star}$ of an underlying linear model. The key challenge of this work lies in the heteroscedasticity assumption that we make, meaning that each covariate has a different and unknown variance. The goal of the decision maker is then to figure out on the fly the optimal way to allocate the total budget of $T$ samples between covariates, as sampling several times a specific one will reduce the variance of the estimated model around it (but at the cost of a possible higher variance elsewhere). By trying to minimize the $\ell^2$-loss $\mathbb{E} [\lVert\hat{\beta}-\beta^{\star}\rVert^2]$ the decision maker is actually minimizing the trace of the covariance matrix of the problem, which corresponds then to online A-optimal design. Combining techniques from bandit and convex optimization we propose a new active sampling algorithm and we compare it with existing ones. We provide theoretical guarantees of this algorithm in different settings, including a $\mathcal{O}(T^{-2})$ regret bound in the case where the covariates form a basis of the feature space, generalizing and improving existing results. Numerical experiments validate our theoretical findings., Comment: 29 pages, 5 figures
Published: 2021

26. Revisiting Bayesian Optimization in the light of the COCO benchmark

Author: Victor Picheny, Rodolphe Le Riche, Centre National de la Recherche Scientifique (CNRS), Institut Henri Fayol (FAYOL-ENSMSE), École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), 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)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Institut Mines-Télécom [Paris] (IMT), Université Clermont Auvergne (UCA), Secondmind, Ecole Nationale Supérieure des Mines de St Etienne-Institut Henri Fayol, and Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne)
Subjects: FOS: Computer and information sciences, Mathematical optimization, Control and Optimization, Computer science, 0211 other engineering and technologies, Machine Learning (stat.ML), 02 engineering and technology, Statistics - Computation, symbols.namesake, Statistics - Machine Learning, 0202 electrical engineering, electronic engineering, information engineering, Code (cryptography), FOS: Mathematics, Optimization algorithm benchmark, Global optimization, Gaussian process, Mathematics - Optimization and Control, Computation (stat.CO), Bayesian optimization, 021103 operations research, global optimization, [INFO.INFO-CE]Computer Science [cs]/Computational Engineering, Finance, and Science [cs.CE], Expensive function optimization, Function (mathematics), Computer Graphics and Computer-Aided Design, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Computer Science Applications, [SPI.MECA.GEME]Engineering Sciences [physics]/Mechanics [physics.med-ph]/Mechanical engineering [physics.class-ph], Control and Systems Engineering, Optimization and Control (math.OC), Kernel (statistics), symbols, Benchmark (computing), 020201 artificial intelligence & image processing, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Engineering design process, Software
Abstract: International audience; It is commonly believed that Bayesian optimization (BO) algorithms are highly efficient for optimizing numerically costly functions. However, BO is not often compared to widely different alternatives, and is mostly tested on narrow sets of problems (multimodal, low-dimensional functions), which makes it difficult to assess where (or if) they actually achieve state-of-the-art performance. Moreover, several aspects in the design of these algorithms vary across implementations without a clear recommendation emerging from current practices, and many of these design choices are not substantiated by authoritative test campaigns. This article reports a large investigation about the effects on the performance of (Gaussian process based) BO of common and less common design choices. The experiments are carried out with the established COCO (COmparing Continuous Optimizers) software. It is found that a small initial budget, a quadratic trend, high-quality optimization of the acquisition criterion bring consistent progress. Using the GP mean as an occasional acquisition contributes to a negligible additional improvement. Warping degrades performance. The Mat\'ern 5/2 kernel is a good default but it may be surpassed by the exponential kernel on irregular functions. Overall, the best EGO variants are competitive or improve over state-of-the-art algorithms in dimensions less or equal to 5 for multimodal functions. The code developed for this study makes the new version (v2.1.1) of the R package DiceOptim available on CRAN. The structure of the experiments by function groups allows to define priorities for future research on Bayesian optimization.
Published: 2021

27. Linear support vector regression with linear constraints

Author: Samuel Vaiter, Quentin Klopfenstein, Institut de Mathématiques de Bourgogne [Dijon] (IMB), Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Bourgogne (UB), Centre National de la Recherche Scientifique (CNRS), French National Research Agency (ANR)ANR-18-CE40-0005INSERM Plan cancer18CP134-00Projet ANER RAGAG048CVCRB-2018ZZ, and ANR-18-CE40-0005,GraVa,Méthodes variationnelles pour les signaux sur graphe(2018)
Subjects: FOS: Computer and information sciences, Mathematical optimization, Statistics::Theory, Optimization problem, Support vector machine, Computer science, Machine Learning (stat.ML), 02 engineering and technology, Kernel (linear algebra), [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Artificial Intelligence, Statistics - Machine Learning, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Isotonic regression, Statistics::Methodology, Sequential minimal optimization, Constrained linear regression, [INFO]Computer Science [cs], Coordinate descent, Mathematics - Optimization and Control, Estimator, Probability vector, Support vector regression, Optimization and Control (math.OC), 020201 artificial intelligence & image processing, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Software
Abstract: International audience; This paper studies the addition of linear constraints to the Support Vector Regression when the kernel is linear. Adding those constraints into the problem allows to add prior knowledge on the estimator obtained, such as finding positive vector, probability vector or monotone data. We prove that the related optimization problem stays a semi-definite quadratic problem. We also propose a generalization of the Sequential Minimal Optimization algorithm for solving the optimization problem with linear constraints and prove its convergence. We show that an efficient generalization of this iterative algorithm with closed-form updates can be used to obtain the solution of the underlying optimization problem. Then, practical performances of this estimator are shown on simulated and real datasets with different settings: non negative regression, regression onto the simplex for biomedical data and isotonic regression for weather forecast. These experiments show the usefulness of this estimator in comparison to more classical approaches.
Published: 2021

28. Algorithmes statistiquement efficaces et en temps polynomial pour les semi-bandits combinatoires

Author: Thibaut Cuvelier, Eric Gourdin, Richard Combes, CentraleSupélec, Laboratoire des signaux et systèmes (L2S), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Orange Labs [Issy les Moulineaux], France Télécom, ACM, and Orange Gardens
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Computational complexity theory, Computer science, Computer Networks and Communications, 0211 other engineering and technologies, Machine Learning (stat.ML), 02 engineering and technology, Combinatorial Bandits, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Set (abstract data type), 010104 statistics & probability, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, Reinforcement learning, Combinatorial Optimization, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Computer Science (miscellaneous), 0101 mathematics, Safety, Risk, Reliability and Quality, Mathematics - Optimization and Control, Time complexity, Mathematics, Linear function (calculus), 021103 operations research, Approximation algorithm, Regret, Maximization, Function (mathematics), Uncorrelated, Approximation algorithms, Exponential function, Combinatorial optimisation, Optimization and Control (math.OC), Hardware and Architecture, Combinatorial optimization, Bandit algorithms, Bandits, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Algorithm, Software
Abstract: International audience; We consider combinatorial semi-bandits over a set X ⊂ {0, 1} d where rewards are uncorrelated across items. For this problem, the algorithm ESCB yields the smallest known regret bound R(T) = O d (ln m) 2 (ln T) ∆ min after T rounds, where m = max x ∈X 1 ⊤ x. However, ESCB has computational complexity O(|X|), which is typically exponential in d, and cannot be used in large dimensions. We propose the first algorithm that is both computationally and statistically efficient for this problem with regret R(T) = O d (ln m) 2 (ln T) ∆ min and computational asymptotic complexity O(δ −1 T poly(d)), where δ T is a function which vanishes arbitrarily slowly. Our approach involves carefully designing AESCB, an approximate version of ESCB with the same regret guarantees. We show that, whenever budgeted linear maximization over X can be solved up to a given approximation ratio, AESCB is implementable in polynomial time O(δ −1 T poly(d)) by repeatedly maximizing a linear function over X subject to a linear budget constraint, and showing how to solve these maximization problems efficiently. Additional algorithms, proofs and numerical experiments are given in the complete version of this work.
Published: 2021

29. Non-asymptotic convergence bounds for Wasserstein approximation using point clouds

Author: Merigot, Quentin, Santambrogio, Filippo, Sarrazin, Cl��ment, Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Jean Monnet [Saint-Étienne] (UJM)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), and ANR-16-CE40-0014,MAGA,Monge-Ampère et Géométrie Algorithmique(2016)
Subjects: FOS: Computer and information sciences, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Optimization and Control (math.OC), Statistics - Machine Learning, Optimal quantization, FOS: Mathematics, Optimal transport, Machine Learning (stat.ML), Wasserstein distance, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract: Several issues in machine learning and inverse problems require to generate discrete data, as if sampled from a model probability distribution. A common way to do so relies on the construction of a uniform probability distribution over a set of $N$ points which minimizes the Wasserstein distance to the model distribution. This minimization problem, where the unknowns are the positions of the atoms, is non-convex. Yet, in most cases, a suitably adjusted version of Lloyd's algorithm --- in which Voronoi cells are replaced by Power cells --- leads to configurations with small Wasserstein error. This is surprising because, again, of the non-convex nature of the problem, as well as the existence of spurious critical points. We provide explicit upper bounds for the convergence speed of this Lloyd-type algorithm, starting from a cloud of points sufficiently far from each other. This already works after one step of the iteration procedure, and similar bounds can be deduced, for the corresponding gradient descent. These bounds naturally lead to a modified Poliak-Łojasiewicz inequality for the Wasserstein distance cost, with an error term depending on the distances between Dirac masses in the discrete distribution.
Published: 2021

30. Automated Data-Driven Selection of the Hyperparameters for Total-Variation-Based Texture Segmentation

Author: Samuel Vaiter, Patrice Abry, Barbara Pascal, Nelly Pustelnik, Laboratoire de Physique de l'ENS Lyon (Phys-ENS), École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon, Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Bourgogne [Dijon] (IMB), Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Bourgogne (UB), ANR-19-CE48-0009,Multisc-In,Multiscale estimation and Interface detection(2019), École normale supérieure de Lyon (ENS de Lyon)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), and Université de Bourgogne (UB)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Statistics and Probability, Computer Science - Machine Learning, Computer science, proximal algorithms, Machine Learning (stat.ML), 02 engineering and technology, Least squares, Regularization (mathematics), Gaussian noise, Machine Learning (cs.LG), symbols.namesake, Bias of an estimator, Statistics - Machine Learning, Strong convexity, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Texture, [MATH]Mathematics [math], Mathematics - Optimization and Control, Total variation, Covariance matrix, Applied Mathematics, segmentation, SURE, Estimator, Stein Unbiased Risk Estimator, 68U10, 65K10, 65C20, 62F12, Condensed Matter Physics, Noise, Optimization and Control (math.OC), Modeling and Simulation, Texture segmentation, Hyperparameter optimization, Regularization parameters tuning, Algorithmic differentiation, symbols, 020201 artificial intelligence & image processing, Geometry and Topology, Computer Vision and Pattern Recognition, Algorithm, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Estimation
Abstract: Penalized Least Squares are widely used in signal and image processing. Yet, it suffers from a major limitation since it requires fine-tuning of the regularization parameters. Under assumptions on the noise probability distribution, Stein-based approaches provide unbiased estimator of the quadratic risk. The Generalized Stein Unbiased Risk Estimator is revisited to handle correlated Gaussian noise without requiring to invert the covariance matrix. Then, in order to avoid expansive grid search, it is necessary to design algorithmic scheme minimizing the quadratic risk with respect to regularization parameters. This work extends the Stein's Unbiased GrAdient estimator of the Risk of Deledalle et al. to the case of correlated Gaussian noise, deriving a general automatic tuning of regularization parameters. First, the theoretical asymptotic unbiasedness of the gradient estimator is demonstrated in the case of general correlated Gaussian noise. Then, the proposed parameter selection strategy is particularized to fractal texture segmentation, where problem formulation naturally entails inter-scale and spatially correlated noise. Numerical assessment is provided, as well as discussion of the practical issues., Submitted to SIAM Imaging Science
Published: 2021

31. Learning Value Functions in Deep Policy Gradients using Residual Variance

Author: Flet-Berliac, Yannis, Ouhamma, Reda, Maillard, Odalric-Ambrym, Preux, Philippe, 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), Université de Lille-Ecole Centrale de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Ecole Centrale de Lille-Centre National de la Recherche Scientifique (CNRS), Scool (Scool), 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, Artificial Intelligence (cs.AI), [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Optimization and Control (math.OC), Computer Science - Artificial Intelligence, Statistics - Machine Learning, FOS: Mathematics, Machine Learning (stat.ML), Mathematics - Optimization and Control, Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: Policy gradient algorithms have proven to be successful in diverse decision making and control tasks. However, these methods suffer from high sample complexity and instability issues. In this paper, we address these challenges by providing a different approach for training the critic in the actor-critic framework. Our work builds on recent studies indicating that traditional actor-critic algorithms do not succeed in fitting the true value function, calling for the need to identify a better objective for the critic. In our method, the critic uses a new state-value (resp. state-action-value) function approximation that learns the value of the states (resp. state-action pairs) relative to their mean value rather than the absolute value as in conventional actor-critic. We prove the theoretical consistency of the new gradient estimator and observe dramatic empirical improvement across a variety of continuous control tasks and algorithms. Furthermore, we validate our method in tasks with sparse rewards, where we provide experimental evidence and theoretical insights., Accepted at ICLR 2021
Published: 2021

32. Accelerating Block Coordinate Descent for Nonnegative Tensor Factorization

Author: Jeremy E. Cohen, Le Thi Khanh Hien, Andersen Man Shun Ang, Nicolas Gillis, Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio (PANAMA), 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 (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), 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)-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), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), FNRS, Fonds Wetenschappelijk Onderzoek - Vlaanderen, O005318F-RG47, ANR-20-CE23-0010,LoRAiA,Approximations de rang faible pour l'intelligence artificielle(2020), European Project: 679515,H2020,ERC-2015-STG,COLORAMAP(2016), 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 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), SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Inria Rennes – Bretagne Atlantique, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Heuristic (computer science), Extrapolation, MathematicsofComputing_NUMERICALANALYSIS, Machine Learning (stat.ML), 010103 numerical & computational mathematics, 01 natural sciences, Machine Learning (cs.LG), [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Convergence (routing), FOS: Mathematics, Mathematics - Numerical Analysis, Nonnegative tensor factorization, 0101 mathematics, Coordinate descent, Mathematics - Optimization and Control, Computational budget, Block (data storage), Mathematics, Descent (mathematics), Algebra and Number Theory, Applied Mathematics, Numerical Analysis (math.NA), 010101 applied mathematics, Optimization and Control (math.OC), Algorithm
Abstract: This paper is concerned with improving the empirical convergence speed of block-coordinate descent algorithms for approximate nonnegative tensor factorization (NTF). We propose an extrapolation strategy in-between block updates, referred to as heuristic extrapolation with restarts (HER). HER significantly accelerates the empirical convergence speed of most existing block-coordinate algorithms for dense NTF, in particular for challenging computational scenarios, while requiring a negligible additional computational budget., 32 pages, 24 figures
Published: 2021

33. Solving Inverse Problems by Joint Posterior Maximization with Autoencoding Prior

Author: Mario González, Andrés Almansa, Pauline Tan, Universidad de la República (UDELAR), Mathématiques Appliquées Paris 5 (MAP5 - UMR 8145), Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), and ANR-19-CE23-0027,PostProdLEAP,Repenser la post-production d'archives avec des méthodes à patch, variationnelles et par apprentissage(2019)
Subjects: FOS: Computer and information sciences, Bi-convex Optimization, Computer Science - Machine Learning, General Mathematics, Computer Vision and Pattern Recognition (cs.CV), Inverse Problems, Computer Science - Computer Vision and Pattern Recognition, Machine Learning (stat.ML), Machine Learning (cs.LG), [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Generative Models, Image Restoration, Variational Auto-encoders, Mathematics - Optimization and Control, Applied Mathematics, Image and Video Processing (eess.IV), Electrical Engineering and Systems Science - Image and Video Processing, Optimization and Control (math.OC), [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Bayesian Statistics, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: In this work we address the problem of solving ill-posed inverse problems in imaging where the prior is a variational autoencoder (VAE). Specifically we consider the decoupled case where the prior is trained once and can be reused for many different log-concave degradation models without retraining. Whereas previous MAP-based approaches to this problem lead to highly non-convex optimization algorithms, our approach computes the joint (space-latent) MAP that naturally leads to alternate optimization algorithms and to the use of a stochastic encoder to accelerate computations. The resulting technique (JPMAP) performs Joint Posterior Maximization using an Autoencoding Prior. We show theoretical and experimental evidence that the proposed objective function is quite close to bi-convex. Indeed it satisfies a weak bi-convexity property which is sufficient to guarantee that our optimization scheme converges to a stationary point. We also highlight the importance of correctly training the VAE using a denoising criterion, in order to ensure that the encoder generalizes well to out-of-distribution images, without affecting the quality of the generative model. This simple modification is key to providing robustness to the whole procedure. Finally we show how our joint MAP methodology relates to more common MAP approaches, and we propose a continuation scheme that makes use of our JPMAP algorithm to provide more robust MAP estimates. Experimental results also show the higher quality of the solutions obtained by our JPMAP approach with respect to other non-convex MAP approaches which more often get stuck in spurious local optima., Comment: arXiv admin note: text overlap with arXiv:1911.06379
Published: 2021

34. Some Remarks on Replicated Simulated Annealing

Author: Vincent Gripon, Franck Vermet, Matthias Löwe, Département Mathematical and Electrical Engineering (IMT Atlantique - MEE), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Fachbereich Mathematik und Informatik [Münster] = Fachbereich Mathematik und Informatik [Münster] (FB 10), Westfälische Wilhelms-Universität Münster (WWU), Laboratoire de mathématiques de Brest (LM), Université de Brest (UBO)-Institut Brestois du Numérique et des Mathématiques (IBNM), and Université de Brest (UBO)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Computer science, Machine Learning (stat.ML), 01 natural sciences, Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], 010104 statistics & probability, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Statistics - Machine Learning, Convergence (routing), FOS: Mathematics, Neural and Evolutionary Computing (cs.NE), 0101 mathematics, Mathematics - Optimization and Control, Mathematical Physics, Ansatz, Artificial neural network, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Replica, Probability (math.PR), 010102 general mathematics, Computer Science - Neural and Evolutionary Computing, Statistical and Nonlinear Physics, Perceptron, Optimization and Control (math.OC), Simulated annealing, Algorithm, Mathematics - Probability
Abstract: Recently authors have introduced the idea of training discrete weights neural networks using a mix between classical simulated annealing and a replica ansatz known from the statistical physics literature. Among other points, they claim their method is able to find robust configurations. In this paper, we analyze this so called “replicated simulated annealing” algorithm. In particular, we give criteria to guarantee its convergence, and study when it successfully samples from configurations. We also perform experiments using synthetic and real data bases.
Published: 2021

35. Bayesian optimization of variable-size design space problems

Author: El-Ghazali Talbi, Mathieu Balesdent, Julien Pelamatti, Yannick Guerin, Loïc Brevault, DTIS, ONERA, Université Paris Saclay [Palaiseau], ONERA-Université Paris-Saclay, Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), and Centre National d'Etudes Spatiales - Direction Des Lanceurs. (CNES)
Subjects: FOS: Computer and information sciences, Mathematical optimization, Control and Optimization, Optimization problem, Discrete variables, Computer science, 0211 other engineering and technologies, Complex system, Aerospace Engineering, Machine Learning (stat.ML), Variable-size design space optimization problems, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, [SPI]Engineering Sciences [physics], Statistics - Machine Learning, Convergence (routing), FOS: Mathematics, 0101 mathematics, Electrical and Electronic Engineering, [MATH]Mathematics [math], Mathematics - Optimization and Control, Civil and Structural Engineering, Variable (mathematics), Bayesian optimization, [PHYS]Physics [physics], 021103 operations research, Mechanical Engineering, Function (mathematics), Covariance, Mixed-variable optimization problems, Optimization and Control (math.OC), Focus (optics), Software
Abstract: International audience; Within the framework of complex system design, it is often necessary to solve mixed variable optimization problems, in which the objective and constraint functions can depend simultaneously on continuous and discrete variables. Additionally, complex system design problems occasionally present a variable-size design space. This results in an optimization problem for which the search space varies dynamically (with respect to both number and type of variables) along the optimization process as a function of the values of specific discrete decision variables. Similarly, the number and type of constraints can vary as well. In this paper, two alternative Bayesian optimization-based approaches are proposed in order to solve this type of optimization problems. The first one consists of a budget allocation strategy allowing to focus the computational budget on the most promising design sub-spaces. The second approach, instead, is based on the definition of a kernel function allowing to compute the covariance between samples characterized by partially different sets of variables. The results obtained on analytical and engineering related test-cases show a faster and more consistent convergence of both proposed methods with respect to the standard approaches.
Published: 2021

36. Denoising modulo samples: k-NN regression and tightness of SDP relaxation

Author: Michaël Fanuel, Hemant Tyagi, Department of Electrical Engineering [KU Leuven] (KU-ESAT), Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven), MOdel for Data Analysis and Learning (MODAL), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Laboratoire Paul Painlevé - UMR 8524 (LPP), and Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe
Subjects: FOS: Computer and information sciences, Statistics and Probability, Modulo, Machine Learning (stat.ML), Mathematics - Statistics Theory, Statistics Theory (math.ST), 01 natural sciences, 030218 nuclear medicine & medical imaging, k-nearest neighbors algorithm, 010309 optics, Combinatorics, 03 medical and health sciences, 0302 clinical medicine, Statistics - Machine Learning, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], 0103 physical sciences, FOS: Mathematics, Mathematics - Optimization and Control, Mathematics, Numerical Analysis, Quadratically constrained quadratic program, Smoothness (probability theory), Applied Mathematics, Function (mathematics), Lipschitz continuity, Computational Theory and Mathematics, Optimization and Control (math.OC), Relaxation (approximation), Laplace operator, Analysis
Abstract: Many modern applications involve the acquisition of noisy modulo samples of a function $f$, with the goal being to recover estimates of the original samples of $f$. For a Lipschitz function $f:[0,1]^d \to \mathbb{R}$, suppose we are given the samples $y_i = (f(x_i) + \eta_i)\bmod 1; \quad i=1,\dots,n$ where $\eta_i$ denotes noise. Assuming $\eta_i$ are zero-mean i.i.d Gaussian's, and $x_i$'s form a uniform grid, we derive a two-stage algorithm that recovers estimates of the samples $f(x_i)$ with a uniform error rate $O((\frac{\log n}{n})^{\frac{1}{d+2}})$ holding with high probability. The first stage involves embedding the points on the unit complex circle, and obtaining denoised estimates of $f(x_i)\bmod 1$ via a $k$NN (nearest neighbor) estimator. The second stage involves a sequential unwrapping procedure which unwraps the denoised mod $1$ estimates from the first stage. The estimates of the samples $f(x_i)$ can be subsequently utilized to construct an estimate of the function $f$, with the aforementioned uniform error rate. Recently, Cucuringu and Tyagi proposed an alternative way of denoising modulo $1$ data which works with their representation on the unit complex circle. They formulated a smoothness regularized least squares problem on the product manifold of unit circles, where the smoothness is measured with respect to the Laplacian of a proximity graph $G$ involving the $x_i$'s. This is a nonconvex quadratically constrained quadratic program (QCQP) hence they proposed solving its semidefinite program (SDP) based relaxation. We derive sufficient conditions under which the SDP is a tight relaxation of the QCQP. Hence under these conditions, the global solution of QCQP can be obtained in polynomial time., Comment: (i) 38 pages, 6 figures (ii) Revised the manuscript after receiving reviews (iii) Removed Theorem 3(2) and Corollary 3 due to inaccuracies in the proof, main results are unchanged (iv) Added Appendix B (v) Added Section 2.5 for estimating f (Theorem 5)
Published: 2021

37. Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD

Author: Bardenet, Remi, Ghosh, Subhro, Lin, Meixia, Centre National de la Recherche Scientifique (CNRS), 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), and National University of Singapore (NUS)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Probability (math.PR), FOS: Physical sciences, Machine Learning (stat.ML), Disordered Systems and Neural Networks (cond-mat.dis-nn), Condensed Matter - Disordered Systems and Neural Networks, 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, Mathematics - Optimization and Control, Mathematics - Probability, ComputingMilieux_MISCELLANEOUS
Abstract: Stochastic gradient descent (SGD) is a cornerstone of machine learning. When the number N of data items is large, SGD relies on constructing an unbiased estimator of the gradient of the empirical risk using a small subset of the original dataset, called a minibatch. Default minibatch construction involves uniformly sampling a subset of the desired size, but alternatives have been explored for variance reduction. In particular, experimental evidence suggests drawing minibatches from determinantal point processes (DPPs), distributions over minibatches that favour diversity among selected items. However, like in recent work on DPPs for coresets, providing a systematic and principled understanding of how and why DPPs help has been difficult. In this work, we contribute an orthogonal polynomial-based DPP paradigm for minibatch sampling in SGD. Our approach leverages the specific data distribution at hand, which endows it with greater sensitivity and power over existing data-agnostic methods. We substantiate our method via a detailed theoretical analysis of its convergence properties, interweaving between the discrete data set and the underlying continuous domain. In particular, we show how specific DPPs and a string of controlled approximations can lead to gradient estimators with a variance that decays faster with the batchsize than under uniform sampling. Coupled with existing finite-time guarantees for SGD on convex objectives, this entails that, DPP minibatches lead to a smaller bound on the mean square approximation error than uniform minibatches. Moreover, our estimators are amenable to a recent algorithm that directly samples linear statistics of DPPs (i.e., the gradient estimator) without sampling the underlying DPP (i.e., the minibatch), thereby reducing computational overhead. We provide detailed synthetic as well as real data experiments to substantiate our theoretical claims., Accepted at NeurIPS 2021 (Spotlight Paper). Authors are listed in alphabetical order
Published: 2021

38. On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layers

Author: Kawaguchi, Kenji, Kawaguchi, Kenji, and Harvard University [Cambridge]
Subjects: FOS: Computer and information sciences, [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], Computer Science - Machine Learning, Computer Science - Artificial Intelligence, Computer Vision and Pattern Recognition (cs.CV), Computer Science - Computer Vision and Pattern Recognition, [INFO.INFO-NE] Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], Machine Learning (stat.ML), [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], [STAT.ML] Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Machine Learning (cs.LG), Artificial Intelligence (cs.AI), [INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], 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: A deep equilibrium model uses implicit layers, which are implicitly defined through an equilibrium point of an infinite sequence of computation. It avoids any explicit computation of the infinite sequence by finding an equilibrium point directly via root-finding and by computing gradients via implicit differentiation. In this paper, we analyze the gradient dynamics of deep equilibrium models with nonlinearity only on weight matrices and non-convex objective functions of weights for regression and classification. Despite non-convexity, convergence to global optimum at a linear rate is guaranteed without any assumption on the width of the models, allowing the width to be smaller than the output dimension and the number of data points. Moreover, we prove a relation between the gradient dynamics of the deep implicit layer and the dynamics of trust region Newton method of a shallow explicit layer. This mathematically proven relation along with our numerical observation suggests the importance of understanding implicit bias of implicit layers and an open problem on the topic. Our proofs deal with implicit layers, weight tying and nonlinearity on weights, and differ from those in the related literature., Comment: ICLR 2021. Selected for ICLR Spotlight (top 6% submissions)
Published: 2021

39. Finding Global Minima via Kernel Approximations

Author: Rudi, Alessandro, Marteau-Ferey, Ulysse, Bach, Francis, Université Paris sciences et lettres (PSL), 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), 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 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), This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the 'Investissements d’avenir' program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). We also acknowledge support from the European Research Council (grant SEQUOIA 724063)., ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), European Project: 724063,ERC-2016-COG,SEQUOIA(2017), 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), 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, Polynomial optimization, Machine Learning (stat.ML), Machine Learning (cs.LG), [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, FOS: Mathematics, Semidefinite programming, Global optimization, Mathematics - Optimization and Control, Sum of squares
Abstract: We consider the global minimization of smooth functions based solely on function evaluations. Algorithms that achieve the optimal number of function evaluations for a given precision level typically rely on explicitly constructing an approximation of the function which is then minimized with algorithms that have exponential running-time complexity. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum. This is done by using infinite sums of square smooth functions and has strong links with polynomial sum-of-squares hierarchies. Leveraging recent representation properties of reproducing kernel Hilbert spaces, the infinite-dimensional optimization problem can be solved by subsampling in time polynomial in the number of function evaluations, and with theoretical guarantees on the obtained minimum. Given $n$ samples, the computational cost is $O(n^{3.5})$ in time, $O(n^2)$ in space, and we achieve a convergence rate to the global optimum that is $O(n^{-m/d + 1/2 + 3/d})$ where $m$ is the degree of differentiability of the function and $d$ the number of dimensions. The rate is nearly optimal in the case of Sobolev functions and more generally makes the proposed method particularly suitable for functions that have a large number of derivatives. Indeed, when $m$ is in the order of $d$, the convergence rate to the global optimum does not suffer from the curse of dimensionality, which affects only the worst-case constants (that we track explicitly through the paper).
Published: 2020

40. Convergence of Online Adaptive and Recurrent Optimization Algorithms

Author: Massé, Pierre-Yves, Ollivier, Yann, Czech Technical University in Prague (CTU), Facebook AI Research [Paris] (FAIR), and Facebook
Subjects: FOS: Computer and information sciences, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Optimization and Control (math.OC), Statistics - Machine Learning, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], FOS: Mathematics, Machine Learning (stat.ML), Dynamical Systems (math.DS), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Dynamical Systems, Mathematics - Optimization and Control
Abstract: We prove local convergence of several notable gradient descent algorithms used in machine learning, for which standard stochastic gradient descent theory does not apply directly. This includes, first, online algorithms for recurrent models and dynamical systems, such as \emph{Real-time recurrent learning} (RTRL) and its computationally lighter approximations NoBackTrack and UORO; second, several adaptive algorithms such as RMSProp, online natural gradient, and Adam with $\beta^2\to 1$.Despite local convergence being a relatively weak requirement for a new optimization algorithm, no local analysis was available for these algorithms, as far as we knew. Analysis of these algorithms does not immediately follow from standard stochastic gradient (SGD) theory. In fact, Adam has been proved to lack local convergence in some simple situations \citep{j.2018on}. For recurrent models, online algorithms modify the parameter while the model is running, which further complicates the analysis with respect to simple SGD.Local convergence for these various algorithms results from a single, more general set of assumptions, in the setup of learning dynamical systems online. Thus, these results can cover other variants of the algorithms considered.We adopt an ``ergodic'' rather than probabilistic viewpoint, working with empirical time averages instead of probability distributions. This is more data-agnostic and creates differences with respect to standard SGD theory, especially for the range of possible learning rates. For instance, with cycling or per-epoch reshuffling over a finite dataset instead of pure i.i.d.\ sampling with replacement, empirical averages of gradients converge at rate $1/T$ instead of $1/\sqrt{T}$ (cycling acts as a variance reduction method), theoretically allowing for larger learning rates than in SGD.
Published: 2020

41. Faster Wasserstein Distance Estimation with the Sinkhorn Divergence

Author: Chizat, Lenaic, Roussillon, Pierre, Léger, Flavien, Vialard, François-Xavier, Peyré, Gabriel, Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Département de Mathématiques et Applications - ENS Paris (DMA), É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é Gustave Eiffel, ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), European Project: H2020 724175, NORIA, 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)-Université Paris-Sud - Paris 11 (UP11), École normale supérieure - Paris (ENS Paris), and Université Gustave Eiffel (UNIV GUSTAVE EIFFEL)
Subjects: FOS: Computer and information sciences, Entropic regularization, Mathematics - Statistics Theory, Machine Learning (stat.ML), Statistics Theory (math.ST), Empirical distribution, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Optimization and Control (math.OC), [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], FOS: Mathematics, Wasserstein distance, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Estimation
Abstract: International audience; The squared Wasserstein distance is a natural quantity to compare probability distributions in a non-parametric setting. This quantity is usually estimated with the plug-in estimator, defined via a discrete optimal transport problem which can be solved to $\epsilon$-accuracy by adding an entropic regularization of order $\epsilon$ and using for instance Sinkhorn's algorithm. In this work, we propose instead to estimate it with the Sinkhorn divergence, which is also built on entropic regularization but includes debiasing terms. We show that, for smooth densities, this estimator has a comparable sample complexity but allows higher regularization levels, of order $\epsilon^{1/2}$, which leads to improved computational complexity bounds and a strong speedup in practice. Our theoretical analysis covers the case of both randomly sampled densities and deterministic discretizations on uniform grids. We also propose and analyze an estimator based on Richardson extrapolation of the Sinkhorn divergence which enjoys improved statistical and computational efficiency guarantees, under a condition on the regularity of the approximation error, which is in particular satisfied for Gaussian densities. We finally demonstrate the efficiency of the proposed estimators with numerical experiments.
Published: 2020

42. Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model

Author: Berthier, Raphaël, Bach, Francis, Gaillard, Pierre, Université Paris sciences et lettres (PSL), 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), Apprentissage de modèles à partir de données massives (Thoth), 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), 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)-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), This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the 'Investissements d’avenir' program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). We acknowledge support from the European Research Council (grant SEQUOIA724063) and from the DGA., ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), 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, É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 We acknowledge support from the European Research Council (grant SEQUOIA724063) and from the DGA.
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Kernel regression, Machine Learning (stat.ML), Machine Learning (cs.LG), Stochastic gradient descent, Gossip algorithm, [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, [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA], FOS: Mathematics, Averaging process, Computer Science - Multiagent Systems, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Multiagent Systems (cs.MA), Nonparametric rates
Abstract: International audience; In the context of statistical supervised learning, the noiseless linear model assumes that there exists a deterministic linear relation $Y = \langle \theta_*, X \rangle$ between the random output $Y$ and the random feature vector $\Phi(U)$, a potentially non-linear transformation of the inputs $U$. We analyze the convergence of single-pass, fixed step-size stochastic gradient descent on the least-square risk under this model. The convergence of the iterates to the optimum $\theta_*$ and the decay of the generalization error follow polynomial convergence rates with exponents that both depend on the regularities of the optimum $\theta_*$ and of the feature vectors $\Phi(u)$. We interpret our result in the reproducing kernel Hilbert space framework. As a special case, we analyze an online algorithm for estimating a real function on the unit interval from the noiseless observation of its value at randomly sampled points; the convergence depends on the Sobolev smoothness of the function and of a chosen kernel. Finally, we apply our analysis beyond the supervised learning setting to obtain convergence rates for the averaging process (a.k.a. gossip algorithm) on a graph depending on its spectral dimension.
Published: 2020

43. On the almost sure convergence of stochastic gradient descent in non-convex problems

Author: Mertikopoulos, P., Nadav Hallak, Kavis, A., Cevher, V., 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), 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)-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), Criteo AI Lab, Criteo [Paris], Ecole Polytechnique Fédérale de Lausanne (EPFL), ANR-19-P3IA-0003,MIAI,MIAI @ Grenoble Alpes(2019), ANR-11-LABX-0025,PERSYVAL-lab,Systemes et Algorithmes Pervasifs au confluent des mondes physique et numérique(2011), and ANR-19-CE48-0018,ALIAS,Apprentissage adaptatif multi-agent(2019)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Probability (math.PR), Machine Learning (stat.ML), Machine Learning (cs.LG), 90C15, 37N40 Non-convex optimization, ml-ai, Primary 90C26, 62L20, secondary 90C30, 90C15, 37N40, 2020 Mathematics Subject Classification. Primary 90C26, Optimization and Control (math.OC), Statistics - Machine Learning, stochastic gradient descent, stochastic approximation, FOS: Mathematics, secondary 90C30, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 62L20, Mathematics - Optimization and Control, Mathematics - Probability
Abstract: This paper analyzes the trajectories of stochastic gradient descent (SGD) to help understand the algorithm's convergence properties in non-convex problems. We first show that the sequence of iterates generated by SGD remains bounded and converges with probability $1$ under a very broad range of step-size schedules. Subsequently, going beyond existing positive probability guarantees, we show that SGD avoids strict saddle points/manifolds with probability $1$ for the entire spectrum of step-size policies considered. Finally, we prove that the algorithm's rate of convergence to Hurwicz minimizers is $\mathcal{O}(1/n^{p})$ if the method is employed with a $\Theta(1/n^p)$ step-size schedule. This provides an important guideline for tuning the algorithm's step-size as it suggests that a cool-down phase with a vanishing step-size could lead to faster convergence; we demonstrate this heuristic using ResNet architectures on CIFAR., Comment: 32 pages, 8 figures
Published: 2020

44. Model identification and local linear convergence of coordinate descent

Author: Klopfenstein, Quentin, Bertrand, Quentin, Gramfort, Alexandre, Salmon, Joseph, Vaiter, Samuel, Institut de Mathématiques de Bourgogne [Dijon] (IMB), Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Bourgogne (UB), 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 Montpelliérain Alexander Grothendieck (IMAG), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Université de Bourgogne (UB)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-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, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Bertrand, Quentin
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, 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], Machine Learning (stat.ML), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-ST] Mathematics [math]/Statistics [math.ST], Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: For composite nonsmooth optimization problems, Forward-Backward algorithm achieves model identification (e.g., support identification for the Lasso) after a finite number of iterations, provided the objective function is regular enough. Results concerning coordinate descent are scarcer and model identification has only been shown for specific estimators, the support-vector machine for instance. In this work, we show that cyclic coordinate descent achieves model identification in finite time for a wide class of functions. In addition, we prove explicit local linear convergence rates for coordinate descent. Extensive experiments on various estimators and on real datasets demonstrate that these rates match well empirical results.
Published: 2020

45. Finite-sample analysis of M-estimators using self-concordance

Author: Dmitrii Ostrovskii, Francis Bach, University of Southern California (USC), 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), 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 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), 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), 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: Statistics and Probability, FOS: Computer and information sciences, Dimension (graph theory), Machine Learning (stat.ML), Mathematics - Statistics Theory, Statistics Theory (math.ST), self-concordance, robustness, Type (model theory), random design, Third derivative, 01 natural sciences, Measure (mathematics), Combinatorics, 010104 statistics & probability, 90C90, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, 0502 economics and business, FOS: Mathematics, Uniform boundedness, 0101 mathematics, Mathematics - Optimization and Control, 050205 econometrics, Mathematics, Second derivative, empirical risk minimization, logistic regression, 05 social sciences, [STAT.TH]Statistics [stat]/Statistics Theory [stat.TH], Asymptotic theory (statistics), Effective dimension, fast rates, Optimization and Control (math.OC), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Statistics, Probability and Uncertainty, $M$-estimators, 62F12, 62F10, 62F99
Abstract: The classical asymptotic theory for parametric $M$-estimators guarantees that, in the limit of infinite sample size, the excess risk has a chi-square type distribution, even in the misspecified case. We demonstrate how self-concordance of the loss allows to characterize the critical sample size sufficient to guarantee a chi-square type in-probability bound for the excess risk. Specifically, we consider two classes of losses: (i) self-concordant losses in the classical sense of Nesterov and Nemirovski, i.e., whose third derivative is uniformly bounded with the $3/2$ power of the second derivative; (ii) pseudo self-concordant losses, for which the power is removed. These classes contain losses corresponding to several generalized linear models, including the logistic loss and pseudo-Huber losses. ¶ Our basic result under minimal assumptions bounds the critical sample size by $O(d\cdot d_{\text{eff}})$, where $d$ the parameter dimension and $d_{\text{eff}}$ the effective dimension that accounts for model misspecification. In contrast to the existing results, we only impose local assumptions that concern the population risk minimizer $\theta _{*}$. Namely, we assume that the calibrated predictors, i.e., predictors scaled by the square root of the second derivative of the loss, is subgaussian at $\theta _{*}$. Besides, for type-ii losses we require boundedness of certain measure of curvature of the population risk at $\theta _{*}$. ¶ Our improved result bounds the critical sample size from above as \begin{equation*}O(\max \{d_{\text{eff}},d\log d\})\end{equation*} under slightly stronger assumptions. Namely, the local assumptions must hold in the neighborhood of $\theta _{*}$ given by the Dikin ellipsoid of the population risk. Interestingly, we find that, for logistic regression with Gaussian design, there is no actual restriction of conditions: the subgaussian parameter and curvature measure remain near-constant over the Dikin ellipsoid. Finally, we extend some of these results to $\ell _{1}$-penalized estimators in high dimensions.
Published: 2020

46. Sparse Optimization on Measures with Over-parameterized Gradient Descent

Author: Lénaïc Chizat, Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), and Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, General Mathematics, 0211 other engineering and technologies, Parameterized complexity, Machine Learning (stat.ML), Sparse optimization, 010103 numerical & computational mathematics, 02 engineering and technology, Global convergence, 01 natural sciences, Measure (mathematics), [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Non-convex optimization, Wasserstein Space, FOS: Mathematics, Applied mathematics, 0101 mathematics, Mathematics - Optimization and Control, Mathematics, 021103 operations research, Artificial neural network, BLASSO, Regular polygon, Lojasiewicz Gradient Inequality, Manifold, Local convergence, Optimization and Control (math.OC), Mirror descent, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Gradient descent, Convex function, Software
Abstract: Minimizing a convex function of a measure with a sparsity-inducing penalty is a typical problem arising, e.g., in sparse spikes deconvolution or two-layer neural networks training. We show that this problem can be solved by discretizing the measure and running non-convex gradient descent on the positions and weights of the particles. For measures on a d-dimensional manifold and under some non-degeneracy assumptions, this leads to a global optimization algorithm with a complexity scaling as $$\log (1/\epsilon )$$ in the desired accuracy $$\epsilon $$ , instead of $$\epsilon ^{-d}$$ for convex methods. The key theoretical tools are a local convergence analysis in Wasserstein space and an analysis of a perturbed mirror descent in the space of measures. Our bounds involve quantities that are exponential in d which is unavoidable under our assumptions.
Published: 2020

47. First-order Optimization for Superquantile-based Supervised Learning

Author: Jérôme Malick, Zaid Harchaoui, Yassine Laguel, Données, Apprentissage et Optimisation (DAO), 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), University of Washington [Seattle], and ANR-19-P3IA-0003,MIAI,MIAI @ Grenoble Alpes(2019)
Subjects: FOS: Computer and information sciences, Computer Science::Machine Learning, Computer Science - Machine Learning, Computer science, 0211 other engineering and technologies, Machine Learning (stat.ML), 02 engineering and technology, 010501 environmental sciences, Machine learning, computer.software_genre, 01 natural sciences, supervised learning, Machine Learning (cs.LG), Convolution, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, SAFER, FOS: Mathematics, Mathematics - Optimization and Control, 0105 earth and related environmental sciences, 021103 operations research, distributional robustness, business.industry, Risk measure, Supervised learning, Function (mathematics), nonsmooth optimization, risk measure, [STAT]Statistics [stat], Optimization and Control (math.OC), Minification, Artificial intelligence, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], business, computer, Smoothing, Test data
Abstract: Classical supervised learning via empirical risk (or negative log-likelihood) minimization hinges upon the assumption that the testing distribution coincides with the training distribution. This assumption can be challenged in modern applications of machine learning in which learning machines may operate at prediction time with testing data whose distribution departs from the one of the training data. We revisit the superquantile regression method by proposing a first-order optimization algorithm to minimize a superquantile-based learning objective. The proposed algorithm is based on smoothing the superquantile function by infimal convolution. Promising numerical results illustrate the interest of the approach towards safer supervised learning., 6 pages, 2 figures, 2 tables, presented at IEEE MLSP
Published: 2020

48. Sparse Separable Nonnegative Matrix Factorization

Author: Jeremy E. Cohen, Nicolas Gillis, Nicolas Nadisic, Arnaud Vandaele, University of Mons [Belgium] (UMONS), Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio (PANAMA), 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 (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), 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)-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), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5), 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)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), and 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)
Subjects: Signal Processing (eess.SP), FOS: Computer and information sciences, Computer Science - Machine Learning, Computer science, Computer Vision and Pattern Recognition (cs.CV), Multispectral image, Computer Science - Computer Vision and Pattern Recognition, Machine Learning (stat.ML), 02 engineering and technology, Least squares, Machine Learning (cs.LG), Separable space, Non-negative matrix factorization, Matrix (mathematics), Statistics::Machine Learning, Statistics - Machine Learning, FOS: Electrical engineering, electronic engineering, information engineering, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Electrical Engineering and Systems Science - Signal Processing, [MATH]Mathematics [math], Time complexity, Mathematics - Optimization and Control, Dykstra's projection algorithm, 020206 networking & telecommunications, Solver, Computer Science::Numerical Analysis, Optimization and Control (math.OC), 020201 artificial intelligence & image processing, Algorithm
Abstract: We propose a new variant of nonnegative matrix factorization (NMF), combining separability and sparsity assumptions. Separability requires that the columns of the first NMF factor are equal to columns of the input matrix, while sparsity requires that the columns of the second NMF factor are sparse. We call this variant sparse separable NMF (SSNMF), which we prove to be NP-complete, as opposed to separable NMF which can be solved in polynomial time. The main motivation to consider this new model is to handle underdetermined blind source separation problems, such as multispectral image unmixing. We introduce an algorithm to solve SSNMF, based on the successive nonnegative projection algorithm (SNPA, an effective algorithm for separable NMF), and an exact sparse nonnegative least squares solver. We prove that, in noiseless settings and under mild assumptions, our algorithm recovers the true underlying sources. This is illustrated by experiments on synthetic data sets and the unmixing of a multispectral image., 20 pages, accepted in ECML 2020
Published: 2020

49. Decentralized gradient methods: does topology matter?

Author: Neglia, Giovanni, Xu, Chuan, Towsley, Don, Calbi, Gianmarco, 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 Computer Science [Amherst], University of Massachusetts [Amherst] (UMass Amherst), and University of Massachusetts System (UMASS)-University of Massachusetts System (UMASS)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Computer Science - Distributed, Parallel, and Cluster Computing, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, Machine Learning (stat.ML), Distributed, Parallel, and Cluster Computing (cs.DC), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: Consensus-based distributed optimization methods have recently been advocated as alternatives to parameter server and ring all-reduce paradigms for large scale training of machine learning models. In this case, each worker maintains a local estimate of the optimal parameter vector and iteratively updates it by averaging the estimates obtained from its neighbors, and applying a correction on the basis of its local dataset. While theoretical results suggest that worker communication topology should have strong impact on the number of epochs needed to converge, previous experiments have shown the opposite conclusion. This paper sheds lights on this apparent contradiction and show how sparse topologies can lead to faster convergence even in the absence of communication delays., A version of this paper is to appear at AISTATS 2020
Published: 2020

50. Complexity Guarantees for Polyak Steps with Momentum

Author: Barr��, Mathieu, Taylor, Adrien, d'Aspremont, Alexandre, 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), 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), 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), Mathieu Barré acknowledges support from an AMX fellowship. Adrien Taylor acknowledges support from the European Research Council (grant SEQUOIA 724063). Alexandre d’Aspremont acknowledges support from the ML & Optimisation joint research initiative with the fonds AXA pour la recherche and Kamet Ventures, as well as a Google focused award., ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), 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), Barré, Mathieu, PaRis Artificial Intelligence Research InstitutE - - PRAIRIE2019 - ANR-19-P3IA-0001 - P3IA - VALID, 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, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)
Subjects: FOS: Computer and information sciences, Optimization and Control (math.OC), Statistics - Machine Learning, FOS: Mathematics, Machine Learning (stat.ML), [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Numerical Analysis (math.NA), Mathematics - Numerical Analysis, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Mathematics::Geometric Topology
Abstract: In smooth strongly convex optimization, knowledge of the strong convexity parameter is critical for obtaining simple methods with accelerated rates. In this work, we study a class of methods, based on Polyak steps, where this knowledge is substituted by that of the optimal value, $f_*$. We first show slightly improved convergence bounds than previously known for the classical case of simple gradient descent with Polyak steps, we then derive an accelerated gradient method with Polyak steps and momentum, along with convergence guarantees., Accepted to COLT2020
Published: 2020

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

120 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