Egor Gladin - “Vaidya’s cutting plane method for stochastic optimization in small dimension“

The talk “Vaidya’s cutting plane method for stochastic optimization in small dimension“ by Egor Gladin on the Moscow Conference on Combinatorics and Applications at MIPT. Annotation: The article considers minimization of the expectation of convex function. Problems of this type often arise in machine learning and a number of other applications. In practice, stochastic gradient descent (SGD) and similar procedures are often used to solve such problems. We propose to use Vaidya’s cutting plane method with minibatching, which converges linearly and hence requires significantly less iterations than SGD. This is verified by our experiments, which are publicly available. The algorithm does not require neither smoothness nor strong convexity of target function to achieve linear convergence. We prove that the method arrives at approximate solution with given probability when using minibatches of size proportional to the desired precision to the power -2. This enables efficient parallel exe