Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters

• URL: http://arxiv.org/abs/2008.11824v1
• Date: Wed, 26 Aug 2020 21:15:18 GMT
• Title: Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Authors: Filip Hanzely
• Abstract summary: Key problems in machine learning and data science are routinely modeled as optimization problems and solved via optimization algorithms. With the increase of the volume of data and the size and complexity of the statistical models used to formulate these often ill-conditioned optimization tasks, there is a need for new efficient algorithms able to cope with these challenges. In this thesis, we deal with each of these sources of difficulty in a different way. To efficiently address the big data issue, we develop new methods which in each iteration examine a small random subset of the training data only. To handle the big model issue, we develop methods which in each iteration update
• Score: 10.279748604797911
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many key problems in machine learning and data science are routinely modeled as optimization problems and solved via optimization algorithms. With the increase of the volume of data and the size and complexity of the statistical models used to formulate these often ill-conditioned optimization tasks, there is a need for new efficient algorithms able to cope with these challenges. In this thesis, we deal with each of these sources of difficulty in a different way. To efficiently address the big data issue, we develop new methods which in each iteration examine a small random subset of the training data only. To handle the big model issue, we develop methods which in each iteration update a random subset of the model parameters only. Finally, to deal with ill-conditioned problems, we devise methods that incorporate either higher-order information or Nesterov's acceleration/momentum. In all cases, randomness is viewed as a powerful algorithmic tool that we tune, both in theory and in experiments, to achieve the best results. Our algorithms have their primary application in training supervised machine learning models via regularized empirical risk minimization, which is the dominant paradigm for training such models. However, due to their generality, our methods can be applied in many other fields, including but not limited to data science, engineering, scientific computing, and statistics.

Related papers

• PETScML: Second-order solvers for training regression problems in Scientific Machine Learning [0.22499166814992438]
  In recent years, we have witnessed the emergence of scientific machine learning as a data-driven tool for the analysis. We introduce a software built on top of the Portable and Extensible Toolkit for Scientific computation to bridge the gap between deep-learning software and conventional machine-learning techniques.
  arXiv  Detail & Related papers  (2024-03-18T18:59:42Z)
• Learning of networked spreading models from noisy and incomplete data [7.669018800404791]
  We introduce a universal learning method based on scalable dynamic message-passing technique. The algorithm leverages available prior knowledge on the model and on the data, and reconstructs both network structure and parameters of a spreading model. We show that a linear computational complexity of the method with the key model parameters makes the algorithm scalable to large network instances.
  arXiv  Detail & Related papers  (2023-12-20T13:12:47Z)
• Adaptive Optimization Algorithms for Machine Learning [0.0]
  Machine learning assumes a pivotal role in our data-driven world. This thesis contributes novel insights, introduces new algorithms with improved convergence guarantees, and improves analyses of popular practical algorithms.
  arXiv  Detail & Related papers  (2023-11-16T21:22:47Z)
• Applications of Nature-Inspired Metaheuristic Algorithms for Tackling Optimization Problems Across Disciplines [12.664160352147293]
  This paper demonstrates the usefulness of nature-inspired metaheuristic algorithms for solving a variety of challenging optimization problems in statistics. The main goal of this paper is to show a typical metaheuristic algorithmi, like CSO-MA, is efficient for tackling many different types of optimization problems in statistics.
  arXiv  Detail & Related papers  (2023-08-08T16:41:33Z)
• Improved Distribution Matching for Dataset Condensation [91.55972945798531]
  We propose a novel dataset condensation method based on distribution matching. Our simple yet effective method outperforms most previous optimization-oriented methods with much fewer computational resources.
  arXiv  Detail & Related papers  (2023-07-19T04:07:33Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• Algorithms that Approximate Data Removal: New Results and Limitations [2.6905021039717987]
  We study the problem of deleting user data from machine learning models trained using empirical risk minimization. We develop an online unlearning algorithm that is both computationally and memory efficient.
  arXiv  Detail & Related papers  (2022-09-25T17:20:33Z)
• Conservative Objective Models for Effective Offline Model-Based Optimization [78.19085445065845]
  Computational design problems arise in a number of settings, from synthetic biology to computer architectures. We propose a method that learns a model of the objective function that lower bounds the actual value of the ground-truth objective on out-of-distribution inputs. COMs are simple to implement and outperform a number of existing methods on a wide range of MBO problems.
  arXiv  Detail & Related papers  (2021-07-14T17:55:28Z)
• Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning [93.1435980666675]
  We show how optimistic exploration can be easily combined with state-of-the-art reinforcement learning algorithms. Our experiments demonstrate that optimistic exploration significantly speeds-up learning when there are penalties on actions.
  arXiv  Detail & Related papers  (2020-06-15T18:37:38Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.