OPTML++

Suvrit Sra (suvrit@mit.edu)

Introduction

Welcome to OPTML++! This is the homepage for our research seminar plus reading group on: Optimization for Machine Learning (the (++) stands for related areas (statistics, signal processing, computer vision, robotics, information theory, among others).

OPTML++ covers topics from convex, nonconvex, continuous and combinatorial optimization. This reading group is a mixture of a research seminar, a journal club, and a problem solving group.

Organization

We will start meeting beginning Sep 15, 2016

Next Meeting: 4PM; Location: 32-D677 on Oct 06, 2016.

The admin, announcements, and discussion related to this group are on this mailing list. Please subscribe.

Schedule

Date	Topic	Links
15 Sep 2016	Introduction, Crash-course in first-order methods, Plans	Suvrit
22 Sep 2016	Nonconvex finite-sum problems	Suvrit
29 Sep 2016	Generalization, implicit generalization SGD	Lorenzo
06 Oct 2016	Gradient descent converges to minimizers	Hongyi
13 Oct 2016	Distributed Newton Method	Rasul
20 Oct 2016	Fast sampling from strongly Rayleigh measures	Chengtao

Papers, grouped for presentation

Expand All Collapse All

STOCHASTIC GRADIENT METHODS
- Nonconvex finite-sum problems:
  - Reddi et al. (NIPS '16). Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
  - Reddi et al. (Allerton 2016). Stochastic Frank-Wolfe Methods for Nonconvex Optimization.
- Stochastic variance reduction, more general setups:
  - A. Defazio (NIPS '16). A Simple Practical Accelerated Method for Finite Sums
  - Balamurugan, Bach (NIPS '16). Stochastic Variance Reduction Methods for Saddle-Point Problems
- Without replacement SGD:
  - O. Shamir (NIPS '16). Without-Replacement Sampling for Stochastic Gradient Methods
  - Recht, Re (2016). Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences
  - Gürbüzbalaban, Ozdaglar, Parrilo (2015). Why Random Reshuffling Beats Stochastic Gradient Descent
- SGD with second-order information:
  - Agarwal, Bullins, Hazan (Mar 2016). Second order stochastic optimization in linear time
- Lei, Jordan (2016). Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
- Other ideas:
  - Namkoong, Duchi (NIPS '16). Stochastic Gradient Methods for Distributionally Robust Optimization with f-divergences
  - Lian et al. (NIPS '16). A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order
OPTIMIZATION I
- Scieur, D'Aspremont, Bach (NIPS '16). Regularized Nonlinear Acceleration
- Lee et al. (COLT '16). Gradient Descent only Converges to Minimizers
- K. Kawaguchi (NIPS '16). Deep Learning without Poor Local Minima
- Semidefinite programming:
  - Boumal, Voroninski, Bandeira (NIPS '16). The non-convex Burer-Monteiro approach works on smooth semidefinite programs
- Gaussian mixture models:
  - Jin et al (NIPS '16). Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
SAMPLING I
- Strongly Rayleigh:
  - Li, Jegelka, Sra (NIPS '16; arXiv). Fast sampling for Strongly Rayleigh Measures
  - Anari, Gharan, Rezaei (COLT '16). Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh distributions and Determinantal Point Processes
- De Sa, Re, Olukotun (ICML 2016). Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling
OPTIMIZATION II
- Frank-Wolfe methods:
  - D. Garber (NIPS '16). Faster Projection-free Convex Optimization over the Spectrahedron
- Allen-Zhu, Hazan (NIPS '16). Optimal Black-Box Reductions Between Optimization Objectives
- Hayashi, Yoshida (NIPS '16). Minimizing Quadratic Functions in Constant Time
- Stochastic eigenvector methods:
  - O. Shamir (ICML 2016). Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
  - Garber et al. (ICML 2016). Faster Eigenvector Computation via Shift-and-Invert Preconditioning
GENERALIZATION AND COMPLEXITY
- Lin, Rosasco (NIPS '16). Optimal Learning for Multi-pass Stochastic Gradient Methods
- Arjevani, Shamir (NIPS '16). Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
- Arjevani, Shalev-Shwartz, Shamir (2016). On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
- Feldman (NIPS '16). Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back
- Dieuleveut, Flammarion, Bach (2016). Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression
SAMPLING II
- Lee, Vempala (2016). Geodesic Walks on Polytopes
- Castro-Villarreal (2010). Brownian motion meets Riemann curvature
- Mangoubi, Smith (2016). Rapid Mixing of Geodesic Walks on Manifolds with Positive Curvature
POSSIBLE, UNSORTED
- Zhang et al (Oct 2016). Convexified Convolutional Neural Networks
- Wang et al (Oct 2016). Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
- Montanari (Mar 2016). A Grothendieck-type inequality for local maxima
- Park et al. Provable non-convex projected gradient descent for a class of constrained matrix optimization problems
- L. Vegh (2016). Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
- Mathkar, Borkar (2016). Nonlinear Gossip
- Looz et al. (2016). Generating massive complex networks with hyperbolic geometry faster in practice
- Gheche, Chierchia, Pesquet (2016). Proximity Operators of Discrete Information Divergences
- Wang et al (2016). Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
- Gambhir, Stathopoulos, Orginos (2016). Deflation as a Method of Variance Reduction for Estimating the Trace of a Matrix Inverse
- Wu, Romero, Stathopoulos (2016). PRIMME_SVDS: A High-Performance Preconditioned SVD Solver for Accurate Large-Scale Computations
- Zhang, White (2016). On the Convergence of GMRES-Accelerated ADMM in O(κ1/4logε−1) Iterations for Quadratic Objectives
- Lahiri, Gao, Ganguli (2016). Random projections of random manifolds
- Hyland, Rätsch Learning Unitary Operators with Help From u(n)
- Yu, Neely (2016). A Primal-Dual Type Algorithm with the O(1/t) Convergence Rate for Large Scale Constrained Convex Programs