Current Location:home > Browse

1. chinaXiv:202005.00043 [pdf]

DEED: A general quantization scheme for saving bits in communication

Tian Ye; Peijun Xiao; Ruoyu Sun
Subjects: Mathematics >> Control and Optimization.

Quantization is a popular technique to reduce communication in distributed optimization. Motivated by the classical work on inexact gradient descent (GD) \cite{bertsekas2000gradient}, we provide a general convergence analysis framework for inexact GD that is tailored for quantization schemes. We also propose a quantization scheme Double Encoding and Error Diminishing (DEED). DEED can achieve small communication complexity in three settings: frequent-communication large-memory, frequent-communication small-memory, and infrequent-communication (e.g. federated learning). More specifically, in the frequent-communication large-memory setting, DEED can be easily combined with Nesterov's method, so that the total number of bits required is $ \tilde{O}( \sqrt{\kappa} \log 1/\epsilon )$, where $\tilde{O}$ hides numerical constant and $\log \kappa $ factors. In the frequent-communication small-memory setting, DEED combined with SGD only requires $\tilde{O}( \kappa \log 1/\epsilon)$ number of bits in the interpolation regime. In the infrequent communication setting, DEED combined with Federated averaging requires a smaller total number of bits than Federated Averaging. All these algorithms converge at the same rate as their non-quantized versions, while using a smaller number of bits.

submitted time 2020-06-16 Hits8053Downloads877 Comment 0

2. chinaXiv:201909.00015 [pdf]

Analytical expressions of copositivity for 4th order symmetric tensors and applications

宋义生; 祁力群
Subjects: Mathematics >> Control and Optimization.

In particle physics, scalar potentials have to be bounded from below in order for the physics to make sense. The precise expressions of checking lower bound of scalar potentials are essential, which is an analytical expression of checking copositivity and positive definiteness of tensors given by such scalar potentials. Because the tensors given by general scalar potential are 4th order and symmetric, our work mainly focuses on finding precise expressions to test copositivity and positive definiteness of 4th order tensors in this paper. First of all, an analytically sufficient and necessary condition of positive definiteness is provided for 4th order 2 dimensional symmetric tensors. For 4th order 3 dimensional symmetric tensors, we give two analytically sufficient conditions of (strictly) cpositivity by using proof technique of reducing orders or dimensions of such a tensor. Furthermore, an analytically sufficient and necessary condition of copositivity is showed for 4th order 2 dimensional symmetric tensors. We also give several distinctly analytically sufficient conditions of (strict) copositivity for 4th order 2 dimensional symmetric tensors. Finally, we apply these results to check lower bound of scalar potentials, and to present analytical vacuum stability conditions for potentials of two real scalar fields and the Higgs boson.

submitted time 2019-08-30 Hits12840Downloads716 Comment 0

3. chinaXiv:201707.00007 [pdf]

B tensors and tensor complementarity problems

Yisheng Song; Wei Mei
Subjects: Mathematics >> Control and Optimization.

In this paper, one of our main purposes is to prove the boundedness of solution set of tensor complementarity problem with B tensor such that the specific bounds only depend on the structural properties of tensor. To achieve this purpose, firstly, we present that each B tensor is strictly semi-positive and each B$_0$ tensor is semi-positive. Subsequencely, the strictly lower and upper bounds of different operator norms are given for two positively homogeneous operators defined by B tensor. Finally, with the help of the upper bounds of different operator norms, we show the strcitly lower bound of solution set of tensor complementarity problem with B tensor. Furthermore, the upper bounds of spectral radius and $E$-spectral radius of B (B$_0$) tensor are obtained, respectively, which achieves our another objective. In particular, such the upper bounds only depend on the principal diagonal entries of tensors.

submitted time 2017-07-25 Hits2745Downloads1506 Comment 0

4. chinaXiv:201608.00201 [pdf]

Conic optimization and complementarity problems V2

S. Z. N?emeth; Guohan Zhang
Subjects: Mathematics >> Control and Optimization.

Although the Karush-Kuhn-Tucker conditions suggest a connection between a conic optimization problem and a complementarity problem, it is difficult to find an accessible explicit form of this relationship in the literature. This note will present such a relationship.

submitted time 2016-12-16 Hits2541Downloads969 Comment 0

5. chinaXiv:201608.00202 [pdf]

Positive operators of Extended Lorentz cones

S. Z. N?emeth; Guohan Zhang
Subjects: Mathematics >> Control and Optimization.

In this paper necessary conditions and sufficient conditions are given for a linear operator to be a positive operators of an Extended Lorentz cone. Similarities and differences with the positive operators of Lorentz cones are investigated.

submitted time 2016-08-30 Hits2370Downloads1209 Comment 0

6. chinaXiv:201607.00035 [pdf]

An efficient m-step Levenberg-Marquardt method for nonlinear equations

Chen, Liang; Ma, Yanfang; Su, Chencheng
Subjects: Mathematics >> Control and Optimization.

In this paper, we construct and analyze an efficient m-step Levenberg-Marquardt method for nonlinear equations. The main advantage of this method is that the m-step LM method could save more Jacobian calculations with frozen $(J_k^TJ_k+\lambda_kI)^{-1}J_k^T$ at every iteration. Under the local error bound condition which is weaker than nonsingularity, the m-step LM method has been proved to have $(m+1)$th convergence order. The global convergence has also been given by trust region technique. Numerical results show that the m-step LM method is efficient and could save many calculations of the Jacobian especially for large scale problems.

submitted time 2016-07-11 Hits2563Downloads1096 Comment 0

  [1 Pages/ 6 Totals]