  Model training algorithms which observe a small portion of the training set
in each computational step are ubiquitous in practical machine learning, and
include both stochastic and online optimization methods. In the vast majority
of cases, such algorithms typically observe the training samples via the
gradients of the cost functions the samples incur. Thus, these methods exploit
are the slope of the cost functions via their first-order approximations. To
address limitations of gradient-based methods, such as sensitivity to step-size
choice in the stochastic setting, or inability to use small function
variability in the online setting, several streams of research attempt to
exploit more information about the cost functions than just their gradients via
the well-known proximal operators. However, implementing such methods in
practice poses a challenge, since each iteration step boils down to computing
the proximal operator, which may not be easy. In this work we devise a novel
algorithmic framework, which exploits convex duality theory to achieve both
algorithmic efficiency and software modularity of proximal operator
implementations, in order to make experimentation with incremental proximal
optimization algorithms accessible to a larger audience of researchers and
practitioners, by reducing the gap between their theoretical description in
research papers and their use in practice. We provide a reference Python
implementation for the framework developed in this paper as an open source
library at on
https://github.com/alexshtf/inc_prox_pt/releases/tag/prox_pt_paper, along with
examples which demonstrate our implementation on a variety of problems, and
reproduce the numerical experiments in this paper. The pure Python reference
implementation is not necessarily the most efficient, but is a basis for
creating efficient implementations by combining Python with a native backend.
