1期

最新文章

• Stochastic quasi-gradient methods: variance reduction via Jacobian sketching AI翻译
  作者：Gower, Robert M.; Richtarik, Peter; Bach, Francis
  作者单位：IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom Paris; King Abdullah University of Science & Technology; University of Edinburgh; Moscow Institute of Physics & Technology; Inria; Universite PSL; Ecole Normale Superieure (ENS)
  摘要：We develop a new family of variance reduced stochastic gradient descent methods for minimizing the average of a very large number of smooth functions. Our method-JacSketch-is motivated by novel developments in randomized numerical linear algebra, and operates by maintaining a stochastic estimate of a Jacobian matrix composed of the gradients of individual functions. In each iteration, JacSketch efficiently updates the Jacobian matrix by first obtaining a random linear measurement of the true J...
• Box-total dual integrality, box-integrality, and equimodular matrices AI翻译
  作者：Chervet, Patrick; Grappe, Roland; Robert, Louis-Hadrien
  作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); University of Geneva
  摘要：Box-totally dual integral (box-TDI) polyhedra are polyhedra described by systems which yield strong min-max relations. We characterize them in several ways, involving the notions of principal box-integer polyhedra and equimodular matrices. A polyhedron is box-integer if its intersection with any integer box {l <= x <= u} is integer. We define principally box-integer polyhedra to be the polyhedra P such that kP is box-integer whenever kP is integer. A rational r x n matrix is equimodular if it ...
• Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion AI翻译
  作者：Zhang, Richard Y.; Lavaei, Javad
  作者单位：University of California System; University of California Berkeley; University of Illinois System; University of Illinois Urbana-Champaign
  摘要：Clique tree conversion solves large-scale semidefinite programs by splitting an nxn matrix variable into up to n smaller matrix variables, each representing a principal submatrix of up to omega x omega. Its fundamental weakness is the need to introduce overlap constraints that enforce agreement between different matrix variables, because these can result in dense coupling. In this paper, we show that by dualizing the clique tree conversion, the coupling due to the overlap constraints is guaran...