Faster Optimization on Sparse Graphs via Neural Reparametrization

• URL: http://arxiv.org/abs/2205.13624v1
• Date: Thu, 26 May 2022 20:52:18 GMT
• Title: Faster Optimization on Sparse Graphs via Neural Reparametrization
• Authors: Nima Dehmamy, Csaba Both, Jianzhi Long, Rose Yu
• Abstract summary: We show that a graph neural network can implement an efficient Quasi-Newton method that can speed up optimization by a factor of 10-100x. We show the application of our method on scientifically relevant problems including heat diffusion, synchronization and persistent homology.
• Score: 15.275428333269453
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In mathematical optimization, second-order Newton's methods generally converge faster than first-order methods, but they require the inverse of the Hessian, hence are computationally expensive. However, we discover that on sparse graphs, graph neural networks (GNN) can implement an efficient Quasi-Newton method that can speed up optimization by a factor of 10-100x. Our method, neural reparametrization, modifies the optimization parameters as the output of a GNN to reshape the optimization landscape. Using a precomputed Hessian as the propagation rule, the GNN can effectively utilize the second-order information, reaching a similar effect as adaptive gradient methods. As our method solves optimization through architecture design, it can be used in conjunction with any optimizers such as Adam and RMSProp. We show the application of our method on scientifically relevant problems including heat diffusion, synchronization and persistent homology.

Related papers

• Regularized Gauss-Newton for Optimizing Overparameterized Neural Networks [2.0072624123275533]
  The generalized Gauss-Newton (GGN) optimization method incorporates curvature estimates into its solution steps. This work studies a GGN method for optimizing a two-layer neural network with explicit regularization.
  arXiv  Detail & Related papers  (2024-04-23T10:02:22Z)
• ELRA: Exponential learning rate adaption gradient descent optimization method [83.88591755871734]
  We present a novel, fast (exponential rate), ab initio (hyper-free) gradient based adaption. The main idea of the method is to adapt the $alpha by situational awareness. It can be applied to problems of any dimensions n and scales only linearly.
  arXiv  Detail & Related papers  (2023-09-12T14:36:13Z)
• How Does Adaptive Optimization Impact Local Neural Network Geometry? [32.32593743852949]
  We argue that in the context of neural network optimization, this traditional viewpoint is insufficient. We show that adaptive methods such as Adam bias the trajectories towards regions where one might expect faster convergence.
  arXiv  Detail & Related papers  (2022-11-04T04:05:57Z)
• An Empirical Evaluation of Zeroth-Order Optimization Methods on AI-driven Molecule Optimization [78.36413169647408]
  We study the effectiveness of various ZO optimization methods for optimizing molecular objectives. We show the advantages of ZO sign-based gradient descent (ZO-signGD) We demonstrate the potential effectiveness of ZO optimization methods on widely used benchmark tasks from the Guacamol suite.
  arXiv  Detail & Related papers  (2022-10-27T01:58:10Z)
• Learning to Optimize Quasi-Newton Methods [22.504971951262004]
  This paper introduces a novel machine learning called LODO, which tries to online meta-learn the best preconditioner during optimization. Unlike other L2O methods, LODO does not require any meta-training on a training task distribution. We show that our gradient approximates the inverse Hessian in noisy loss landscapes and is capable of representing a wide range of inverse Hessians.
  arXiv  Detail & Related papers  (2022-10-11T03:47:14Z)
• Alternately Optimized Graph Neural Networks [33.98939289745346]
  We propose a new optimization framework for semi-supervised learning on graphs. The proposed framework can be conveniently solved by the alternating optimization algorithms, resulting in significantly improved efficiency.
  arXiv  Detail & Related papers  (2022-06-08T01:50:08Z)
• Channel-Directed Gradients for Optimization of Convolutional Neural Networks [50.34913837546743]
  We introduce optimization methods for convolutional neural networks that can be used to improve existing gradient-based optimization in terms of generalization error. We show that defining the gradients along the output channel direction leads to a performance boost, while other directions can be detrimental.
  arXiv  Detail & Related papers  (2020-08-25T00:44:09Z)
• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning [95.85269649177336]
  ZO optimization iteratively performs three major steps: gradient estimation, descent direction, and solution update. We demonstrate promising applications of ZO optimization, such as evaluating and generating explanations from black-box deep learning models, and efficient online sensor management.
  arXiv  Detail & Related papers  (2020-06-11T06:50:35Z)
• Global Optimization of Gaussian processes [52.77024349608834]
  We propose a reduced-space formulation with trained Gaussian processes trained on few data points. The approach also leads to significantly smaller and computationally cheaper sub solver for lower bounding. In total, we reduce time convergence by orders of orders of the proposed method.
  arXiv  Detail & Related papers  (2020-05-21T20:59:11Z)
• Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
  Self-directed Online Learning Optimization integrates Deep Neural Network (DNN) with Finite Element Method (FEM) calculations. Our algorithm was tested by four types of problems including compliance minimization, fluid-structure optimization, heat transfer enhancement and truss optimization. It reduced the computational time by 2 5 orders of magnitude compared with directly using methods, and outperformed all state-of-the-art algorithms tested in our experiments.
  arXiv  Detail & Related papers  (2020-02-04T20:00:28Z)

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.