Mixed Optimization for Smooth Functions

Mehrdad Mahdavi, Lijun Zhang, Rong JinNeurIPS 2013 · OpenReview

Introduction

In the realm of convex optimization, practitioners often face a frustrating trade-off between computational cost per iteration and overall convergence speed. Batch Gradient Descent (GD) uses the entire dataset to calculate gradients, converging quickly in terms of iterations (achieving $O(1/T^2)$ for smooth functions using acceleration). However, each iteration is prohibitively expensive for large-scale datasets. Conversely, Stochastic Gradient Descent (SGD) processes one random sample per iteration, making it computationally cheap. Yet, the inherent "noise" from sampling restricts its convergence to a slow $O(1/\sqrt{T})$ rate, even for smooth functions, because the variance of the stochastic gradient does not vanish near the optimum.

This paper introduces Mixed Optimization, a hybrid approach designed to exploit the smoothness of a loss function to accelerate stochastic optimization without incurring the full computational penalty of batch GD.

The Mixed Optimization Framework

The authors propose a novel setup that bridges the gap between fast-but-noisy SGD and slow-but-precise Batch GD. By supplementing standard stochastic updates with a logarithmic number of full gradient calls, the proposed algorithm achieves an $O(1/T)$ convergence rate for smooth functions.

Comparison of convergence rates and oracle complexities for Full GD, SGD, and Mixed Optimization.

As shown in the comparison table, Mixed Optimization significantly improves upon the standard stochastic rate of $O(1/\sqrt{T})$ while requiring only $O(\log T)$ calls to the expensive full gradient oracle.

The MIXEDGRAD Algorithm

To realize this framework, the authors introduce MIXEDGRAD, an epoch-based algorithm that utilizes two distinct "oracles":

  1. The Full Gradient Oracle ($\mathcal{O}_f$): Called only once at the beginning of each epoch to provide a "global anchor" for the gradient.
  2. The Stochastic Oracle ($\mathcal{O}_s$): Called during the iterations within an epoch to perform computationally cheap updates.

Variance Reduction via Smoothness

The core innovation of MIXEDGRAD lies in its handling of the stochastic gradient. Instead of relying on a raw stochastic gradient $\nabla g_i(w)$, it employs a variance-reduced gradient. It calculates the difference between the current stochastic gradient and the stochastic gradient at the "anchor" point (established at the start of the epoch), and then adds the full gradient from that anchor point.

Mathematically, as the algorithm converges and the search domain shrinks across epochs, the difference between these gradients approaches zero. This mechanism effectively "extinguishes" the stochastic noise that typically bottlenecks SGD. Furthermore, MIXEDGRAD introduces a temporary $\ell_2$ regularizer that gradually decreases, ensuring the sub-problems in each epoch are strongly convex and easier to solve.

Key Theoretical Results

This work is a theoretical machine learning paper focused on proving convergence bounds and algorithmic complexity; thus, it relies on rigorous mathematical proofs rather than empirical benchmarks.

The key theoretical insights include:

  • Improved Convergence Rate: The algorithm achieves an optimization error of $O(1/T)$. This is a substantial improvement over the $O(1/\sqrt{T})$ rate of standard SGD for smooth functions, effectively allowing smooth (but not necessarily strongly convex) functions to be optimized as quickly as strongly convex ones in a stochastic setting.
  • Logarithmic Oracle Efficiency: The paper proves that to reach this error over $T$ total iterations, the algorithm requires $O(T)$ calls to the stochastic oracle but only $O(\ln T)$ calls to the full gradient oracle.
  • Exploiting Smoothness: In standard stochastic optimization, smoothness does not inherently improve the convergence rate. MIXEDGRAD changes this paradigm by actively using smoothness to bound the variance of the modified stochastic gradients.

Limitations and Future Directions

While the theoretical foundation is robust, the authors acknowledge several areas for future exploration:

  • Empirical Validation: The paper lacks empirical experiments to demonstrate how MIXEDGRAD performs on real-world datasets compared to other variance-reduction methods like SVRG or SAG.
  • Nesterov Acceleration: While MIXEDGRAD reaches $O(1/T)$, full batch GD can reach $O(1/T^2)$ using Nesterov acceleration. A natural next step is determining if a "Mixed" approach can be accelerated to achieve that $O(1/T^2)$ rate.
  • Distributed Computing: The authors suggest this model is highly suitable for distributed settings, where full gradients are expensive due to communication latency, but leave the formal exploration of distributed MIXEDGRAD for future research.
  • Strong Convexity: The current work focuses on smooth convex functions. Future research will investigate whether linear convergence rates can be achieved if the function is also strongly convex.

Summary updated

Abstract

It is well known that the optimal convergence rate for stochastic optimization of smooth functions is $[O(1/\sqrt{T})]$, which is same as stochastic optimization of Lipschitz continuous convex functions. This is in contrast to optimizing smooth functions using full gradients, which yields a convergence rate of $[O(1/T^2)]$. In this work, we consider a new setup for optimizing smooth functions, termed as {\bf Mixed Optimization}, which allows to access both a stochastic oracle and a full gradient oracle. Our goal is to significantly improve the convergence rate of stochastic optimization of smooth functions by having an additional small number of accesses to the full gradient oracle. We show that, with an $[O(\ln T)]$ calls to the full gradient oracle and an $O(T)$ calls to the stochastic oracle, the proposed mixed optimization algorithm is able to achieve an optimization error of $[O(1/T)]$.
BibTeX
@inproceedings{mahdavi2013mixed,
  author = {Mehrdad Mahdavi and Lijun Zhang and Rong Jin},
  title = {{Mixed Optimization for Smooth Functions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=H1-MK_ZdZr},
}
Figure