Manifold Identification for Regularized Stochastic Online Learning
Manifold Identification in Dual Averaging for Regularized
Stochastic Online Learning
Sangkyun Lee sklee@cs.wisc.edu
Stephen J. Wright swright@cs.wisc.edu
Computer Sciences Department
University of Wisconsin
1210 W. Dayton Street, Madison, WI 53706
Editor:
Abstract
Iterative methods that calculate their steps from approximate subgradient directions have
proved to be useful for stochastic learning problems over large and streaming data sets.
When the objective consists of a loss function plus a nonsmooth regularization term whose
purpose is to induce structure in the solution, the solution often lies on a low-dimensional
manifold of parameter space along which the regularizer is smooth. (When an ℓ1 regularizer
is used to induce sparsity in the solution, for example, this manifold is defined by the set
of nonzero components of the parameter vector.) This paper shows that a regularized dual
averaging algorithm can identify this manifold, with high probability, before reaching the
solution. This observation motivates an algorithmic strategy in which, once an iterate is
suspected of lying on an optimal or near-optimal manifold, we switch to an “local phase”
algorithm that searches in this manifold, thus converging rapidly to a near-optimal point.
Computational results are presented to verify the identification property and to illustrate
the effectiveness of this approach.
Keywords: regularization, dual averaging, partly smooth manifold, manifold identifica-
tion.
1. Introduction
Online learning algorithms based on stochastic approximation often are effective for solving
large machine learning problems. Each step of these methods evaluates an approximate
subgradient of the objective at the current iterate, based on a small subset (perhaps a
single item) of the data. The amount of computation and data manipulation required per
iteration is therefore small. Although many iterations are needed to converge to high-
accuracy solutions, the tradeoffs between optimization errors and the other errors that arise
in machine learning problems suggest that solutions of moderate accuracy often suffice.
However, most existing stochastic algorithms do not produce approximate solutions that
have the desirable structure (such as sparsity) that motivate the use of a regularization
term in the formulation in the first place.
We focus on the regularized dual averaging (RDA) approach developed by Nesterov
(2009) and extended by Xiao (2010) to regularized problems. We show that, under ap-
propriate assumptions, iterates generated by this method have a structure similar to the
solution (to high probability) after a sufficiently large number of iterations. (This structure
1
Lee and Wright
is characterized by a manifold; identification of structure corresponds to identifying the
manifold on which the solution lies.) We sketch an algorithmic strategy that exploits this
property by switching to a “local phase” that searches on the identified manifold, which
often has much lower dimension than the full space.
1.1 Problem Setting and Regularized Dual Averaging
In regularized stochastic learning, we consider the following problem:
min
w∈Rn
φ(w) := f(w) + Ψ(w), (1)
where
f(w) := EξF (w; ξ) =
∫
Ξ
F (w; ξ)dP (ξ), (2)
and ξ is a random vector whose probability distribution P is supported on the set Ξ ⊂ Rd.
We assume that Ψ : Rn → R ∪ {+∞} is a closed proper convex function whose effective
domain (denoted by domΨ) is closed, and that there is an open neighborhood O of domΨ
that is contained in the domain of F (·, ξ), for all ξ ∈ Ξ. We assume that the expectation
in (2) is well defined and finite-valued for all w ∈ O. We also assume that for every ξ ∈ Ξ,
F (w, ξ) is a smooth convex function of w ∈ O. (An elementary argument shows that f is
therefore convex.) We use w∗ to denote a minimizer of (1).
The purpose of the regularization function Ψ is to promote certain desirable types of
structure in the solution of (1). A common desirable property is sparsity (that is, w has
few nonzero elements), which can be promoted by setting Ψ(·) = λ‖ · ‖1 for some parameter
λ > 0.
One method for finding an (approximate) solution to (1) is to draw random variables ξj
for all j ∈ N independently from the space Ξ, where N is an index set of finite cardinality,
and solve a sample average approximation (SAA) problem
min
w∈Rn
φ˜N (w) := f˜N (w) + Ψ(w) (3)
where f˜N (w) := 1card(N )
∑
j∈N F (w; ξj). This approach requires batch optimization, which
does not scale well for N with large cardinality.
Iteration t of a stochastic online learning approach examines a cost function F (·; ξt) :
Rn → R for some ξt ∈ Ξ, drawn randomly according to the distribution P , where {ξt}t≥1
forms an i.i.d. sequence of samples. The next iterate wt+1 is obtained from information
gathered up to the time t, the aim being to generate a sequence {wt} such that
lim
t→∞
E[F (wt; ξ)] + Ψ(wt) = f(w∗) + Ψ(w∗). (4)
We focus on objectives that consist of a smooth loss function F in conjunction with
a nonsmooth regularizer Ψ. Xiao (2010) recently developed the regularized dual averaging
(RDA) method, in which the smooth term is approximated by an averaged gradient in
the subproblem at each iteration, while the regularization term appears explicitly. (Xiao’s
approach extends the method of Nesterov (2009) in the sense that the regularization term
2
Manifold Identification for Regularized Stochastic Online Learning
is not handled explicitly in Nesterov’s paper.) Specifically, the RDA subproblem is
wt+1 = argmin
w∈Rn
{
〈g¯t, w〉+Ψ(w) +
βt
t h(w)
}
, (5)
where g¯t = 1t
∑t
j=1 gj and gj ∈ ∂F (wj ; ξj). The prox-function h(·) is a proper strongly
convex function such as h(·) = ‖·−w1‖2, and {βt}t≥1 is a sequence of nonnegative numbers.
A characteristic of problems with nonsmooth regularizers is that the solution often lies on
a manifold of low dimension. In ℓ1-regularized problems, for instance, the number of nonzero
components at the solution is often a small fraction of the dimension of the full space.
When a reliable method for identifying an optimal (or near-optimal) manifold is available,
we have the possibility of invoking an algorithm that searches just in the low-dimensional
space defined by this manifold — possibly a very different algorithm from the one used on
the full space. One local-phase algorithm that is well suited to the ℓ1 regularizer is LASSO
Pattern-Search (LPS) (Shi et al., 2008; Wright, 2010), a batch optimization method for ℓ1-
regularized logistic regression, which takes gradient steps in the space of nonzero variables,
enhanced by Newton steps. In logistic regression, and probably in other applications too, it
can be much less expensive to compute first- and second-order information on a restricted
subspace than on the full space.
A second motivation for aiming to identify the optimal manifold is that for problems
of large dimension, it may be quite expensive even to store a single iterate wt, whereas an
iterate whose structure is similar to that of the solution w∗ may be stored economically. (To
take the case of ℓ1 regularization again, we would need to stored only the nonzero elements
of wt and their locations.)
In this paper, we investigate the ability of the RDA algorithm to identify the optimal
manifold. We also suggest an enhanced algorithm, RDA+, and test it for the case of ℓ1-
regularized logistic regression, in which an LPS-based algorithm is used to explore the
near-optimal manifold identified by RDA.
1.2 Optimal Manifolds and the Identification
Identification of optimal manifolds has been studied in the context of convex constrained
optimization (Burke and More´, 1994; Wright, 1993) and nonsmooth nonconvex optimiza-
tion (Hare and Lewis, 2004). In constrained optimization, the optimal manifold is typically
a face or edge of the feasible set that contains the solution. In nonsmooth optimization,
the optimal manifold is a smooth surface passing through the optimum, parameterizable by
relatively few variables, such that the restriction of the objective function to the manifold is
smooth. In either case, when a certain nondegeneracy condition is satisfied, this manifold
may be identified without knowing the solution, usually as a by-product of an algorithm for
solving the problem. Lewis and Wright (2008) analyze a framework for composite minimiza-
tion (which uses a subproblem in which f is replaced by an exact linearization around wt)
and prove identification results. Part of the motivation for the current paper is to obtain
similar results as in Lewis and Wright (2008) in the stochastic gradient setting.
3
Lee and Wright
1.3 Alternative Stochastic Approximation Approaches
Stochastic approximation algorithms have a rich history, and are currently the focus of
intense research in the machine learning and optimization communities. We mention a few
relevant developments here, and discuss their manifold identification properties.
Stochastic approximation methods often solve formulations in which an explicit con-
straint w ∈ W (for a compact convex set W) is present. These can be incorporated into
the framework (1) by defining the regularization function Ψ as follows:
Ψ(w) := δW(w) + ψ(w), (6)
where δW(w) is the indicator function (zero on W and +∞ elsewhere) and ψ is a convex
function whose domain includes W. (In this setting, O is taken to be an open neighborhood
of W.) The classical approaches to solve such problems can be traced back to Robbins and
Monro (1951) and Kiefer and Wolfowitz (1952). The stochastic gradient descent (SGD)
method generates its iterates by stepping in the direction of a subgradient estimate and
then projecting onto W, as follows:
wt+1 = ΠW (wt − αt(gt + κt)) , t = 1, 2, . . . (7)
where gt ∈ ∂F (wt; ξt) for some sampled random variable ξt, κt ∈ ∂ψ(wt), and ΠW(·) denotes
the Euclidean projection onto the set W. With steplength choice of the form αt = θ/t
(for a well-chosen constant θ), the SGD method exhibits O(1/t) convergence rate in the
quantity (4) for strongly convex functions f (Chung, 1954; Sacks, 1958). For general convex
functions, a step length of the form αt = θ′/
√
t (for some θ′ > 0) yields an O(1/
√
t) rate of
convergence in the function value (Nemirovski and Yudin, 1978; Polyak, 1990; Polyak and
Juditsky, 1992). (Simplified proofs of these rates can be found in Nemirovski et al. (2009).)
These rates are known to be optimal for subgradient schemes in “black-box” algorithmic
models (Nemirovski and Yudin, 1983). Although batch optimization methods based on an
approximate objective (such as (3)) may provide better convergence rates, SGD has been
widely used in machine learning because it scales very well with large data sets and provides
good generalization performance in practice (Zinkevich, 2003; Bottou, 2004; Zhang, 2004;
Shalev-Shwartz et al., 2007).
As discussed in Xiao (2010), the SGD method does not exploit the problem structure
that is present in the regularizer ψ. There is no reason to believe that these algorithms have
good manifold identification properties. When ψ = ‖·‖1, for instance, there is no particular
reason for the iterates wt to be sparse. Though equal in expectation, gt and ∇f(xt) may be
far apart, so that even if a careful choice of κt is made at each iteration, the updates may
have the cumulative effect of “filling in” the iterates wt.
Variants of SGD for the general convex cases often work with averaged primal iterates,
of the form
w¯t :=
∑t
j=1 νjwj
∑t
j=1 νj
, (8)
where the νj are nonnegative weights (see, for example, equation (2.16) in Nemirovski et al.,
2009). Averaging does not improve identification properties. For ℓ1 regularization, we can
still expect the averaged iterates w¯t to be at least as dense as the “raw” iterations wt.
4
Manifold Identification for Regularized Stochastic Online Learning
Recently, various authors have proposed modifications of SGD that account for the
regularization structure. Some representative examples include composite objective mir-
ror descent (COMID) (Duchi et al., 2010), forward-backward splitting (FOBOS) (Duchi
and Singer, 2009), truncated gradient (TG) (Langford et al., 2009), and sparsity-preserving
stochastic gradient (SSG) (Lin et al., 2011). The basic FOBOS subproblem is similar to
that of the prox-descent algorithm of Lewis and Wright (2008) and the SpaRSA framework
of Wright et al. (2009), that is,
wt+1 = argmin
w∈Rn
{
〈gt, w〉+Ψ(w) +
1
2αt
‖w − wt‖22
}
, (9)
for some parameter αt > 0 (which plays a step-length-like role) — where gt is assumed
to be the exact gradient ∇f(wt). However, Duchi and Singer (2009) suggest an extension
to an online setting, in which gt is replaced by an approximate gradient. SSG (Lin et al.,
2011) also has the subproblem (9) at its core, but embeds it in a strategy for generating
three sequences of iterates (rather than the single sequence {wt}), extending an idea of
Nesterov (2004). The TG method (Langford et al., 2009) solves a subproblem like (9) on
some iterations; on other iterations it simply steps in the direction gt of the latest gradient
estimate for f , ignoring the regularization term. COMID (Duchi et al., 2010) is also based on
a subproblem of the form (9), but with a Bregman divergence replacing the final quadratic
term, thus yielding a more general framework.
Since all these methods make explicit use of the regularization term Ψ in the subproblem,
they are more likely to generate iteration sequences that share the structure of the solution
w∗, that is, to identify a near-optimal manifold. Such behavior is far from guaranteed,
however, because gt may be only a rough approximation to ∇f(wt). The inaccuracy of
this gradient estimate may cause the iterates to step away from the optimal manifold, even
from an iterate wt that is close to the solution w∗. (In Appendix D, we give an example of
a function satisfying all the assumptions of this paper, in which the subproblem (9) steps
away from the optimal point and off the optimal manifold.) In contrast, the dual average
g¯t used by the RDA subproblem stabilizes around ∇f(w∗) as the iterates converge to w∗,
allowing identification results to be derived from analysis like that of Hare and Lewis (2004);
Lewis and Wright (2008), suitably generalized to the stochastic setting.
Averaging of the primal iterates (8) does not improve the identification properties of the
methods above, and will usually make them worse. Considering again ℓ1 regularization, we
observe that if component i of any iterate wt is nonzero, then component i of all averaged
iterates at subsequent iterations will also be nonzero (unless some fortuitous cancellation
occurs). RDA itself, in the version recommended by the analysis of Xiao (2010), has the
same deficiency, as the main convergence results in that paper are for averaged iterates (8).
In the current paper, we facilitate the use of the raw iterates wt by RDA by adding two
assumptions. First, w∗ is assumed to be a strong minimizer of the restriction of φ to the
optimal manifold. Second, a nondegeneracy condition ensures that φ increases sharply as
we move off the manifold. Together, these conditions ensure that w∗ is a strong minimizer
of φ, so convergence of φ(wt) to φ(w∗) forces convergence of wt to w∗.
Convergence analysis of stochastic approximation algorithms focuses largely on the re-
gret, which is defined as follows, for any instantiation of the random sequence {wt}t≥1 with
5
Lee and Wright
respect to any fixed decision w ∈ domΨ:
Rt(w) :=
t
∑
j=1
[F (wj ; ξj) + Ψ(wj)]−
t
∑
j=1
[F (w; ξj) + Ψ(w)]. (10)
As we discuss later, the RDA algorithm has O(
√
t) regret bounds when βt = O(
√
t) for
general convex cases, and O(ln t) bounds with βt = O(ln t) for strongly convex cases. These
bounds are comparable to those of the SGD method. For general convex cases, when we use
αt = O(1/
√
t), SGD achieves an O(1/
√
t) regret bound (e.g. Zinkevich, 2003; Nemirovski
et al., 2009), which cannot be improved in general. For the strongly convex case, SGD has
an O(ln t) bound (e.g. Hazan et al., 2006; Bartlett et al., 2008) with αt = O(1/t).
1.4 Notation and Terminology
Throughout the paper, we use ‖·‖ (without a subscript) to denote the Euclidean norm ‖·‖2,
and card(M) to denote the cardinality of a finite set M . The distance function dist (w,C)
for w ∈ Rn and a convex set C ⊂ Rn is defined by dist (w,C) := infc∈C ‖w − c‖. The
effective domain of Ψ : Rn → R ∪ {+∞} is defined by domΨ := {w ∈ Rn |Ψ(w) < +∞}.
ri C denotes the relative interior of a convex set C, that is, the interior relative to the affine
span of C (the smallest affine set which can be expressed as the intersection of hyperplanes
containing C).
We call a function ϕ : Rn → R ∪ {∞} strongly convex if there exists a constant σ > 0
such that ∀w,w′ ∈ domϕ and ∀α ∈ [0, 1],
ϕ(αw + (1− α)w′) ≤ αϕ(w) + (1− α)ϕ(w′)− σ
2
α(1− α)‖w − w′‖2.
(σ is known as the modulus of strong convexity.) Strong convexity implies that for any
w ∈ domϕ and w′ ∈ ri domϕ, we have
ϕ(w) ≥ ϕ(w′) + 〈s, w − w′〉+ σ
2
‖w − w′‖2, ∀s ∈ ∂ϕ(w′).
We say that a function ϕ has a locally strong minimizer at w∗ if there exist positive
constants c and r¯ such that
ϕ(w)− ϕ(w∗) ≥ c‖w − w∗‖2, for all w ∈ O with ‖w − w∗‖ ≤ r¯. (11)
w∗ is a globally strong minimizer if this expression is true with r¯ = ∞.
The algorithm we consider in this paper makes use of an i.i.d. sequence {ξj}j≥1 of
random variables drawn from Ξ according to the distribution P . We denote the history of
random variables up to time t by
ξ[t] := {ξ1, ξ2, . . . , ξt}.
The iterate wt produced by the algorithm depends on ξ1, ξ2, . . . , ξt−1 but not on ξt, ξt+1, · · · ;
we sometimes emphasize this fact by writing wt = wt(ξ[t−1]).
6
Manifold Identification for Regularized Stochastic Online Learning
2. Assumptions and Basic Results
We summarize here our fundamental assumptions about the problem and its solution, to-
gether with some basic observations and results that will be used in the analysis of later
sections.
2.1 Unbiasedness
As in Nemirovski et al. (2009), we assume the following unbiasedness property:
∇f(w) = ∇wEξF (w; ξ) = Eξ∇wF (w; ξ) (12)
for any w independent of ξ. (As the differentiation of F is taken only for its first argument,
we omit the subscript “w” in subsequent discussions.) Given that wt = wt(ξ[t−1]), this
implies
E[∇F (wt; ξt)] = E
[
E[∇F (wt; ξt)|ξ[t−1]]
]
= E [∇f(wt)] .
2.2 Uniform Lipschitz Continuity
First, we assume that each F (w; ξ) is a smooth convex function of w ∈ O for every ξ ∈ Ξ,
and in particular that ∇F (·; ξ) is uniformly Lipschitz continuous with respect to its first
argument, over all ξ. That is, there exists a constant L > 0 such that
‖∇F (w; ξ)−∇F (w′; ξ)‖ ≤ L‖w − w′‖, ∀w,w′ ∈ O, ∀ξ ∈ Ξ. (13)
This assumption immediately leads to a Lipschitz property on ∇f . We prove this claim
after presenting a technical result that is used often in later sections.
Lemma 1 For a vector-valued function h : Ξ → Rn which is integrable with respect to P ,
we have
‖Eh‖2 ≤ E‖h‖2.
Proof Using the dual of the Euclidean norm, we deduce that
‖Eh‖2 = sup
v∈Rn,‖v‖2=1
〈v,Eh〉
= sup
v∈Rn,‖v‖2=1
∫
Ξ
〈v, h(ξ)〉dP (ξ)
≤ sup
v∈Rn,‖v‖2=1
∫
Ξ
[
sup
w∈Rn,‖w‖2=1
〈w, h(ξ)〉
]
dP (ξ)
=
∫
Ξ
‖h(ξ)‖2dP (ξ) = E‖h‖2.
Lemma 2 If ∇F (w; ξ) satisfies the uniform Lipschitz continuity assumption (13), then
∇f(w) is also uniformly Lipschitz continuous on O with the same constant L.
7
Lee and Wright
Proof From unbiasedness, we have for w,w′ ∈ O independent of ξ that
∇f(w) = ∇E[F (w; ξ)] = E[∇F (w; ξ)] from (12)
= E[∇F (w′; ξ) + uξ] for uξ := ∇F (w; ξ)−∇F (w′; ξ)
= ∇f(w′) + E[uξ] from (12) again.
Since ‖uξ‖ ≤ L‖w − w′‖, we have
‖∇f(w)−∇f(w′)‖ = ‖Euξ‖ ≤ E‖uξ‖ ≤ L‖w − w′‖,
where the first inequality is due to Lemma 1.
We further assume that there exists a uniform bound G for which
‖∇F (w; ξ)‖ ≤ G, ∀w ∈ O, ∀ξ ∈ Ξ. (14)
2.3 Optimality and Nondegeneracy
We specify several optimality conditions that are assumed to hold throughout the paper.
The optimality of w∗ for the problem (1) can be characterized as follows:
0 ∈ ∇f(w∗) + ∂Ψ(w∗). (15)
We assume that w∗ is a nondegenerate solution — one that satisfies the stronger condition
0 ∈ ri [∇f(w∗) + ∂Ψ(w∗)] . (16)
2.4 Manifolds and Partial Smoothness
In this section we discuss properties of differential manifolds and partial smoothness by
repeating some definitions from Hare and Lewis (2004).
Definition 3 (Manifold) A set M ⊂ Rn is a manifold about z¯ ∈ M if it can be described
locally by a collection of Cp functions (p ≥ 2) with linearly independent gradients. That is,
there exists a map H : Rn → Rk that is Cp around z¯ with ∇H(z¯)T ∈ Rk×n, surjective, such
that points z near z¯ lie in M if and only if H(z) = 0.
The normal space to M at z¯, denoted by NM(z¯), is the range space of ∇H(z¯), while the
tangent space to M at z¯ is the null space of ∇H(z¯)T . We assume without loss of generality
that ∇H(z¯) has orthonormal columns.
We define partial smoothness as follows (Lewis, 2003, Section 2).
Definition 4 (Partial Smoothness) A function ϕ : Rn → R is (C2-) partly smooth at
a point z¯ ∈ Rn relative to a set M ⊂ Rn containing z¯ if M is a manifold about z¯ and the
following properties hold:
(i) (Smoothness) The function ϕ restricted to M, denoted by ϕ|M, is C2 near z¯;
(ii) (Regularity) ϕ is subdifferentially regular at all points z ∈ M near z¯, with ∂ϕ(z) 6= ∅;
8
Manifold Identification for Regularized Stochastic Online Learning
(iii) (Sharpness) The affine span of ∂ϕ(z¯) is a translate of NM(z¯);
(iv) (Sub-continuity) The set-valued mapping ∂ϕ : M ⇉ Rn is continuous at z¯.
We refer to M as the active manifold at the point z¯, as the optimal manifold when z¯ = w∗,
where w∗ is a solution of (1).
Henceforth, we assume that Ψ is partly smooth at w∗ relative to the optimal manifold, which
implies partly smoothness of φ since f is smooth (by an argument like that of Lemma 2).
We discuss the concepts outlined in the definitions above for the specific case of Ψ(·) =
‖ · ‖1. Given z¯ ∈ Rn, we define the following partition of the indices {1, 2, . . . , n}:
{1, 2, . . . , n} = P ∪N ∪ Z,
where z¯i = 0 for all i ∈ Z, z¯i > 0 for all i ∈ P, and z¯i < 0 for all i ∈ N . A natural definition
of the active manifold M is thus
M = {z | zi = 0 for all i ∈ Z}. (17)
Note that z¯ ∈ M, and that the mapping H of Definition 3 can be defined as H(z) = [zi]i∈Z ,
with k = card(Z) in that definition. The restriction of Ψ to this manifold thus has the
following form for all z ∈ M near z¯:
−
∑
i∈N
zi +
∑
i∈P
zi,
so that (i) of Definition 4 is satisfied. For z ∈ M near z¯, we have
[∂φ(z)]i = [∇f(z)]i +





