Algorithms in varied fields use the idea of maintaining a distribution over certain set and multiplicative update rule to iteratively change these weights.Their analyses are usually very similar rely on an exponential potential function.In this survey we present simple meta-algorithm that unifies many disparate algorithms derives them as instantiations meta-algorithm.We feel since its analysis so simple, applications broad, it should be standard part courses, like "divide conquer."

We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan extended et al. which achieve almost the same wealth as best constant-rebalanced portfolio determined in hindsight. These are to combine optimal logarithmic regret bounds with efficient deterministic computability. They based on Newton method for offline optimization which, unlike previous approaches, exploits second order information. After analyzing algorithm using potential function introduced Hazan,...

We design a non-convex second-order optimization algorithm that is guaranteed to return an approximate local minimum in time which scales linearly the underlying dimension and number of training examples. The complexity our find even faster than gradient descent critical point. Our applies general class problems including neural network other objectives arising machine learning.

The quest for a polynomial-time approximation scheme (PTAS) Nash equilibrium in two-player game, which emerged as major open question algorithmic game theory, seeks to circumvent the PPAD-completeness of finding an (exact) by approximate equilibrium. closely related problem maximizing certain objective, such social welfare, was shown be NP-hard [Gilboa and Zemel, Games Econom. Behav., 1 (1989), pp. 80–93]. However, this NP-hardness is unlikely extend equilibria, since latter admits...

Conventional wisdom in deep learning states that increasing depth improves expressiveness but complicates optimization. This paper suggests that, sometimes, can speed up The effect of on optimization is decoupled from by focusing settings where additional layers amount to overparameterization - linear neural networks, a well-studied model. Theoretical analysis, as well experiments, show here acts preconditioner which may accelerate convergence. Even simple convex problems such regression...

Suppose an agent is in a (possibly unknown) Markov Decision Process the absence of reward signal, what might we hope that can efficiently learn to do? This work studies broad class objectives are defined solely as functions state-visitation frequencies induced by how behaves. For example, one natural, intrinsically defined, objective problem for policy which induces distribution over state space uniform possible, be measured entropic sense. We provide efficient algorithm optimize such...

Semidefinite programming (SDP) relaxations appear in many recent approximation algorithms but the only general technique for solving such SDP is via interior point methods. We use a Lagrangian-relaxation based (modified from papers of Plotkin, Shmoys, and Tardos (PST), Klein Lu) to derive faster approximately several families relaxations. The are upon some improvements PST ideas - which lead new results even their framework as well approximate eigenvalue computations by using random sampling.

We study online learning in an oblivious changing environment. The standard measure of regret bounds the difference between cost learner and best decision hindsight. Hence, minimizing algorithms tend to converge static optimum, clearly a suboptimal behavior environments. On other hand, various metrics proposed strengthen allow for more dynamic produce inefficient algorithms.We propose different performance metric which strengthens measures with respect comparator. then describe series...