Quantization-Based Optimization: Alternative Stochastic Approximation of Global Optimization
In this study, we propose a global optimization algorithm based on quantizing the energy level of an objective function in an NP-hard problem. According to the white noise hypothesis for a quantization error with a dense and uniform distribution, we can regard the quantization error as i.i.d. white noise. From stochastic analysis, the proposed algorithm converges weakly only under conditions satisfying Lipschitz continuity, instead of local convergence properties such as the Hessian constraint of the objective function. This shows that the proposed algorithm ensures global optimization by Laplace's condition. Numerical experiments show that the proposed algorithm outperforms conventional learning methods in solving NP-hard optimization problems such as the traveling salesman problem.
Code (0)
등록된 구현이 없습니다.
Tasks
global-optimizationQuantizationTraveling Salesman ProblemSimilar Papers 제목 키워드 기반
Quantization goes Polynomial
Quantization algorithms have been successfully adopted to option pricing in finance thanks to the high convergence rate of the numerical approximation. In particular, very recently, recursive marginal quantization has be…
QuantizationQuantization-based Optimization with Perspective of Quantum Mechanics
Statistical and stochastic analysis based on thermodynamics has been the main analysis framework for stochastic global optimization. Recently, appearing quantum annealing or quantum tunneling algorithm for global optimiz…
global-optimizationQuantizationvalidQuantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry
We study distributed optimization with stochastic gradients and finite-bit communication modeled by random (unbiased) quantization. We propose q-PDGD, a quantized stochastic primal-dual method, and analyze it under relax…
Distributed OptimizationStochastic Gradient Langevin Dynamics Based on Quantization with Increasing Resolution
Stochastic learning dynamics based on Langevin or Levy stochastic differential equations (SDEs) in deep neural networks control the variance of noise by varying the size of the mini-batch or directly those of injecting n…
QuantizationQuantization enabled Privacy Protection in Decentralized Stochastic Optimization
By enabling multiple agents to cooperatively solve a global optimization problem in the absence of a central coordinator, decentralized stochastic optimization is gaining increasing attention in areas as diverse as machi…
global-optimizationQuantizationStochastic Optimization