[
https://issues.apache.org/jira/browse/SPARK-1503?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14644560#comment-14644560
]
Xiangrui Meng commented on SPARK-1503:
--------------------------------------
There are couple stop criteria in TFOCS (implemented in
https://github.com/cvxr/TFOCS/blob/master/private/tfocs_iterate.m and
documented in section 2.4.4 of
https://github.com/cvxr/TFOCS/raw/master/userguide.pdf)
Copied from
https://github.com/cvxr/TFOCS/blob/e34c0daeb136935d23b8df506de8b7b191f6b0a3/userguide.tex#L536:
{code}
\subsubsection{Stopping criteria}
There are a variety of ways to decide when the algorithm should terminate:
\begin{trivlist}
\item \texttt{tol}: TFOCS terminates when the iterates satisfy
$\|x_{k+1}-x_k\|/\max\{1,\|x_{k+1}\|\}\leq\texttt{tol}$.
The default value is $10^{-8}$; if set to zero or a negative value,
this criterion will never be engaged.
\item \texttt{maxIts}: The maximum number of iterations the algorithm
should take; defaults to \verb@Inf@.
\item \texttt{maxCounts}: This option causes termination after a certain
number of function calls or linear operations are made; see
\S\ref{sec:opcounts}
for details. It defaults to \verb@Inf@.
\item \texttt{stopCrit}: Choose from one of several stopping criteria.
By default, \texttt{stopCrit} is 1, which is our recommended stopping
criteria
when not using the SCD model.
Setting this to 3 will use a stopping criteria applied to the dual value
(so this is only available in SCD models, where the dual is really the
primal),
and setting this to 4 is similar but uses a relative error tolerance.
A value of 4 is recommended when using the SCD model with continuation.
For details, see the code in \verb@private/tfocs_iterate.m@.
\item \texttt{stopFcn}: This option allows you to supply one or more
stopping criteria of your own design. To use it, set \verb@stopFcn@
must be a function handle or a cell array of function handles. For
\verb@tfocs.m@, these function handles will be called as follows:
\begin{code_}
stop = stopFcn( f, x );
\end{code_}
where \verb@f@ is the function value and \verb@x@ is the current point.
\begin{code_}
stop = stopFcn( f, z, x );
\end{code_}
where \verb@f@ is the current \emph{dual} function value, \verb@z@ is
the current dual point, and \verb@x@ is the current primal point.
The output should either be \verb@true@ or \verb@false@; if
\verb@true@, the algorithm will stop.
Note that the standard stopping criteria still apply, so the algorithm will halt
when any of the stopping criteria are reached. To ignore the standard stopping
criteria,
set \texttt{stopCrit} to $\infty$.
\end{trivlist}
{code}
> Implement Nesterov's accelerated first-order method
> ---------------------------------------------------
>
> Key: SPARK-1503
> URL: https://issues.apache.org/jira/browse/SPARK-1503
> Project: Spark
> Issue Type: New Feature
> Components: MLlib
> Reporter: Xiangrui Meng
> Assignee: Aaron Staple
> Attachments: linear.png, linear_l1.png, logistic.png, logistic_l2.png
>
>
> Nesterov's accelerated first-order method is a drop-in replacement for
> steepest descent but it converges much faster. We should implement this
> method and compare its performance with existing algorithms, including SGD
> and L-BFGS.
> TFOCS (http://cvxr.com/tfocs/) is a reference implementation of Nesterov's
> method and its variants on composite objectives.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
