Reproduce “On the Convergence of Bound Optimization Algorithms” on OpenResearch

About this paper

Ruslan R Salakhutdinov, Sam T Roweis, Zoubin Ghahramani

Fitting logistic regression with iterative scaling can guarantee objective improvement yet still make slow progress. The authors inspect how bound updates reshape steps and test changing feature geometry. In a synthetic experiment with N=2,000 and d=2, translating positive features reached the same maximum-likelihood solution in almost 12-fold fewer iterations than naive iterative scaling, not 12-fold faster runtime.

Key insights

• The local convergence rate of a bound optimization algorithm is directly determined by the eigenvalues of a 'convergence rate matrix', which can be derived from the curvature of the objective and bound functions.
• BO algorithms can exhibit fast, quasi-Newton-like convergence when these eigenvalues are small (e.g., low 'missing information' in EM) and slow, first-order convergence when eigenvalues approach unity (e.g., high 'missing information').
• Simple, problem-specific input data preprocessing, such as translating feature vectors or decorrelating them, can significantly improve convergence speed without changing the final optimum.

Summary by alphaXiv.