[−1, 1] for i ∈ Z,
−1 for i ∈ N ,
+1 for i ∈ P.
Clearly, condition (ii) of Definition 4 holds. The affine span of ∂φ(z¯) is
{∇f(z¯) + g | gi = −1 for i ∈ N and gi = +1 for j ∈ P},
whereas NM(z¯) = {g | gi = 0 for i ∈ P ∪N}. Comparison of the last two expressions shows
that (iii) of Definition 4 is satisfied. Finally, the set-valued map ∂Ψ is in fact constant along
M near z¯, so because f is smooth, Definition 4 (iv) also holds.
2.5 Strong Minimizer Properties
We assume that w∗ is a locally strong minimizer of φ relative to the optimal manifoldM with
modulus cM > 0, that is, there exists cM > 0 and rM > 0 such that {w ∈ Rn | ‖w −w∗‖ ≤
rM} ⊂ O and
φ|M(w) ≥ φ|M(w∗) + cM‖w − w∗‖2, for all w ∈ O with ‖w − w∗‖ ≤ rM. (18)
Under the given conditions, this implies that w∗ is a locally strong minimizer of φ(w)
(without restriction to the optimal manifold).
9
Lee and Wright
Theorem 5 (Strong Minimizer for General Convex Case) Suppose that φ is partly
smooth at w∗ relative to the optimal manifold M, that w∗ is a locally strong minimizer
of φ|M with the modulus cM > 0 and radius rM > 0 as defined in (18), and that the
nondegeneracy condition (16) holds at w∗. Then there exist c ∈ (0, cM] and r¯ ∈ (0, rM]
such that
φ(w)− φ(w∗) ≥ c‖w − w∗‖2, for all w ∈ O with ‖w − w∗‖ ≤ r¯, (19)
that is, w∗ is a locally strong minimizer of φ, without restriction to the manifold M.
Proof The proof is a simplification of the proof of (Wright, 2010, Theorem 2.5), which
considers the more general case in which f is prox-regular rather than convex. For com-
pleteness, we present the proof in Appendix A.
The condition (19) is similar to the quadratic growth condition proposed by Anitescu (2000)
in the context of nonlinear programming. It was shown by Anitescu that this fundamen-
tal condition is weaker than many other second-order conditions that are widely used in
nonlinear programming.
Two corollaries follow in a straightforward fashion from the theorem above. We state
these results here and give their proofs in Appendix A.
Corollary 6 Suppose that w∗ is a locally strong minimizer of (1) that satisfies (19). For
all w ∈ O with ‖w − w∗‖ > r¯, we have
φ(w)− φ(w∗) > cr¯‖w − w∗‖.
Corollary 7 (Globally Strong Minimizer for Strongly Convex Case) Suppose that
w∗ is a locally strong minimizer of (1) satisfying (19). If φ is strongly convex on domΨ
with modulus σ > 0, then w∗ is a globally strong minimizer of (1) with modulus min(c, σ/2),
that is,
φ(w) ≥ φ(w∗) + min(c, σ/2)‖w − w∗‖2, for all w ∈ O. (20)
2.6 Summary of Assumptions
We summarize here the assumptions introduced in this section, for reference in the remain-
der of the paper.
The first assumption summarizes basic properties of the functions and the minimizer.
Assumption 1 The unbiasedness property (12), uniform Lipschitz continuity of ∇F (·; ξ)
for all ξ ∈ Ξ (13), uniform boundedness of ‖∇F (·, ξ)‖ (14), and nondegeneracy at the
optimum w∗ (16) are satisfied.
The second assumption provides sufficient conditions for w∗ to be a locally strong min-
imizer.
Assumption 2 The function φ is partly smooth at its minimizer w∗ relative to the optimal
manifold M and w∗ is a locally strong minimizer of φ|M as defined in (18).
10
Manifold Identification for Regularized Stochastic Online Learning
3. Regularized Dual Averaging Algorithm
We start this section by describing regret bounds for the regularized dual averaging (RDA)
algorithm of Xiao (2010) (following Nesterov, 2009), focusing on its stochastic variant. We
also describe the consequences for the analysis of the condition that the minimum is strong
locally (19) or globally (20). We then analyze the properties of the averaged gradient; this
analysis forms the basis of the manifold identification result in Section 4.
3.1 The RDA Algorithm
We start by specifying the RDA algorithm from Xiao (2010), noting that our assumptions
on the functions F , f , and Ψ from Section 1 are stronger than the corresponding conditions
in Xiao (2010), which require only subdifferentiability of F (w; ξt) on domΨ. We assume
without loss of generality that minΨ(w) = 0.
We introduce a prox-function h : Rn → R ∪ {∞} which is proper, strongly convex on
domΨ, and subdifferentiable on ri domΨ. Without loss of generality, h(w) is assumed to
have modulus of convexity 1, with minh(w) = 0. In addition, we require h to satisfy
argmin
w
h(w) ∈ argmin
w
Ψ(w).
We define the prox-center w1 of domΨ with respect to h, (which will be the starting point
of the RDA method) as follows:
w1 := argmin
w∈domΨ
h(w).
Note that h(w1) = 0 and Ψ(w1) = 0 by the assumptions. (The terms “prox-function”
and “prox-center” are borrowed from Nesterov (2009).) The most obvious prox-function is
h(·) = ‖ · −w1‖2, where w1 ∈ argminx Ψ(w).
We now define a constant D that reappears throughout the analysis. For any D > 0,
we consider a level set of the prox-function h defined as follows:
FD := {w ∈ domΨ | h(w) ≤ D2}. (21)
We assume in the analysis that points of interest (specifically, w∗) lie in FD.
At iteration t, the stochastic RDA algorithm samples a vector ξt ∈ Ξ, according to the
distribution P , and evaluates an approximate gradient as follows:
gt := ∇F (wt; ξt). (22)
We assume that the random variables ξt are i.i.d. The dual average — an averaged approx-
imation to the gradient of f — is defined as follows:
g¯t :=
1
t
t
∑
j=1
gj =
1
t
t
∑
j=1
∇F (wj ; ξj). (23)
The RDA algorithm is specified rigorously in Algorithm 1. As the objective function in
the subproblem (24) is strongly convex when βt > 0 or when Ψ(·) is strongly convex, wt+1
11
Lee and Wright
Algorithm 1 The RDA Algorithm.
Input:
• a prox-function h(w) that is strongly convex on domΨ and also satisfies
argmin
w∈Rn
h(w) ∈ argmin
w∈Rn
Ψ(w).
• a nonnegative and nondecreasing sequence {βt}, t ≥ 1.
Initialize: set w1 = argmin h(w) and g¯0 = 0.
for t = 1, 2, . . . do
Sample ξt from Ξ and compute a gradient gt = ∇F (wt; ξt).
Update the average gradient:
g¯t =
t− 1
t g¯t−1 +
1
t gt.
Compute the next iterate:
wt+1 = argmin
w∈Rn
{
〈g¯t, w〉+Ψ(w) +
βt
t h(w)
}
. (24)
end for
is uniquely defined by (24). Note that wt+1 depends on the history of random variables ξ[t]
up to iteration t, and is independent of later samples ξt+1, ξt+2, . . . .
We consider two choices of parameter sequences {βt} in the remainder of the paper,
depending on whether the regularization function Ψ is strongly convex or not. The first
choice holds for general convex regularizers Ψ.
βt = γ
√
t, t ≥ 1, for some constant γ > 0. (25)
The second choice, βt ≤ O(1 + ln t), can be used when Ψ is a strongly convex function,
with modulus σ > 0. Among the three choices discussed in Xiao (2010), that is, βt = σ,
βt = σ(1+ ln t), and βt = 0, we focus on the zero sequence which gives the simplest bounds.
βt = 0, t ≥ 1. (26)
In this case, the subproblem (24) in Algorithm RDA has no damping term. We rely instead
on the damping effect supplied by the strong convexity of Ψ to stabilize the iterates.
3.2 Bounds on Regret and Expected Errors in the Iterations
Our first key result concerns bounds on the regret function defined in (10).
Theorem 8 Suppose that that Assumptions 1 and 2 are satisfied. When {βt} is chosen
according to (25), we have for any w ∈ FD that
Rt(w) ≤
(
γD2 + G
2
γ
)√
t, t ≥ 1. (27)
12
Manifold Identification for Regularized Stochastic Online Learning
Moreover, when Ψ(w) is strongly convex with the modulus σ > 0, then the choice (26) for
{βt} results in the following bound for w ∈ FD:
Rt(w) ≤
G2
2σ (6 + ln t), t ≥ 1. (28)
Proof See Xiao (2010, Corollary 2) for the general convex case, and Xiao (2010, Theorem
1 and Section 3.2) for the strongly convex case.
The next result obtains bounds on the expected errors in the iterates generated by
Algorithm 1. For the purpose of this and future results, we define the indicator function
I(A) for the event A as follows
I(A) =
{
1 if event A is true,
0 if event A is false.
(29)
For a random event A, I(A) is a random variable.
Lemma 9 (Expected Error Bounds of Iterates) Suppose that w∗ ∈ FD is a locally
strong minimizer of (1) according to the definition (19). Then for the iterates w1, w2, . . . , wt
generated by the stochastic RDA algorithm with {βt} chosen by (25), we have
1
t
t
∑
j=1
E
[
I(‖wj−w∗‖≤r¯)‖wj − w∗‖2
]
≤ 1c
(
γD2 + G
2
γ
)
t−1/2, (30a)
1
t
t
∑
j=1
E
[
I(‖wj−w∗‖>r¯)‖wj − w∗‖
]
≤ 1cr¯
(
γD2 + G
2
γ
)
t−1/2. (30b)
When Ψ(w) is strongly convex with the modulus σ > 0, then with {βt} chosen by (26) we
have
1
t
t
∑
j=1
E
[
‖wj − w∗‖2
]
≤ G
2
2σmin(c, σ/2)
6 + ln t
t . (31)
Proof See Appendix B.1.
The next result combines the error bounds (30a) and (30b) into a more useful form for
the results that follow.
Theorem 10 Suppose that w∗ ∈ FD is a locally strong minimizer of (1) according to
the definition (19). Then for the iterates w1, w2, . . . , wt generated by the stochastic RDA
algorithm with the choice (25) for {βt}, we have
1
t
t
∑
j=1
E‖wj − w∗‖ ≤ µt−1/4 (32)
13
Lee and Wright
for the constant µ defined as follows:
µ := 1√c
(
γD2 + G
2
γ
)1/2 [
1 +
1
r¯√c
(
γD2 + G
2
γ
)1/2]
. (33)
When Ψ(w) is strongly convex with the modulus σ > 0, then with the choice (26) for {βt}
we have
1
t
t
∑
j=1
E‖wj − w∗‖ ≤ µ′
(
6 + ln t
t
)1/2
(34)
for the constant µ′ defined by
µ′ := G√
2σmin(c, σ/2)
. (35)
Proof See Appendix B.1.
3.3 Stochastic Behavior of the Dual Average
We now study the properties of the dual average, g¯t, and in particular the quality of its
convergence to the optimal gradient ∇f(w∗).
Theorem 11 Suppose that Assumptions 1 and 2 are satisfied and that w∗ ∈ FD. Defining
Σt := E[(g¯t − Eg¯t)(g¯t − Eg¯t)T ],
we have for the choice (25) of {βt} that
(i) ‖Eg¯t −∇f(w∗)‖ ≤ Lµt−1/4,
(ii) tr Σt ≤ 4G(G+ 4Lµ)t−1/4.
For the strongly convex case with the choice (26) of {βt}, we have
(i’) ‖Eg¯t −∇f(w∗)‖ ≤ Lµ′
(6+ln t
t
)1/2
,
(ii’) tr Σt ≤ 4G(G+ 4Lµ′)
(6+ln t
t
)1/2
.
The constants µ and µ′ are defined in (33) and (35), respectively.
Proof See Appendix B.2
Using Theorem 11, we show an important property for the dual average: the probability
that g¯t lies outside any given ball around ∇f(w∗) goes to zero as t increases.
14
Manifold Identification for Regularized Stochastic Online Learning
Theorem 12 Suppose that Assumptions 1 and 2 are satisfied and that w∗ ∈ FD, and let
ǫ > 0 be any chosen constant. Define the quantities ν and ν ′ by
ν :=
[
Lµ+ 2
√
G (G+ 4Lµ)1/2
]2
, (36a)
ν ′ :=
[
Lµ′ + 2
√
G
(
G+ 4Lµ′
)1/2
]2
. (36b)
When {βt} is chosen from (25), we have
P(‖g¯t −∇f(w∗)‖ > ǫ) < ǫ−2νt−1/4, t ≥ 1.
When Ψ is strongly convex and the choice (26) is used for {βt}, we have
P(‖g¯t −∇f(w∗)‖ > ǫ) < ǫ−2ν ′
(
6 + ln t
t
)1/2
, t ≥ 1.
Proof For the general convex case, from Markov inequality, we obtain for every ǫ > 0 that
P(‖g¯t −∇f(w∗)‖ > ǫ) = P(‖g¯t −∇f(w∗)‖2 > ǫ2) < ǫ−2E[‖g¯t −∇f(w∗)‖2].
Since g¯t −∇f(w∗) = {Eg¯t −∇f(w∗)}+ {g¯t − Eg¯t}, we have
E[‖g¯t −∇f(w∗)‖2]
≤ E
[
‖Eg¯t −∇f(w∗)‖2 + 2‖Eg¯t −∇f(w∗)‖‖g¯t − Eg¯t‖+ ‖g¯t − Eg¯t‖2
]
= ‖Eg¯t −∇f(w∗)‖2 + 2‖Eg¯t −∇f(w∗)‖E‖g¯t − Eg¯t‖+ E‖g¯t − Eg¯t‖2
≤ ‖Eg¯t −∇f(w∗)‖2 + 2‖Eg¯t −∇f(w∗)‖
(
E‖g¯t − Eg¯t‖2
)1/2
+ E‖g¯t − Eg¯t‖2
=
[
‖Eg¯t −∇f(w∗)‖+
(
E‖g¯t − Eg¯t‖2
)1/2]2 ,
where the third inequality is due to Jensen’s inequality. The first term in the last line can
be bounded by Theorem 11 (i). For the second term, we use Theorem 11 (ii) to obtain
E‖g¯t − Eg¯t‖2 = E
( n
∑
i=1
[g¯t − Eg¯t]2i
)
=
n
∑
i=1
E
(
[g¯t − Eg¯t]2i
)
= trΣt ≤ 4G [G+ 4Lµ] t−1/4.
Collecting all results, we conclude that
P(‖g¯t −∇f(w∗)‖ > ǫ)
< ǫ−2
[
Lµt−1/4 +
{
4G(G+ 4Lµ)t−1/4
}1/2
]2
≤ ǫ−2
[
Lµ+ 2
√
G (G+ 4Lµ)1/2
]2
t−1/4
as claimed.
For the strongly convex case, we use the bounds in parts (i’) and (ii’) of Theorem 11
and a similar argument to obtain the result.
15
Lee and Wright
4. Manifold Identification
In this section we show that most sufficiently advanced iterates of the RDA algorithm
identify the optimal manifold. Our analysis is based upon the properties of the dual average
discussed in the previous section and on basic results for manifold identification.
4.1 Convergent Sequences
We start with two result that estimate the likelihood of wj lying within a given radius of
w∗. The first of these results is for general convex objectives.
Lemma 13 (Convergent Sequences for General Convex Case) Suppose that Assump-
tions 1 and 2 hold, that w∗ ∈ FD, and that {βt} is chosen according to (25). Define the
subsequence S by
S :=
{
j ∈ {1, 2, . . . } | E
[
I(‖wj−w∗‖≤r¯)‖wj − w∗‖2
]
≤ j−1/4, and
E
[
I(‖wj−w∗‖>r¯)‖wj − w∗‖
]
≤ r¯−1j−1/4
}
. (37)
For any ǫ > 0, we then have
P (‖wj − w∗‖ > ǫ) <
1
ǫ
(
1
ǫ +
1
r¯
)
j−1/4, ∀j ∈ S. (38)
Defining
St := S ∩ {1, 2, . . . , t}, (39)
we have
1
t card(St) > 1−
2
c
(
γD2 + G
2
γ
)
t−1/4, (40)
that is, the density of St in {1, 2, . . . , t} is 1−O(t−1/4).
Proof To measure the cardinality of the complement of St, that is, Sct := {1, 2, . . . , t} \ St,
we first define indicator variables χj− and χj+ for j ≥ 1 as follows:
χj− :=
{
1 if E
[
I(‖wj−w∗‖≤r¯)‖wj − w∗‖2
]
> j−1/4,
0 otherwise.
χj+ :=
{
1 if E
[
I(‖wj−w∗‖>r¯)‖wj − w∗‖
]
> (1/r¯)j−1/4,
0 otherwise.
16
Manifold Identification for Regularized Stochastic Online Learning
As the set Sct contains all indices j ∈ {1, 2, . . . , t} that satisfy χj− = 1 or χj+ = 1, the
cardinality of Sct is bounded above by
∑t
j=1(χ
j
− + χj+). For
∑t
j=1 χ
j
−, we note that
t
∑
j=1
E
[
I(‖wj−w∗‖≤r¯)‖wj − w∗‖2
]
≥
t
∑
j=1
χj−E
[
I(‖wj−w∗‖≤r¯)‖wj − w∗‖2
]
>
t
∑
j=1
χj−j−1/4 (from the definition of χj−)
≥ t−1/4
t
∑
j=1
χj−.
Using (30a), we deduce that
1
t
t
∑
j=1
χj− <
1
c
(
γD2 + G
2
γ
)
t−1/4.
Similar arguments for
∑t
j=1 χ
j
+ with E
[
I(‖wj−w∗‖>r¯)‖wj − w∗‖
]
, j = 1, 2, . . . , t and (30b)
lead to
1
t
t
∑
j=1
χj+ <
1
c
(
γD2 + G
2
γ
)
t−1/4.
Therefore, the fraction of the cardinality of St to {1, 2, . . . , t} is
1
t card(St) = 1−
1
t card(S
c
t )
≥ 1− 1t
t
∑
j=1
(χj− + χj+)
> 1− 2c
(
γD2 + G
2
γ
)
t−1/4,
thus proving (40).
To show (38), we first observe that for any ǫ > 0,
P(‖wj − w∗‖ > ǫ) = P(‖wj − w∗‖ > ǫ, ‖wj − w∗‖ ≤ r¯)
+ P(‖wj − w∗‖ > ǫ, ‖wj − w∗‖ > r¯). (41)
Focusing on the first term, we have for all j ∈ S that
P(‖wj − w∗‖ > ǫ, ‖wj − w∗‖ ≤ r¯) = P(I(‖wj−w∗‖≤r¯)‖wj − w∗‖ > ǫ)
< ǫ−2E
[
I(‖wj−w∗‖≤r¯)‖wj − w∗‖2
]
≤ ǫ−2j−1/4, (42)
17
Lee and Wright
where the first inequality is due to Markov and the second inequality is from the definition
of S in (37). Similarly for the second term in (41), we have for all j ∈ S that
P(‖wj − w∗‖ > ǫ, ‖wj − w∗‖ > r¯) = P(I(‖wj−w∗‖>r¯)‖wj − w∗‖ > ǫ)
< ǫ−1E
[
I(‖wj−w∗‖>r¯)‖wj − w∗‖
]
≤ ǫ−1r¯−1j−1/4. (43)
Applying (42) and (43) to (41) leads to the claim,
P(‖wj − w∗‖ > ǫ) < ǫ−1(ǫ−1 + r¯−1)j−1/4, ∀j ∈ S.
This result implies that for sufficiently large j, the majority of iterates wj converges to w∗
in probability. The next theorem is the corresponding result for the strongly convex case.
Lemma 14 (Convergent Sequences for Strongly Convex Case) Suppose that Assump-
tions 1 and 2 hold, that w∗ ∈ FD, and that the regularizer Ψ is strongly convex with modulus
σ > 0. Suppose that {βt} is defined by (26). For any ǫ > 0, we have
P (‖wj − w∗‖ > ǫ) <
G2
ǫ2σ2
(
6 + ln j
j
)
, j ≥ 1. (44)
Proof From the proof of Xiao (2010, Corollary 4), we have
E‖wj − w∗‖2 ≤
G2
σ2
(
6 + ln j
j
)
, j ≥ 1.
The claim follows from the Markov inequality.
4.2 Identification
In this subsection, we state the main identification results. We start with a result from
Hare and Lewis (2004), stating it in a modified form that is useful for our analysis below.
Theorem 15 Suppose that φ is partly smooth at the minimizer w∗ relative to the optimal
manifold M and that the nondegeneracy condition (16) holds. Then there exists a threshold
ǫ¯ > 0 such that for all w ∈ O with ‖w − w∗‖ < ǫ¯ and dist (0, ∂φ(w)) < ǫ¯, we have w ∈ M.
Proof Suppose for contradiction that no such ǫ¯ exists. Let {ǫj}j≥1 be any sequence of
positive numbers such that ǫj ↓ 0. Then for each j ≥ 1 we have wj such that ‖wj−w∗‖ < ǫj ,
dist (0, ∂φ(wj)) < ǫj but wj /∈ M. Considering the sequence {wj}j≥1, we have that
wj → w∗, and dist (0, ∂φ(wj)) → 0. With convexity, these imply φ(wj) → φ(w∗), since
for all aj ∈ ∂φ(wj) we have φ(wj) − φ(w∗) ≤ aTj (wj − w∗) ≤ ‖aj‖‖wj − w∗‖. Convexity
implies prox-regularity, so by applying Theorem 5.3 of Hare and Lewis (2004), we have that
wj ∈ M for all j sufficiently large. This contradicts our choice of wj , so we conclude that
ǫ¯ > 0 with the claimed properties exists.
18
Manifold Identification for Regularized Stochastic Online Learning
The next theorem is our main result, showing that the RDA algorithm identifies the
optimal manifold with increasing probability as iterations proceed. This result requires a
condition (45) on h that is trivially satisfied by the usual prox-function h(w) = ‖w−w1‖22.
Theorem 16 (Identification for General Convex Case) Suppose that Assumptions 1
and 2 hold, that w∗ ∈ FD, that
sup
bj∈∂h(wj)
‖bj‖ ≤ η‖wj − w1‖, j = 1, 2, . . . (45)
for some η > 0, and that {βt} is defined as in (25). Given S defined in (37), we have
P(wj ∈ M) ≥ 1− (ζ1 + ζ2)j−1/4
for all j ∈ S sufficiently large, where
ζ1 :=
3max(1, L)
ǫ¯
(
3max(1, L)
ǫ¯ +
1
r¯
)
, and ζ2 := 1.2
(
3
ǫ¯
)2
ν.
Here ǫ¯ > 0 has the value defined in Theorem 15, L is the Lipschitz constant of (13), r¯ is
the radius of strong convexity from (11), and ν is defined in (36a).
Proof We focus on the iterate wj and the random events associated with it. First we
denote the following event as E1:
E1 : ‖wj − w∗‖ ≤
ǫ¯
3max(L, 1) . (46)
Note that E1 depends on the history ξ[j−1] of random variables prior to iteration j. If E1
is true, it trivially implies the condition ‖wj − w∗‖ ≤ ǫ¯ of Theorem 15. From Lemma 13,
with ǫ = ǫ¯3max(L,1) , we have that
P(‖wj − w∗‖ ≤ ǫ¯) ≥ P(E1) ≥ 1− ζ1j−1/4. for all j ∈ S, (47)
We now examine the other condition in Theorem 15, namely
dist
(
0,∇f(wj) + ∂Ψ(wj)
)
≤ ǫ¯.
By adding and subtracting terms, we obtain
∇f(xj) + aj = (∇f(wj)−∇f(w∗)) + (∇f(w∗)− g¯j−1)−
βj−1
j − 1bj
+
(
g¯j−1 + aj +
βj−1
j − 1bj
)
. (48)
for any aj ∈ ∂Ψ(wj) and bj ∈ ∂h(wj). We choose the specific aj and bj that satisfy the
optimality of the subproblem (24), that is,
0 = g¯j−1 + aj +
βj−1
j − 1bj . (49)
This choice eliminates the last term in (48). For the other three terms, we have the following
observations.
19
Lee and Wright
(i) For those wj satisfying E1, the Lipschitz property of ∇f (Lemma 2) implies that
‖∇f(wj)−∇f(w∗)‖ ≤ L‖wj − w∗‖ ≤
L
3max(L, 1) ǫ¯ ≤
ǫ¯
3
.
Hence, E1 implies the following event:
E2 : ‖∇f(wj)−∇f(w∗)‖ ≤ ǫ¯/3.
(ii) From Theorem 12, we have by setting ǫ = ǫ¯/3 and t = j − 1 that
P(‖∇f(w∗)− g¯j−1‖ > ǫ¯/3) <
(
3
ǫ¯
)2
ν(j − 1)−1/4 < ζ2j−1/4, j ≥ 2.
Hence, denoting by E3 the event
E3 : ‖∇f(w∗)− g¯j−1‖ ≤ ǫ¯/3,
we have that
P(¬E3) < ζ2j−1/4, j ≥ 2. (50)
(iii) Since βj−1 = γ(j − 1)1/2, we have for wj satisfying E1 that
βj−1
j − 1‖bj‖ = γ(j − 1)
−1/2‖bj‖
≤ γη(j − 1)−1/2‖wj − w1‖ from (45)
≤ γη(j − 1)−1/2(‖wj − w∗‖+ ‖w1 − w∗‖)
≤ γη(j − 1)−1/2
( ǫ¯
3max(L, 1) +D
)
from w∗ ∈ FD.
Therefore, E1 implies the event
E4 :
βj−1
j − 1‖bj‖ ≤
ǫ¯
3
, j ≥ j0,
where we define j0 by
j0 := 1 +
⌈
9γ2η2
ǫ¯2
( ǫ¯
3max(L, 1) +D
)2
⌉
.
Therefore for j ∈ S with j ≥ j0, by definition of the events E1, E2, E3, and E4 above, the
probability that the conditions of Theorem 15 hold is bounded as follows:
P
(
‖wj − w∗‖ ≤ ǫ¯ ∧ dist (0, ∂φ(wj)) < ǫ¯
)
≥ P
(
E1 ∧ E2 ∧ E3 ∧ E4
)
= P(E1 ∧ E3)
≥ 1− P(¬E1)− P(¬E3) ≥ 1− (ζ1 + ζ2)j−1/4,
where the last inequality is due to (47) and (50). Our claim follows.
20
Manifold Identification for Regularized Stochastic Online Learning
Theorem 17 (Identification for Strongly Convex Case) Suppose that Assumptions 1
and 2 hold, that Ψ is strongly convex with the modulus σ > 0, that w∗ ∈ FD, that h(·) sat-
isfies (45), and that {βt} is defined as in (26). Then we have
P(wj ∈ M) ≥ 1− (ζ ′1 + ζ ′2)
(
6 + ln j
j
)1/2
.
for all j ≥ 9, where
ζ ′1 :=
G2
σ2
(
3max(1, L)
ǫ¯
)2
, and ζ ′2 := 1.8
(
3
ǫ¯
)2
ν ′.
Here ǫ¯ > 0 has the value defined in Theorem 15, L is the Lipschitz constant of (13), r¯ is
the radius of strong convexity from (11), and ν ′ is defined in (36b).
Proof This proof is almost identical to that of Theorem 16; here we briefly mention the
required changes for the strongly convex case. Consider ǫ¯ > 0 and the event E1 defined in
the proof of Theorem 16. From Lemma 14 with ǫ = ǫ¯3max(L,1) , we have
P(‖wj − w∗‖ ≤ ǫ¯) ≥ P(E1) ≥ 1− ζ ′1(6 + ln j)/j, j ≥ 1.
Instead of (ii) and (iii) in the proof of Theorem 16, we use the following:
(ii’) From Theorem 12, we have by setting ǫ = ǫ¯/3 and t = j − 1 that
P(‖∇f(w∗)−g¯j−1‖ > ǫ¯/3) <
(
3
ǫ¯
)2
ν ′
(
6 + ln(j − 1)
j − 1
)1/2
< ζ ′2
(
6 + ln j
j
)1/2
, j ≥ 2.
Hence, denoting by E3 the event ‖∇f(w∗)− g¯j−1‖ ≤ ǫ¯/3, we have that
P(¬E3) < ζ ′2
(
6 + ln j
j
)1/2
, j ≥ 2.
(iii’) With βj−1 = 0 and the given conditions, the event E4 holds for all j ≥ 2.
Using the modified probability bounds for E1 and E3, we have
P
(
‖wj − w∗‖ ≤ ǫ¯ ∧ dist (0, ∂φ(wj)) < ǫ¯
)
≥ P
(
E1 ∧ E3
)
≥ 1− ζ ′1
(
6 + ln j
j
)
+ ζ ′2
(
6 + ln j
j
)1/2
≥ 1− (ζ ′1 + ζ ′2)
(
6 + ln j
j
)1/2
,
for all j ≥ 9, using the fact that (6 + ln j)/j ≤ 1 for j ≥ 9. Our claim follows.
Lemma 13 tells us that the sequence S is “dense” in {1, 2, . . . }, while Theorem 16
states that for all sufficiently large j ∈ S, wj lies on the optimal manifold with probability
approaching one as j increases. When the regularizer Ψ is strongly convex, Theorem 17
tells that similar results holds earlier in the sequence {wj}.
21
Lee and Wright
5. Enhancing the Regularized Dual Averaging Algorithm
Here we present a simple optimization strategy motivated by our analysis above, in which
the RDA method gives way to a local phase after a near-optimal manifold is identified.
Algorithm 2 summarizes our algorithm RDA+. This algorithm starts with RDA steps
until it identifies a near-optimal manifold, then searches this manifold using a different
optimization strategy, possibly better suited to lower-dimensional spaces and possibly with
better local convergence properties. If an explicit parametrization of M is available, the
“local phase” could take the form of a Newton-like method applied to the composition of
the objective with this parametrization. In the important special case of Ψ(·) = λ‖ · ‖1, M
can be represented simply by its nonzero variables, and LPS (Shi et al., 2008; Wright, 2010)
can be applied on the space of just these variables. The LPS approach, as implemented
here, evaluates partial gradients (the restriction of the gradients to the active manifold),
enhancing the steps with (approximate) second-order information.
To decide when to make the switch to the local phase, we use a simple heuristic inspired
by Theorem 16 and 17 that if the past τ consecutive iterates have been on the same manifold
M, we take M to be approximately optimal. However, we “safeguard” by expanding M
to incorporate additional dimensions that may yet contain the minimizer. This simple
approach will work provided that theM so constructed is a superset of the optimal manifold,
since our implementation of the local phase is able to move to more restricted submanifolds
of M but does not expand its search to include dimensions not originally included in the
manifold. When sufficient progress is not attained in the local phase, we can resume the
paused dual-averaging phase.
We describe the details of Algorithm 2 for ℓ1 regularization, where Ψ(w) = λ‖w‖1 for
some λ > 0. (Thus w1 = 0.) The optimal manifold corresponds (near w∗) to the points in
Rn that have the same nonzero patterns as w∗. Suppose that we use the simple quadratic
prox-function h(w) = ‖w−w1‖2. Since Ψ is not strongly convex, we use the sequence {βt}
defined in (25).
We now describe various specifics of the implementation of Algorithm 2 for this case.
Computation of wj+1: The closed-form solution for the subproblem (24) is
[wt+1]i =
√
t
2γ soft(−[g¯t]i, λ), i = 1, 2, . . . , n,
where soft(u, a) := sgn(u)max{|u| − a, 0} is the well-known soft-threshold function.
Surrogate Objective: To apply the batch optimization method LPS in the local phase of
Algorithm 2, we use an empirical estimate φ˜N in (3) as a surrogate objective function (where
ξj , j ∈ N is a sample of random variables from the space Ξ according to the distribution
P ), and then solve
min
w∈M
φ˜N (w) = f˜N (w) + λ‖w‖1.
Note that ‖ · ‖1 behaves like a smooth function on the optimal manifold in a neighborhood
of w∗. LPS calculates first- and second-order information for φ˜N on the subset of compo-
nents defined by M. Since the intrinsic dimension of M is usually much smaller than the
dimension n of the full space, these restricted gradients and Hessians are much cheaper to
compute than their full-space counterparts.
22
Manifold Identification for Regularized Stochastic Online Learning
Algorithm 2 RDA+ Algorithm.
1: Input:
• a prox-function h(w) that is strongly convex on domΨ and also satisfies
argmin
w
h(w) ∈ argmin
w
Ψ(w),
sup
bj∈∂h(wj)
‖bj‖ ≤ η‖w − w1‖, ∀w ∈ domΨ, where w1 ∈ argmin
w
Ψ(w).
• a nonnegative and nondecreasing sequence {βt}, t ≥ 1.
• a positive integer τ .
2: Initialize: Set g¯0 = 0.
3: Dual Averaging:
4: for j = 1, 2, . . . do
5: Choose a random vector ξj ∈ Ξ.
6: Compute a gradient gj = ∇F (wj ; ξj).
7: Update the average gradient:
g¯j =
j − 1
j g¯j−1 +
1
j gj .
8: Compute the next iterate by solving the subproblem (24), which is
wj+1 = argmin
w∈Rn
{
〈g¯j , w〉+Ψ(w) +
βt
t h(w)
}
. (51)
9: if there is M such that wj+2−i ∈ M for i = 1, 2, . . . , τ then
10: Local Phase:
11: Safeguard M by adding dimensionality as appropriate to encompass w∗;
12: Use a technique for low-dimensional optimization to search for a solution on man-
ifold M, starting at wj+1;
13: end if
14: end for
Checking Optimality: From the optimality condition for (3), we define the optimality
measure δ(wj) as follows,
δ(wj) :=
1√n infaj∈∂‖wj‖1
‖∇f˜N (wj) + λaj‖. (52)
Since δ(w∗) ≈ 0 for a sufficiently large sample set N because of the law of large numbers,
it makes sense to terminate when δ(wj) drops below a certain threshold.
Safeguarding: At the start of the local phase, we augment M by adding components i for
which [wj+1]i = 0 but [g¯j ]i is close to one of the endpoints of its allowable range; that is,
[wj+1]i = 0 and |[g¯j ]i| > ρλ (53)
23
Lee and Wright
for some ρ between 0 and 1 (but closer to 1). Since g¯j approaches ∇f(w∗) in probability
(see Theorem 12), it is possible that |[g¯j ]i| will approach λ on a later iteration, and so [wj ]i
may move away from 0.
6. Computational Experiments
We report here on computational experiments involving binary classification tasks via ℓ1-
regularized logistic regression. Given a set of m training examples, we select one at time t
— indexed by ξt — and use its feature vector xξt ∈ Rn−1 and label yξt ∈ {−1, 1} to define
the corresponding loss function for w˜ ∈ Rn−1, b ∈ R and w = (w˜, b):
F (w; ξt) = log
(
1 + exp
(
−yξt(w˜Txξt + b)
))
.
We choose Ψ(w) = λ‖w˜‖1 as the regularizer for some λ > 0, and set w1 = 0, as required in
Algorithm 2.
For the second phase of Algorithm 2, we obtain the empirical estimate φ˜N from the full
training set.
6.1 Manifold Identification
To investigate the identification behavior of the RDA algorithm in practical circumstances,
we use five data sets from the UCI Machine Learning Repository, which have the sizes /
dimensions shown in Table 1. We apply the original LPS to acquire the reference solution
w∗N of (3), with the tight optimality threshold of 10−6. We then tabulate how many
iterations of RDA are required before it generates a point in the optimal manifold M
containing w∗N . We also check when the iterates of RDA reach a modest superset of the
optimal manifold — a “2×” superset composed of the points in Rn having the same sign
pattern for the active components in M, and up to twice as many nonzeros as the points
in M. For each data set we use three values of λ equally spaced in the log-scale range of
[0.3, 0.9]λmax, where λmax, computed accordingly to Koh et al. (2007), is the value beyond
which the solution w∗ has all zero components, except for the intercept term.
Table 1 shows performance of the RDA algorithm, over 100 repeated runs for each data
set (using random permutations of training data for each run and for each sweep through
the data), as measured by the number of iterations required for the algorithm to identify
the optimal manifold and its 2× superset. Since the empirical distributions of the iteration
counts are skewed, we show the median (rather than the mean) and the standard deviation.
The table also shows the values of the optimality measure δ defined in (52) for the iterate
at the moment we identify the optimal manifold. These results demonstrate that a huge
number of iterations may be required to identify the optimal manifold, whereas identifying
the superset is often much easier. In cases in which only a few components of w∗N are
nonzero, just a small fraction of the training examples usually suffice to identify the 2×
superset. We note too that even when optimal identification is achieved, the iterate is still
far from being optimal (by the criterion (52)), suggesting the need for a local phase to
achieve tighter optimality.
24
Manifold Identification for Regularized Stochastic Online Learning
Table 1: Manifold identification properties of the RDA algorithm over 100 runs for each data
set. The median number of iterations required to identify the optimal manifold M,
and the number required to identify a 2× superset, are presented, along with the
standard deviations over the 100 tests (in parentheses). δ represents the optimality
measure at the moment of identifying M, while the last column shows the number
of nonzeros in the reference solution obtained by LPS.
Data set λ 2× Superset Optimal M Optimality δ NNZs w∗N
Glass
(m = 214, n = 10)
0.29 14 (25) 20 (27) 0.068 1
0.17 13 (10) 116 (428) 0.063 2
0.10 13 (11) 28392 (6907) 0.016 3
Iono
(m = 351, n = 35)
0.22 38 (84) 122 (95) 0.015 2
0.13 44 (28) 30812 (15575) 0.008 3
0.07 86 (41) 404 (150) 0.019 5
Arrhythmia
(m = 452, n = 280)
0.15 192 (110) 304 (141) 0.001 2
0.09 272 (88) 2036 (1076) 0.002 8
0.05 447 (195) 27750 (4590) 0.001 13
Spambase
(m = 4601, n = 58)
0.17 137 (219) 357 (325) 0.006 1
0.10 722 (2495) 4340 (3097) 0.004 8
0.06 812 (1247) 4680 (2209) 0.004 17
Pageblock
(m = 5473, n = 11)
0.11 26 (326) 58 (395) 0.063 1
0.07 182 (941) 524 (1233) 0.038 3
0.04 103 (913) 461 (1232) 0.040 4
6.2 Performance on the MNIST Dataset
We now focus on the effects of the local phase on the performance of RDA+. For this
purpose, we use the MNIST data set which consists of gray-scale images of digits represented
by 28×28 pixels. We choose the binary classification problem of distinguishing between the
digits 6 and 7, for which the data set has 12183 training and 1986 test examples. Although
the “6 vs 7” task is relatively easy, we choose this setting so that we can compare our results
to those reported in Xiao (2010) for the original RDA algorithm.
We compare RDA+ to several other algorithms: SGD, TG, RDA, and LPS. The SGD
method (for instance, Nemirovski et al., 2009) for ℓ1 regularization consists of the iterations
[wt+1]i = [wt]i − αt
(
[gt]i + λsgn ([wt]i)
)
, i = 1, 2, . . . , n,
where gt is a sampled approximation to the gradient of f at wt, obtained from a single
training example. The TG method (Langford et al., 2009) truncates the iterates obtained
by the standard SGD at every Kth step (where K is a user-defined constant). That is,
[wt+1]i =
{
trnc
(
[wt]i − αt[gt]i, λTGt , θ
)
if mod(t,K) = 0,
[wt]i − αt[gt]i otherwise,
(54)
25
Lee and Wright
where λTGt := αtλK, mod(t,K) is the remainder on division of t by K, θ is a user-defined
constant, and
trnc(ω, λTGt , θ) =





0 if |ω| ≤ λTGt
ω − λTGt sgn(ω) if λTGt < |ω| ≤ θ,
ω otherwise.
We follow Xiao (2010) in using θ = ∞ and K = 10.
For the stepsize αt in SGD and TG, we adopt a variable stepsize scheme (Zinkevich,
2003; Nemirovski et al., 2009), choosing αt to be a multiple of 1/
√
t so that the methods
can achieve regret bounds of O(
√
t) similar to that of RDA. (The derivation, which follows
the analysis of Zinkevich (2003), is given in Appendix C.)
In our implementations of RDA+ and RDA, we set γ = 5000 in (25). (This value is
determined by cross validation with RDA, using a single scan through the data set.) For
LPS and the local phase of RDA+, we compute a reduced Newton step on the current
active manifold only when the number of nonzeros falls below 200. We also use the full set
of training examples to compute the reduced gradient and reduced Hessian of the surrogate
function fN .
For SGD, TG, and RDA, we keep track not only of the primal iteration sequence {wt},
but also the primal averages w¯T := 1T
∑T
t=1wt, where T for each algorithm denotes the
iteration number where the algorithm is stopped. We include these in the comparison
because the convergence of the stochastic subgradient algorithms are often described in
terms of the primal averages. Note that RDA+ and LPS do not make use of primal averages.
We first run the RDA+ algorithm with random permutations of the training samples,
stopping when τ = 100 consecutive iterates have the same sparsity pattern, after seeing all
samples at least once. (All repeated runs required at most 19327 iterations to stop, which is
less than two complete sweeps through the data set.) In the safeguarding test (53), we use
ρ = 0.85. We run the local phase of RDA+ until the optimality measure in (52) falls below
10−4. We record the total runtime of the RDA+ algorithm, then run other algorithms SGD,
TG, RDA, and LPS up to the runtime of RDA+, stopping them earlier if they achieve the
desired optimality before that point.
Progress in Time. We compare the convergence of the algorithms in terms of the opti-
mality measure and the number of nonzero components. Figure 1 presents the plots for the
iterates without averaging, for three different values of λ: 10, 1, and 0.1. The optimality
plots (on the left) show that RDA+ achieves the target optimality much faster than other
algorithms, including LPS. RDA behaves better than SGD and TG, but still does not come
close to the target value of optimality. There is only a modest decrease in the optimality
measure for SGD, TG, and RDA over the time frame of this experiment.
The plots on the right of Figure 1 show the number of nonzeros in the iterates. RDA
tends to produce much sparser iterates with less fluctuation than SGD and TG, but it fails
to reduce the number of nonzeros to the smallest number identified by RDA+ in the given
time, for the values λ = 1.0 and λ = 0.1.
In its local phase, RDA+ behaves very similarly to LPS, sharing the typical behavior
of nonmonotonic decrease in the optimality measure (52). However, the local phase often
26
Manifold Identification for Regularized Stochastic Online Learning
converges faster than LPS, because it starts with the reduced space chosen by the dual-
averaging phase of RDA+. The number of nonzeros often increases at the point of switching
between phases, since the safeguarding can add more elements to the nonzero set.
Figure 2 shows similar plots but for the primal averaged iterates w¯t. We duplicate
the plots of RDA+ and LPS (which do not use iterate averaging) from Figure 1 for easy
comparison. The number of nonzeros components is clearly higher for averaged iterates.
Quality of Solutions. In Figure 3, we compare the quality of the solutions in terms of
optimality, the number of nonzeros, and test error rate. We present the results for the
iterates without averaging in the three plots on the left, and those for the primal-averaged
iterates (for algorithms SGD, TG, and RDA) in the plots on the right. (The plots of RDA+
and LPS on the left are duplicated in the right-hand plots for easy comparison.) We run the
algorithms with the same setting used in the previous experiments, except for LPS, which
we run to optimality (10−4, without time limit) to provide as baseline for comparison.
(The runtime of LPS was about four times longer than that of RDA+ on average.) The
experiments are repeated for 100 runs of the data (using random permutations of training
data for each run and for each sweep through the data), for each of seven λ values in the
interval [.01, 10]. (The value of λmax for this data set is 45.8.)
In Figure 3, only the solutions from RDA+ achieve the desired optimality and the
smallest number of nonzeros, with almost identical quality to the solutions from LPS. The
solutions (both with and without averaging) from SGD, TG, and RDA are suboptimal,
leaving much scope for zeroing out many more components of the iterates. RDA achieves a
similar number of nonzeros to RDA+ for large λ values, but more nonzeros for smaller values
of λ. In terms of the test error rate, RDA+ produces slightly better solutions than SGD,
TG, and RDA overall. Although the improvement is marginal, we note that high accuracy is
difficult to achieve solely with the stochastic online learning algorithms in limited time. The
averaged iterates of SGD and TG show smaller test error for λ ≥ 1 than others, but they
require a large number of nonzero components, despite the strong regularization imposed.
In Figure 4, we show the typical solutions from the algorithm runs, for different λ
values. The first three rows present the solutions acquired without averaging, and the
last three rows present those obtained with primal averaging. The solutions from RDA+
reveal almost identical sparsity pattern to those from the baseline algorithm LPS, achieving
smallest nonzero patterns. For large λ values, RDA produces similar sparse solutions to
RDA+, but much denser solutions for smaller values. Again, we see that primal-averaged
solutions are denser than those without averaging.
7. Conclusion
We have shown that the RDA algorithm identifies the optimal manifold with probability
approaching one as iterations proceed. This observation enables us to develop a new al-
gorithmic framework that enjoys the low computational footprint of stochastic gradient
methods in the ambient space identifying near-optimal manifolds, as well as the rapid lo-
cal convergence of Newton-type optimization techniques by searching for solutions on the
manifolds that often have much lower intrinsic dimension than the full space.
27
Lee and Wright
O
pt
im
al
it
y
(λ
=
10
)
0 1 2 3 4 5 6 7 8
10−4
10−3
10−2
10−1
100
101
102
 
 
SGD
TG
RDA
RDA+
LPS
N
N
Z
s
(λ
=
10
)
0 1 2 3 4 5 6 7 8
0
100
200
300
400
500
600
700
O
pt
im
al
it
y
(λ
=
1.
0)
0 5 10 15 20 25 30 35 40
10−4
10−3
10−2
10−1
100
101
102
N
N
Z
s
(λ
=
1.
0)
0 5 10 15 20 25 30 35 40
0
100
200
300
400
500
600
700
O
pt
im
al
it
y
(λ
=
0.
1)
0 50 100 150
10−4
10−3
10−2
10−1
100
101
102
N
N
Z
s
(λ
=
0.
1)
0 50 100 150
0
100
200
300
400
500
600
700
Runtime (second) Runtime (second)
Figure 1: Convergence of iterates for various algorithms applied to an ℓ1-regularized logistic
regression function constructed from the digits 6 and 7 in the MNIST data set.
Convergence is measured in terms of the optimality measure (left) and the number
of nonzero components in the iterates (right). SGD, TG, RDA, and LPS are run
up to the time taken for RDA+ to achieve 10−4 optimality value. The vertical
dot-dashed lines indicate the event of phase switching in RDA+. The vertical
axes on the left are in logarithmic scale.
28
Manifold Identification for Regularized Stochastic Online Learning
O
pt
im
al
it
y
(λ
=
10
)
0 1 2 3 4 5 6 7 8
10−4
10−3
10−2
10−1
100
101
102
 
 
SGD
TG
RDA
RDA+
LPS
N
N
Z
s
(λ
=
10
)
0 1 2 3 4 5 6 7 8
0
100
200
300
400
500
600
700
O
pt
im
al
it
y
(λ
=
1.
0)
0 5 10 15 20 25 30 35 40
10−4
10−3
10−2
10−1
100
101
102
N
N
Z
s
(λ
=
1.
0)
0 5 10 15 20 25 30 35 40
0
100
200
300
400
500
600
700
O
pt
im
al
it
y
(λ
=
0.
1)
0 50 100 150
10−4
10−3
10−2
10−1
100
101
102
N
N
Z
s
(λ
=
0.
1)
0 50 100 150
0
100
200
300
400
500
600
700
Runtime (second) Runtime (second)
Figure 2: Convergence of averaged iterates (for SGD, TG, and RDA) and original iterates
(for RDA+ and LPS) on the ℓ1-regularized logistic regression function constructed
from the digits 6 and 7 in the MNIST data set. Convergence is measured in terms
of the optimality measure (left) and the number of nonzero components in the
iterates (right). SGD, TG, RDA and LPS are run up to the time taken for RDA+
to achieve 10−4 optimality value. The vertical dot-dashed lines indicate the event
of phase switching in RDA+. The vertical axes on the left are in logarithmic
scale.
29
Lee and Wright
Left: iterates without averaging Right: primal averages
O
pt
im
al
it
y
0.01 0.1 1 10
10−6
10−4
10−2
100
102
 
 
SGD
TG
RDA
RDA+
LPS (baseline)
0.01 0.1 1 10
10−6
10−4
10−2
100
102
N
N
Z
s
0.01 0.1 1 10
  0
100
200
300
400
500
600
700
0.01 0.1 1 10
  0
100
200
300
400
500
600
700
E
rr
or
R
at
e
0.01 0.1 1 10
10−3
10−2
10−1
0.01 0.1 1 10
10−3
10−2
10−1
Regularization Parameter λ Regularization Parameter λ
Figure 3: Quality of solutions (MNIST 6 vs. 7) in terms of the optimality, the number of
nonzero components, and the test error rate, measured for 100 different random
permutations of the training set. The plots on the left show the results for the
iterates without averaging, and those on the right show averaged primal iterates
for algorithms SGD, TG, and RDA, and non-averaged iterates for RDA+ and
LPS. The SGD, TG, and RDA algorithms are run up to the time taken for
RDA+ to achieve a 10−4 threshold in the measure (52), whereas LPS is run to
convergence. All axes are in logarithmic scale, except for the vertical axes in the
second row.
30
Manifold Identification for Regularized Stochastic Online Learning
λ 0.01 0.05 0.1 0.5 1.0 5.0 10.0
SG
D
(w
T
)
T
G
(w
T
)
R
D
A
(w
T
)
R
D
A
+
(w
T
→
w
∗ N
)
L
P
S
(w
∗ N
)
SG
D
(w¯
T
)
T
G
(w¯
T
)
R
D
A
(w¯
T
)
Figure 4: Sparsity patterns of the solutions for classification of the digits 6 and 7 in the
MNIST data set. The regularization parameter λ is varied in the range of
[0.01, 10]. The spots represent the positive (bright) and negative (dark) values,
whereas the gray background represents zero. The top three rows show the solu-
tions acquired without averaging, and the bottom three rows show those obtained
with primal averaging. The two rows in the middle presents the solutions from
RDA+ and LPS. The algorithms SGD, TG, and RDA are run up to the time
taken for RDA+ to achieve a solution with 10−4 optimality value; the batch algo-
rithm LPS is run without time limit. Note that for each value of λ, the sparsest
solutions are obtained by RDA+ and LPS.
31
Lee and Wright
Acknowledgments
We thank our colleague Ben Recht for helpful comments and discussions.
This research was supported in part by National Science Foundation Grant DMS-
0914524.
Appendix A. Proofs: Strong Minimizer Property
In this section we prove Theorem 5 and its corollaries stated in Section 2.5, based on results
from manifold analysis and other elementary arguments. Our proof is similar to that of
Wright (2010, Theorem 2.5), but simpler.
We first state an elementary result on manifold characterization, which is proved in
Vaisman (1984, Sections 1.4–1.5) and Wright (2010, Appendix A.).
Lemma 18 Let the manifold M ⊂ Rn containing z¯ be characterized by a Cp (p ≥ 2)
function H : Rn → Rk. Then there is y¯ ∈ Rn−k and a Cp function G mapping some
neighborhood of y¯ to Rn such that G(y) ∈ M for all y near y¯. Moreover, G(y) − z¯ =
Y (y− y¯)+O(‖y− y¯‖2), where Y ∈ Rn×(n−k) is an orthonormal matrix whose columns span
the tangent space to M at z¯.
The next result from Wright (2010) shows how perturbations from a point at which the
objective function is partly smooth can be decomposed according to the manifold charac-
terization above.
Lemma 19 Let the manifold M ⊂ Rn be characterized in a neighborhood of z¯ ∈ M by Cp
mappings H : Rn → Rk and G : Rn−k → Rn and the point y¯ described in Lemma 18. Then
for all z near z¯, there are unique vectors y ∈ Rn−k and v ∈ Rk with ‖(yT − y¯T , vT )‖ =
O(‖z − z¯‖) such that z = G(y) +∇H(z¯)v.
We also make use of a result from Wright (2010, Lemma A.1).
Lemma 20 Consider a function ϕ : Rn → R, a point z¯ ∈ Rn, and a manifold M containing
z¯ such that ϕ is partly smooth at z¯ with respect to M. If the nondegeneracy condition
0 ∈ ri ∂ϕ(z¯) holds, then there exists ǫ > 0 such that
sup
g∈∂ϕ(z¯)
〈g, d〉 ≥ ǫ‖d‖, ∀d ∈ NM(z¯).
Proof (Theorem 5) We now proceed with the proof of the main result of Section 2.5.
Recall the following assumptions:
(i) φ is partly smooth at w∗ relative to the optimal manifold M.
(ii) w∗ is a locally strong minimizer of φ|M with modulus cM > 0 and radius rM > 0,
and
(iii) the nondegeneracy condition (16) holds at w∗.
32
Manifold Identification for Regularized Stochastic Online Learning
For the minimizer w∗ of (1) and the optimal manifold M containing w∗, we consider
the mappings H and G, the matrix Y , and the point y¯ ∈ Rn−k satisfying Lemma 18
and Lemma 19, associated with z¯ = w∗ ∈ Rn. From Lemma 19, for all w satisfying
‖w − w∗‖ ≤ r¯ ≤ rM with small enough r¯ > 0, we can find unique vectors y ∈ Rn−k and
v ∈ Rk with ‖(yT − y¯T , vT )‖ = O(‖w − w∗‖) such that w = G(y) + ∇H(w∗)v. Therefore
we have
φ(w)− φ(w∗) = [φ(G(y) +∇H(w∗)v)− φ(G(y))] + [φ(G(y))− φ(w∗)] . (55)
From the locally strong minimizer property relative to M and the facts that w∗ ∈ M and
G(y) ∈ M for all y near y¯, we have for the second bracketed term that
φ(G(y))− φ(w∗) = φ|M(G(y))− φ|M(w∗) ≥ cM‖G(y)− w∗‖2 (56)
for all y near y¯. Consider next the first bracketed term of (55). From Lemma 20, we have
ǫ > 0 such that supg∈∂φ(w∗)〈g, d〉 ≥ ǫ‖d‖ for all d ∈ NM(w∗). From the subcontinuity
property (iv) from Definition 4, we can choose a neighborhood of w∗ sufficiently small that
for all g ∈ ∂φ(w∗), there exists gˆ ∈ ∂φ(G(y)) such that ‖gˆ− g‖ ≤ ǫ/2. These facts, together
with convexity of φ, imply that for all y near y¯ and v near 0 we have
φ(G(y) +∇H(w∗)v)− φ(G(y)) ≥ sup
gˆ∈φ(G(y))
〈gˆ,∇H(w∗)v〉
≥ sup
g∈∂φ(w∗)
〈g,∇H(w∗)v〉 − (ǫ/2)‖∇H(w∗)v‖
≥ ǫ‖∇H(w∗)v‖ − (ǫ/2)‖∇H(w∗)v‖.
By substituting this inequality and (56) into (55), we obtain
φ(w)− φ(w∗) ≥ (ǫ/2)‖∇H(w∗)v‖+ cM‖G(y)− w∗‖2.
By further reducing r¯ if necessary, we can choose the neighborhood of w∗ small enough to
ensure that ‖∇H(w∗)v‖ ≤ 1, and therefore
φ(w)− φ(w∗) ≥ (ǫ/2)‖∇H(w∗)v‖2 + cM‖G(y)− w∗‖2
≥ min(ǫ/2, cM)
[
‖∇H(w∗)v‖2 + ‖G(y)− w∗‖2
]
≥ 12 min(ǫ/2, cM)
[
‖∇H(w∗)v‖+ ‖G(y)− w∗‖
]2
≥ 12 min(ǫ/2, cM)‖w − w∗‖2.
(The third inequality follows from the elementary bound (a2 + b2) ≥ 12(a + b)2, for any
scalars a and b.) We have thus shown that w∗ indeed is a local strong minimizer of φ,
without the restriction to the manifold M, with the modulus c := min(ǫ/2, cM) and the
radius r¯.
We follow with the proofs of the remaining results of Section 2.5.
Proof (Corollary 6) Given w ∈ O with ‖w − w∗‖ > r¯, we have from the convexity of φ
that
φ
(
w∗ + r¯ w − w
∗
‖w − w∗‖
)
≤ φ(w∗) + r¯‖w − w∗‖(φ(w)− φ(w
∗)).
33
Lee and Wright
From the locally strong minimizer property of w∗, we also have
φ
(
w∗ + r¯ w − w
∗
‖w − w∗‖
)
− φ(w∗) ≥ c
∥
∥
∥
∥
(
w∗ + r¯ w − w
∗
‖w − w∗‖
)
− w∗
∥
∥
∥
∥
2
= cr¯2.
Collecting the above two inequalities leads to the claim.
Proof (Corollary 7) Given w ∈ O, if ‖w −w∗‖ ≤ r¯, then the claim follows from (19). If
‖w − w∗‖ > r¯, then we have from strong convexity of φ that
φ
(
w∗ + r¯ w − w
∗
‖w − w∗‖
)
≤ φ(w∗) + r¯‖w − w∗‖(φ(w)− φ(w
∗))
− σ
2
r¯
‖w − w∗‖
(
1− r¯‖w − w∗‖
)
‖w − w∗‖2.
From the locally strong minimizer property of w∗, we also have
φ
(
w∗ + r¯ w − w
∗
‖w − w∗‖
)
− φ(w∗) ≥ cr¯2.
Combining the above two inequalities results in
φ(w)− φ(w∗) ≥
[
σ/2 + r¯‖w − w∗‖(c− σ/2)
]
‖w − w∗‖2 ≥ min(c, σ/2)‖w − w∗‖2.
Appendix B. Proofs: Properties of the RDA Algorithm
In this section we provides the analyses for the results discussed in Section 3, regarding the
iterates generated by the RDA algorithm under our assumptions.
B.1 Expected Error Bounds of the Iterates
Proof (Lemma 9) For the general convex case, with {βt} chosen by (25), we consider the
expected regret up to time t with respect to w∗, and obtain
ERt(w∗) = E


t
∑
j=1
(F (wj ; ξj) + Ψ(wj))−
t
∑
j=1
(F (w∗; ξj) + Ψ(w∗))


=
t
∑
j=1
E
[
E
{
(F (wj ; ξj) + Ψ(wj)− F (w∗; ξj)−Ψ(w∗)) | ξ[j−1]
}]
=
t
∑
j=1
E [f(wj) + Ψ(wj)− f(w∗)−Ψ(w∗)]
=
t
∑
j=1
E [φ(wj)− φ(w∗)] . (57)
34
Manifold Identification for Regularized Stochastic Online Learning
Noting that I(‖wj−w∗‖≤r¯) + I(‖wj−w∗|>r¯) = 1, we can split the right-hand side into two sums
and obtain
ERt(w∗) =
t
∑
j=1
E
[
I(‖wj−w∗‖≤r¯){φ(wj)− φ(w∗)}
]
+
t
∑
j=1
E
[
I(‖wj−w∗‖>r¯){φ(wj)− φ(w∗)}
]
. (58)
Note that both terms on the right-hand side of (58) are nonnegative. For the first term, we
have by using the regret bound (27) and the locally strong minimizer property (19) that
(
γD2 + G
2
γ
)
t1/2 ≥ ERt(w∗)
≥
t
∑
j=1
E
[
I(‖wj−w∗‖≤r¯){φ(wj)− φ(w∗)}
]
≥ c
t
∑
j=1
E
[
I(‖wj−w∗‖≤r¯)‖wj − w∗‖2
]
,
proving the first inequality (30a). For the second inequality, we have from (58), the regret
bound (27), and Corollary 6 that
(
γD2 + G
2
γ
)
t1/2 ≥ ERt(w∗)
≥
t
∑
j=1
E
[
I(‖wj−w∗‖>r¯){φ(wj)− φ(w∗)}
]
≥ cr¯
t
∑
j=1
E
[
I(‖wj−w∗‖>r¯)‖wj − w∗‖
]
,
thus proving (30b).
When Ψ is strongly convex with the modulus σ > 0 and {βt} chosen by (26), we apply
the other regret bound (28) to (57), resulting in
G2
2σ (6 + ln t) ≥ ERt(w
∗) ≥
t
∑
j=1
E{φ(wj)− φ(w∗)} ≥ min(c, σ/2)
t
∑
j=1
E‖wj − w∗‖2,
where for the last inequality we use the fact that w∗ is a (global) strong minimizer with the
modulus min(c, σ/2), as shown in Corollary 7. This proves (31).
35
Lee and Wright
Proof (Theorem 10) We start with the general convex case. From the Cauchy-Schwartz
inequality ‖z‖1 ≤
√m‖z‖2 for a vector z ∈ Rm and Jensen’s inequality, we have
1
t
t
∑
j=1
E
[
I(‖wj−w∗‖≤r¯)‖wj − w∗‖
]
≤
√
t
t


t
∑
j=1
{
E
[
I(‖wj−w∗‖≤r¯)‖wj − w∗‖
]}2


1/2
≤


1
t
t
∑
j=1
E
[
I(‖wj−w∗‖≤r¯)‖wj − w∗‖2
]


1/2
≤ 1√c
(
γD2 + G
2
γ
)1/2
t−1/4,
where the last inequality is from (30a). Together with (30b), this leads to
1
t
t
∑
j=1
E‖wj − w∗‖
=
1
t
t
∑
j=1
E
[
I(‖wj−w∗‖≤r¯)‖wj − w∗‖
]
+
1
t
t
∑
j=1
E
[
I(‖wj−w∗‖>r¯)‖wj − w∗‖
]
≤ 1√c
(
γD2 + G
2
γ
)1/2
t−1/4 + 1r¯c
(
γD2 + G
2
γ
)
t−1/2
≤ µt−1/4,
for µ defined in (33).
For the strongly convex case, we have from Cauchy-Schwarz and Jensen’s inequalities
that
1
t
t
∑
j=1
E‖wj − w∗‖ ≤


1
t
t
∑
j=1
{E‖wj − w∗‖}2


1/2
≤


1
t
t
∑
j=1
E‖wj − w∗‖2


1/2
.
Applying the bound in (31) to the last line leads to (34).
36
Manifold Identification for Regularized Stochastic Online Learning
B.2 Properties of the Dual Average
Proof (Theorem 11) We first examine (i), for the choice of {βt} defined in (25). Recalling
that wj = wj(ξ[j−1]) is independent of the future random variables ξj , ξj+1, . . . , ξt, we have
E[g¯t] =
1
t
t
∑
j=1
E[∇F (wj ; ξj)]
=
1
t
t
∑
j=1
E
[
E[∇F (wj ; ξj) | ξ[j−1]]
]
=
1
t
t
∑
j=1
E∇f(wj) by (12)
= ∇f(w∗) + 1t
t
∑
j=1
Evj , where vj := ∇f(wj)−∇f(w∗).
From Lemma 2, we have ‖vj‖ ≤ L‖wj − w∗‖ for j = 1, 2, . . . , t, so that
‖E[g¯t]−∇f(w∗)‖ =
∥
∥
∥
∥
∥
∥
1
t
t
∑
j=1
Evj
∥
∥
∥
∥
∥
∥
≤ 1t
t
∑
j=1
‖Evj‖
≤ 1t
t
∑
j=1
E‖vj‖ by Lemma 1
≤ Lt
t
∑
j=1
E‖wj − w∗‖
≤ Lµt−1/4 by (32), (59)
proving (i).
For the strongly convex case (i’), with {βt} defined by (26), we have similarly that
‖E[g¯t]−∇f(w∗)‖ ≤
L
t
t
∑
j=1
E‖wj − w∗‖ ≤ Lµ′
(
6 + ln t
t
)1/2
, (60)
by (34).
37
Lee and Wright
Next, for (ii), we observe that
g¯t − Eg¯t
=
1
t
t
∑
j=1
(∇F (wj ; ξj)− E∇F (wj ; ξj))
=
1
t
t
∑
j=1
(
∇F (wj ; ξj)− E
[
E[∇F (wj ; ξj) | ξ[j−1]]
])
=
1
t
t
∑
j=1
(∇F (wj ; ξj)− E∇f(wj))
=
1
t
t
∑
j=1
(
{∇F (w∗; ξj)−∇f(w∗)}
+ {∇F (wj ; ξj)−∇F (w∗; ξj)} − E{∇f(wj)−∇f(w∗)}
)
=
1
t
t
∑
j=1
(ϕj + ϑj), (61)
where
ϕj := ∇F (w∗; ξj)−∇f(w∗),
ϑj := ∇F (wj ; ξj)−∇F (w∗; ξj)− E{∇f(wj)−∇f(w∗)}.
We now derive bounds on ϕj and ϑj . Note first that ϕj = ϕj(ξj) and ϑj = ϑj(ξ[j]). By
unbiasedness (12), the assumption (14), the triangle inequality, and Lemma 1, we have
Eϕj = E[∇F (w∗; ξj)−∇f(w∗)] = 0, (62)
‖ϕj‖ ≤ ‖∇F (w∗; ξj)‖+ ‖∇f(w∗)‖
= ‖∇F (w∗; ξj)‖+ ‖E∇F (w∗; ξj)‖
≤ ‖∇F (w∗; ξj)‖+ E‖∇F (w∗; ξj)‖ ≤ 2G. (63)
For ϑj , we have from (13), Lemma 1 and 2, and the triangle inequality, that
‖ϑj‖ ≤ ‖∇F (wj ; ξj)−∇F (w∗; ξj)‖+ ‖E(∇f(wj)−∇f(w∗))‖
≤ ‖∇F (wj ; ξj)−∇F (w∗; ξj)‖+ E‖∇f(wj)−∇f(w∗)‖
≤ L (‖wj − w∗‖+ E‖wj − w∗‖) . (64)
On the other hand, using (14) we have (with unbiasedness (12) and Lemma 1),
‖ϑj‖ ≤ ‖∇F (wj ; ξj)‖+ ‖∇F (w∗; ξj)‖+ ‖E∇f(wj)‖+ ‖∇f(w∗)‖
= ‖∇F (wj ; ξj)‖+ ‖∇F (w∗; ξj)‖+ ‖E∇F (wj ; ξj)‖+ ‖E∇F (w∗; ξj)‖
≤ ‖∇F (wj ; ξj)‖+ ‖∇F (w∗; ξj)‖+ E‖∇F (wj ; ξj)‖+ E‖∇F (w∗; ξj)‖
≤ 4G. (65)
38
Manifold Identification for Regularized Stochastic Online Learning
Focusing on the trace of Σt, we have
t2(tr Σt) = t2E
n
∑
ℓ=1
[g¯t − Eg¯t]2ℓ
= E
n
∑
ℓ=1


t
∑
j=1
[ϕj + ϑj ]ℓ


2
from (61)
= E
t
∑
j=1
n
∑
ℓ=1
[ϕj ]2ℓ +
n
∑
ℓ=1
∑
j 6=k
E([ϕj ]ℓ[ϕk]ℓ)
+ E
∑
j,k
( n
∑
ℓ=1
[ϕj ]ℓ[ϑk]ℓ +
n
∑
ℓ=1
[ϑj ]ℓ[ϕk]ℓ +
n
∑
ℓ=1
[ϑj ]ℓ[ϑk]ℓ
)
. (66)
Each term of (66) can be bounded as follows, using (62), (63), (64) and (65) as required:
(a)
n
∑
ℓ=1
[ϕj ]2ℓ = ‖ϕj‖2 ≤ 4G2,
(b) E([ϕj ]ℓ[ϕk]ℓ) = [Eϕj ]ℓ[Eϕk]ℓ = 0, for j 6= k,
(c)
n
∑
ℓ=1
[ϕj ]ℓ[ϑk]ℓ ≤ ‖ϕj‖‖ϑk‖ ≤ 2GL (‖wk − w∗‖+ E‖wk − w∗‖) ,
n
∑
ℓ=1
[ϑj ]ℓ[ϕk]ℓ ≤ ‖ϑj‖‖ϕk‖ ≤ 2GL (‖wj − w∗‖+ E‖wj − w∗‖) ,
(d)
n
∑
ℓ=1
[ϑj ]ℓ[ϑk]ℓ ≤ ‖ϑj‖‖ϑk‖ ≤ 4GL (‖wj − w∗‖+ E‖wj − w∗‖) .
Bound (a) uses (63). (b) uses (62) and independence of ξj and ξk, for j 6= k. (c) uses
the Cauchy-Schwartz inequality, together with (63), and (64). (d) uses Cauchy-Schwartz,
together with (64) and (65). Combining these results with (66) results in
t2(tr Σt) ≤ 4G2t+ 8GLtE
t
∑
j=1
(‖wj − w∗‖+ E‖wj − w∗‖) . (67)
The second term can be bounded as follows:
tE
t
∑
j=1
(‖wj − w∗‖+ E‖wj − w∗‖) = 2t
t
∑
j=1
E‖wj − w∗‖
= 2t2



1
t
t
∑
j=1
E‖wj − w∗‖



≤ 2t2µt−1/4, (68)
39
Lee and Wright
where the final inequality follows from (32). Applying this bound to (67), we obtain
trΣt ≤ 4G2t−1 + 16GLµt−1/4 ≤ 4G[G+ 4Lµ]t−1/4,
which implies (ii).
The corresponding strongly convex case (ii’) follows identically, until stage (68), where
we apply the bound (34) instead of (32), and thus obtain
tE
t
∑
j=1
(‖wj − w∗‖+ E‖wj − w∗‖) = 2t2



1
t
t
∑
j=1
E‖wj − w∗‖



≤ 2t2µ′
(
6 + ln t
t
)1/2
,
Applying this bound to (67) we obtain
trΣt ≤ 4G2t−1 + 16GLµ′
(
6 + ln t
t
)1/2
≤ 4G(G+ 4Lµ′)
(
6 + ln t
t
)1/2
,
which implies (ii’).
Appendix C. Regret Bound for SGD with Variable Stepsizes
In this section we discuss the regret bounds of a variable-stepsize version of the SGD al-
gorithm. As in Section 1.3, we consider regularization functions of the form Ψ(w) :=
δW(w) + ψ(w) (see (6)), for which the SGD algorithm has the form (7):
wt+1 := ΠW (wt − αt(gt + κt)) , t = 1, 2, . . . ,
where gt = ∇F (wt; ξt) and κt ∈ ∂ψ(wt). We assume that there exists H > 0 such that
supκ∈∂ψ(w) ‖κ‖ ≤ H for all w ∈ W, in addition to the earlier uniform bound (14) on ‖gt‖.
Note that (7) can be stated equivalently as
wt+1 := arg minw∈W 〈w, gt〉+ ψ(w) +
1
2αt
‖w − wt‖22,
which has a similar form to the subproblem (24) in the RDA algorithm.
Similarly to (21) (setting h(·) := ‖ ·−w1‖2), we define D to be a bound on the radius of
W around the initial iterate w1, that is,
max
w∈W
‖w − w1‖ ≤ D. (69)
Similarly to the variable stepsize scheme (Nemirovski et al., 2009, equation (2.25)) for
general convex objectives, we consider the following choice of stepsize:
αt =
D
G
θ√
t
, (70)
where θ > 0 is some constant. We present a regret bound of the SGD algorithm, extending
Theorem 1 in Zinkevich (2003). Note that for the choice (6) of regularization function,
40
Manifold Identification for Regularized Stochastic Online Learning
and assuming that w ∈ W and wj ∈ W for all j = 1, 2, . . . , t, the definition (10) of regret
function becomes
Rt(w) =
t
∑
j=1
[F (wj ; ξj) + ψ(wj)]−
t
∑
j=1
[F (w; ξj) + ψ(w)]. (71)
Theorem 21 Suppose that the iterates w1, w2, . . . are generated by the SGD algorithm (7)
applied to the problem (1), (6) with variable stepsizes (70). Then the regret (71) of SGD
up to the iteration t with respect to w∗ is bounded as follows:
Rt(w∗) ≤ D
(
2G
θ +
(G+H)2
G θ
)√
t.
Proof We assume throughout that wj ∈ W for all j, and for the solution w∗ we also have
of course that w∗ ∈ W. We define φj(w) = F (w; ξj) + ψ(w) and note that φj is convex for
all j, so that for all zj ∈ ∂φj(wj), we have
φj(wj)− φj(w∗) ≤ 〈zj , wj − w∗〉, j = 1, 2, . . . , t.
Since zj = gj + κj for gj = ∇F (wj ; ξj) and κj ∈ ∂ψ(wj), we have
‖zj‖ ≤ G+H, for all j. (72)
Summing both sizes of the expression above for j = 1, 2, . . . , t, and using (71), we obtain
Rt(w∗) =
t
∑
j=1
{φj(wj)− φj(w∗)} ≤
t
∑
j=1
〈zj , wj − w∗〉. (73)
Let vj+1 = wj − αjzj and wj+1 = ΠW(vj+1). Then
‖wj+1 − w∗‖2 ≤ ‖vj+1 − w∗‖2 (contraction due to projection)
= ‖(wj − w∗)− αjzj‖2
= ‖wj − w∗‖2 − 2αj〈zj , wj − w∗〉+ α2j‖zj‖2.
Rearranging these terms, we have
〈zj , wj − w∗〉 ≤
1
2αj
(
‖wj − w∗‖2 − ‖wj+1 − w∗‖2
)
+
αj
2
‖zj‖2.
From (69), we have maxw,w′∈W ‖w−w′‖ ≤ 2D. By combining with (73) and (72), we have
Rt(w∗) ≤
t
∑
j=1
[
1
2αj
(
‖wj − w∗‖2 − ‖wj+1 − w∗‖2
)
+
αj
2
(G+H)2
]
≤ 1
2α1
‖w1 − w∗‖2 +
1
2
t
∑
j=2
(
1
αj
− 1αj−1
)
‖wj − w∗‖2 +
(G+H)2
2
t
∑
j=1
αj
≤ (2D)2



1
2α1
+
1
2
t
∑
j=2
(
1
αj
− 1αj−1
)



+
(G+H)2
2
t
∑
j=1
αj
≤ 2D
2
αt
+
(G+H)2
2
t
∑
j=1
αj .
41
Lee and Wright
For αj defined by (70), we have
Rt(w∗) ≤ 2DG
√
t
θ +D
(G+H)2
2G θ
t
∑
j=1
1√j ≤ D
(
2G
θ +
(G+H)2
G θ
)√
t,
where the last inequality uses the fact that
∑t
j=1
1√j ≤ 1 +
∫ t
1 s−1/2ds ≤ 2
√
t.
Note that this bound is with respect to w∗, not to the minimizer of the second term in the
regret (10), as in Zinkevich (2003).
By choosing the optimal θ∗ =
√
2G/(G+H) to minimize the expression involving θ, we
can simplify the bound as
Rt(w∗) ≤ 2
√
2D(G+H)
√
t.
For ℓ1 regularization (ψ(w) = λ‖w‖1), we have H = λ, which is often much smaller than
G. If it is the case, the regret bound of SGD can be further simplified to 2
√
2DG
√
t. This
bound is comparable to the simplified regret bound of RDA, Rt(w∗) ≤ 2GD
√
t, which is
obtained by setting γ = G/D to minimize the expression (γD2+G2/γ) in the regret bound
of RDA (27) for the general convex case.
Appendix D. Identification Properties of Algorithms Based on (9)
We give here a simple example to show that algorithms based on subproblem (9) that were
discussed in Section 1.3 do not have reliable identification properties. The major reason is
that each iteration uses a “raw” sampled gradient gt of f , rather than the averaged (and
thus smoothed) approximate gradient g¯t of RDA. Thus, as we see now, even when the
current iterate wt is optimal, the subproblem may step away from this point, and off the
optimal manifold.
Consider the following definitions for the problem (1):
• n = 1 (a scalar problem)
• Ξ = [−2, 2] with ξ uniformly distributed on this interval.
• F (w; ξ) = ξw. Thus ∇F (w; ξ) = ξ and f(w) ≡ 0.
• Ψ(w) = |w|.
With these definitions, the solution is w∗ = 0 and the optimal manifold is zero-dimensional:
M = {0}. Thus Assumption 2 is trivially satisfied. Regarding Assumption 1, the nondegen-
eracy condition is satisfied, since ∂Ψ(0) = [−1, 1] while ∇f(0) = 0. It is easy to verify too
that F satisfies the unbiasedness, uniform Lipschitz, and uniform boundedness properties
of Assumption 1.
Setting wt = w∗ = 0, the subproblem (9) is
wt+1 = argminw ξtw + |w|+
1
2αt
w2,
where ξt is selected uniformly at random from [−2, 2]. For ξt ∈ [−1, 1], we have wt+1 = 0,
so the next iterate remains at the optimal point. However, if ξt ∈ [−2,−1), we have
42
Manifold Identification for Regularized Stochastic Online Learning
wt+1 = −αt(ξt + 1) > 0, while if ξt ∈ (1, 2], we have wt+1 = −αt(ξt − 1) < 0. In both
cases, the next iterate steps away from the solution w∗ = 0 and from the optimal manifold.
Because ξt is uniformly distributed in [−2, 2], this event happens with probability 1/2 in this
example. (The probability of this behavior can be made arbitrarily close to 1 by suitable
extension of the interval Ξ.)
References
M. Anitescu. Degenerate nonlinear programming with a quadratic growth condition. SIAM
Journal on Optimization, 10(4):1116–1135, 2000.
P. L. Bartlett, E. Hazan, and A. Rakhlin. Adaptive online gradient descent. In J. Platt,
D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing
Systems 20, pages 65–72, Cambridge, MA, 2008. MIT Press.
L. Bottou. Stochastic learning. In Advanced Lectures on Machine Learning, volume 3176
of Lecture Notes in Artificial Intelligence, pages 146–168. Springer Verlag, 2004.
J. V. Burke and J. J. More´. Exposing constraints. SIAM Journal on Optimization, 4(3):
573–595, 1994.
K. Chung. On a stochastic approximation method. The Annals of Mathematical Statistics,
25(3):463–483, 1954.
J. Duchi, S. Shalev-Shwartz, Y. Singer, and A. Tewari. Composite objective mirror descent.
In the 23rd Annual Conference on Learning Theory (COLT), 2010.
J. Duchi and Y. Singer. Efficient online and batch learning using forward backward splitting.
Journal of Machine Learning Research, 10:2899–2934, 2009.
W. L. Hare and A. S. Lewis. Identifying active constraints via partial smoothness and
prox-regularity. Journal of Convex Analysis, 11(2):251–266, 2004.
E. Hazan, A. Kalai, S. Kale, and A. Agarwal. Logarithmic regret algorithms for online
convex optimization. In 19th Annual Conference on Learning Theory (COLT), pages
499–513, 2006.
J. Kiefer and J. Wolfowitz. Stochastic estimation of the maximum of a regression function.
Ann. Math. Statist., 23:462–466, 1952.
K. Koh, S.-J. Kim, and S. Boyd. An interior-point method for large-scale ℓ1-regularized
logistic regression. Journal of Machine Learning Research, 8:1519–1555, 2007.
J. Langford, L. Li, and T. Zhang. Sparse online learning via truncated gradient. Journal
of Machine Learning Research, 10:777–801, June 2009.
A. S. Lewis. Active sets, nonsmoothness, and sensitivity. SIAM Journal on Optimization,
13:702–725, 2003.
43
Lee and Wright
A. S. Lewis and S. J. Wright. A proximal method for composite minimization. Technical
report, University of Wisconsin-Madison, August 2008.
Q. Lin, X. Chen, and J. Pen˜a. A sparsity preserving stochastic gradient method for compos-
ite optimization. Working paper, Tepper School of Business, Carnegie Mellon University,
March 2011.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation
approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609,
2009.
A. Nemirovski and D. Yudin. On cezari’s convergence of the steepest descent method for
approximating saddle point of convex-concave functions. Soviet Math. Dokl., 19, 1978.
A. Nemirovski and D. B. Yudin. Problem complexity and method efficiency in optimization.
John Wiley, 1983.
Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer
Academic Publishers, 2004.
Y. Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Pro-
gramming, 120:221–259, 2009.
B. T. Polyak. New stochastic approximation type procedures. Automat. i Telemekh., 7:
98–107, 1990.
B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging.
SIAM Journal on Control and Optimization, 30(4):838–855, 1992.
H. Robbins and S. Monro. A stochastic approximation method. Ann. Math. Statist., 22:
400–407, 1951.
J. Sacks. Asymptotic distribution of stochastic approximation procedures. The Annals of
Mathematical Statistics, 29(2):373–405, 1958.
S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos: Primal estimated sub-gradient
solver for svm. In Proceedings of the 24th International Conference on Machine Learning
(ICML), pages 807–814, 2007.
W. Shi, G. Wahba, S. J. Wright, K. Lee, R. Klein, and B. Klein. LASSO-Patternsearch
algorithm with application to opthalmology data. Statistics and its Interface, 1:137–153,
January 2008.
I. Vaisman. A First Course in Differential Geometry. Monographs and Textbooks in Pure
and Applied Mathematics. Marcel Dekker, 1984.
S. J. Wright. Identifiable surfaces in constrained optimization. SIAM Journal on Control
and Optimization, 31(4):1063–1079, 1993.
S. J. Wright. Accelerated block-coordinate relaxation for regularized optimization. Technical
report, University of Wisconsin-Madison, August 29 2010.
44
Manifold Identification for Regularized Stochastic Online Learning
S. J. Wright, R. D. Nowak, and M. A. T. Figueiredo. Sparse reconstruction by separable
approximation. IEEE Transactions on Signal Processing, 57:2479–2493, August 2009.
L. Xiao. Dual averaging methods for regularized stochastic learning and online optimization.
Journal of Machine Learning Research, 11:2543–2596, October 2010.
T. Zhang. Solving large scale linear prediction problems using stochastic gradient descent
algorithms. In Proceedings of the 21st International Conference on Machine Learning
(ICML), 2004.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent.
In Proceedings of the 20th International Conference on Machine Learning (ICML), pages
928–936, 2003.
45