资源论文Variance Reduction for Matrix Games

Variance Reduction for Matrix Games

2020-02-20 | |  81 |   73 |   0

Abstract

We present a randomized primal-dual algorithm thatpsolves the problem 图片.png to additive error 图片.png in time 图片.png for matrix A with larger dimension n and nnz(A) nonzero p entries. This improves the best known exact gradient methods by a factor of 图片.png and is faster p than fully stochastic gradient methods in the accurate and/or sparse regime 图片.png Our results hold for x, y in the simplex (matrix games, linear programming) and for x in an 图片.png ball and y in the simplex (perceptron / SVM, minimum enclosing ball). Our algorithm combines the Nemirovski’s “conceptual prox-method” and a novel reduced-variance gradient estimator based on “sampling from the difference” between the current iterate and a reference point.

上一篇:Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs

下一篇:Learning to Learn via Self-Critique

用户评价
全部评价

热门资源

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Hierarchical Task...

    We extend hierarchical task network planning wi...

  • Shape-based Autom...

    We present an algorithm for automatic detection...