OPT2017

TBA

In this talk, we analyze a voting model based on random preferences of participants. Each voter can choose a party with certain probability, which depends on the divergence between his personal preferences and the position of the party. Our model represents a rare example of a community detection (or, clustering) model with unique equilibrium solution. This is achieved by allowing the flexible positions for the parties (centers of clusters). We propose an efficient algorithm for finding the equilibrium state with linear rate of convergence. It can be interpreted as an alternating minimization scheme. Again, this is a rare example when such a scheme has provable global rate of convergence.

TBA

We consider large linear and nonlinear fixed point problems, and solution with proximal algorithms. We show that there is a close connection between two seemingly different types of methods from distinct fields: 1) Proximal iterations for linear systems of equations, which are prominent in numerical analysis and convex optimization, and 2) Temporal difference (TD) type methods, such as TD(lambda), LSTD(lambda), and LSPE(lambda), which are central in simulation-based approximate dynamic programming/reinforcement learning (DP/RL), and its recent prominent successes in large-scale game contexts, among others. One benefit of this connection is a new and simple way to accelerate the standard proximal algorithm by extrapolation towards the TD iteration, which generically has a faster convergence rate. Another benefit is the potential integration into the proximal algorithmic context of several new ideas that have emerged in the DP/RL context. A third benefit is that insights and analysis from proximal algorithms can be brought to bear on the enhancement of TD methods. The linear fixed point methodology can be extended to nonlinear fixed point problems involving a contraction, thus providing guaranteed and potentially substantial acceleration of the proximal and forward backward splitting algorithms at no extra cost. Moreover, the connection of proximal and TD methods can be extended to nonlinear (nondifferentiable) fixed point problems through new proximal-like algorithms that involve successive linearization, similar to policy iteration in DP.

TBA