Quantiles, such as the median or percentiles, provide concise and useful information about the distribution of a collection of items, drawn from a linearly ordered universe. We study data structures, called quantile summaries, which keep track of all quantiles, up to an error of at most @math . That is, an @math -approximate quantile summary first processes a stream of items and then, given any quantile query @math , returns an item from the stream, which is a @math -quantile for some @math . We focus on comparison-based quantile summaries that can only compare two items and are otherwise completely oblivious of the universe. The best such deterministic quantile summary to date, by Greenwald and Khanna (ACM SIGMOD '01), stores at most @math items, where @math is the number of items in the stream. We prove that this space bound is optimal by providing a matching lower bound. Our result thus rules out the possibility of constructing a deterministic comparison-based quantile summary in space @math , for any function @math that does not depend on @math . A consequence of our results is also to show a lower bound for randomized algorithms.
If we tolerate randomization and relax the requirement for worst-case error guarantees, it is possible to design quantile summaries with space close to @math . After a sequence of improvements @cite_0 @cite_3 @cite_4 @cite_10 , Karnin, Lang, and Liberty @cite_14 designed a randomized comparison-based quantile summary with space bounded by @math , where @math is the probability of not returning an @math -approximate @math -quantile for some @math . The algorithm combines careful sampling, and uses the Greenwald-Khanna summary as a subroutine. They also provide a reduction to transform the deterministic @math lower bound into a randomized lower bound of @math , implying optimality of their approach in its model. We discuss further how the deterministic and randomized lower bounds relate in .
@cite_14 @cite_4 @cite_3 @cite_0 @cite_10
2963274201 2279830512 2950958145 2114944618 2950981509 2508919161 179407972 2067202579 2950256099 2547508527 2139964991 2952056844 2078764670 2951290586 2007104311 2123372478 1521197246 2036804629 2000931246 2950132609
This paper resolves one of the longest standing basic problems in the streaming computational model. Namely, optimal construction of quantile sketches. An e approximate quantile sketch receives a stream of items x1,·,xn and allows one to approximate the rank of any query item up to additive error e n with probability at least 1-δ.The rank of a query x is the number of stream items such that xi ≤ x. The minimal sketch size required for this task is trivially at least 1 e.Felber and Ostrovsky obtain a O((1 e)log(1 e)) space sketch for a fixed δ.Without restrictions on the nature of the stream or the ratio between e and n, no better upper or lower bounds were known to date. This paper obtains an O((1 e)log log (1 δ)) space sketch and a matching lower bound. This resolves the open problem and proves a qualitative gap between randomized and deterministic quantile sketching for which an Ω((1 e)log(1 e)) lower bound is known. One of our contributions is a novel representation and modification of the widely used merge-and-reduce construction. This modification allows for an analysis which is both tight and extremely simple. The same technique was reported, in private communications, to be useful for improving other sketching objectives and geometric coreset constructions. Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish connections between the deterministic and randomized complexities in the LOCAL model. Each result has a very compelling take-away message: 1. Fast @math -coloring of trees requires random bits: Building on the recent lower bounds of , we prove that the randomized complexity of @math -coloring a tree with maximum degree @math is @math , whereas its deterministic complexity is @math for any @math . This also establishes a large separation between the deterministic complexity of @math -coloring and @math -coloring trees. 2. Randomized lower bounds imply deterministic lower bounds: We prove that any deterministic algorithm for a natural class of problems that runs in @math rounds can be transformed to run in @math rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires @math time deterministically. 3. Deterministic lower bounds imply randomized lower bounds: We prove that the randomized complexity of any natural problem on instances of size @math is at least its deterministic complexity on instances of size @math . This shows that a deterministic @math lower bound for any problem implies a randomized @math lower bound. It also illustrates that the graph shattering technique is absolutely essential to the LOCAL model. We consider the problem of selecting the best subset of exactly @math columns from an @math matrix @math . We present and analyze a novel two-stage algorithm that runs in @math time and returns as output an @math matrix @math consisting of exactly @math columns of @math . In the first (randomized) stage, the algorithm randomly selects @math columns according to a judiciously-chosen probability distribution that depends on information in the top- @math right singular subspace of @math . In the second (deterministic) stage, the algorithm applies a deterministic column-selection procedure to select and return exactly @math columns from the set of columns selected in the first stage. Let @math be the @math matrix containing those @math columns, let @math denote the projection matrix onto the span of those columns, and let @math denote the best rank- @math approximation to the matrix @math . Then, we prove that, with probability at least 0.8, @math This Frobenius norm bound is only a factor of @math worse than the best previously existing existential result and is roughly @math better than the best previous algorithmic result for the Frobenius norm version of this Column Subset Selection Problem (CSSP). We also prove that, with probability at least 0.8, @math This spectral norm bound is not directly comparable to the best previously existing bounds for the spectral norm version of this CSSP. Our bound depends on @math , whereas previous results depend on @math ; if these two quantities are comparable, then our bound is asymptotically worse by a @math factor. In a recent paper [MRL98], we had described a general framework for single pass approximate quantile finding algorithms. This framework included several known algorithms as special cases. We had identified a new algorithm, within the framework, which had a significantly smaller requirement for main memory than other known algorithms. In this paper, we address two issues left open in our earlier paper. First, all known and space efficient algorithms for approximate quantile finding require advance knowledge of the length of the input sequence. Many important database applications employing quantiles cannot provide this information. In this paper, we present a novel non-uniform random sampling scheme and an extension of our framework. Together, they form the basis of a new algorithm which computes approximate quantiles without knowing the input sequence length. Second, if the desired quantile is an extreme value (e.g., within the top 1 of the elements), the space requirements of currently known algorithms are overly pessimistic. We provide a simple algorithm which estimates extreme values using less space than required by the earlier more general technique for computing all quantiles. Our principal observation here is that random sampling is quantifiably better when estimating extreme values than is the case with the median. Let @math be a tree space (or tree network) represented by a weighted tree with @math vertices, and @math be a set of @math stochastic points in @math , each of which has a fixed location with an independent existence probability. We investigate two fundamental problems under such a stochastic setting, the closest-pair problem and the nearest-neighbor search. For the former, we study the computation of the @math -threshold probability and the expectation of the closest-pair distance of a realization of @math . We propose the first algorithm to compute the @math -threshold probability in @math time for any given threshold @math , which immediately results in an @math -time algorithm for computing the expected closest-pair distance. Based on this, we further show that one can compute a @math -approximation for the expected closest-pair distance in @math time, by arguing that the expected closest-pair distance can be approximated via @math threshold probability queries. For the latter, we study the @math most-likely nearest-neighbor search ( @math -LNN) via a notion called @math most-likely Voronoi Diagram ( @math -LVD). We show that the size of the @math -LVD @math of @math on @math is bounded by @math if the existence probabilities of the points in @math are constant-far from 0. Furthermore, we establish an @math average-case upper bound for the size of @math , by regarding the existence probabilities as i.i.d. random variables drawn from some fixed distribution. Our results imply the existence of an LVD data structure which answers @math -LNN queries in @math time using average-case @math space, and worst-case @math space if the existence probabilities are constant-far from 0. Finally, we also give an @math -time algorithm to construct the LVD data structure. [See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the @math -Approximate Near Neighbor Search problem. For the @math -dimensional Euclidean space and @math -point datasets, we develop a data structure with space @math and query time @math for every @math such that: This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor @math , improving upon [Kapralov, PODS 2015]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [Becker, Ducas, Gama, Laarhoven, SODA 2016] and data-dependent hashing [Andoni, Indyk, Nguyen, Razenshteyn, SODA 2014] [Andoni, Razenshteyn, STOC 2015]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole above trade-off in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match the above trade-off for @math , improving upon the best known lower bounds from [Panigrahy, Talwar, Wieder, FOCS 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes. We report on a novel technique called spatial coupling and its application in the analysis of random constraint satisfaction problems (CSP). Spatial coupling was invented as an engineering construction in the area of error correcting codes where it has resulted in efficient capacity-achieving codes for a wide range of channels. However, this technique is not limited to problems in communications, and can be applied in the much broader context of graphical models. We describe here a general methodology for applying spatial coupling to random constraint satisfaction problems and obtain lower bounds for their (rough) satisfiability threshold. The main idea is to construct a distribution of geometrically structured random K-SAT instances - namely the spatially coupled ensemble - which has the same (rough) satisfiability threshold, and is at the same time algorithmically easier to solve. Then by running well-known algorithms on the spatially coupled ensemble we obtain a lower bound on the (rough) satisfiability threshold of the original ensemble. The method is versatile because one can choose the CSP, there is a certain amount of freedom in the construction of the spatially coupled ensemble, and also in the choice of the algorithm. In this work we focus on random K-SAT but we have also checked that the method is successful for Coloring, NAE-SAT and XOR-SAT. We choose Unit Clause propagation for the algorithm which is analyzed over the spatially coupled instances. For K = 3, for instance, our lower bound is equal to 3.67 which is better than the current bounds in the literature. Similarly, for graph 3-colorability we get a bound of 2.22 which is also better than the current bounds in the literature. A central theme in distributed network algorithms concerns understanding and coping with the issue of locality . Despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for . In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. We consider the standard @math model of computation and define @math (for local decision ) as the class of decision problems that can be solved in @math communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class @math , containing all languages for which there exists a randomized algorithm that runs in @math rounds, accepts correct instances with probability at least @math and rejects incorrect ones with probability at least @math . We show that @math is a threshold for the containment of @math in @math . More precisely, we show that there exists a language that does not belong to @math for any @math but does belong to @math for any @math such that @math . On the other hand, we show that, restricted to hereditary languages, @math , for any function @math and any @math such that @math . In addition, we investigate the impact of non-determinism on local decision, and establish some structural results inspired by classical computational complexity theory. Specifically, we show that non-determinism does help, but that this help is limited, as there exist languages that cannot be decided non-deterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with non-determinism that enables to decide languages . Finally, we introduce the notion of local reduction, and establish some completeness results. We consider the unweighted bipartite maximum matching problem in the one-pass turnstile streaming model where the input stream consists of edge insertions and deletions. In the insertion-only model, a one-pass @math -approximation streaming algorithm can be easily obtained with space @math , where @math denotes the number of vertices of the input graph. We show that no such result is possible if edge deletions are allowed, even if space @math is granted, for every @math . Specifically, for every @math , we show that in the one-pass turnstile streaming model, in order to compute a @math -approximation, space @math is required for constant error randomized algorithms, and, up to logarithmic factors, space @math is sufficient. Our lower bound result is proved in the simultaneous message model of communication and may be of independent interest. We present an algorithm for the statistical learning setting with a bounded exp-concave loss in @math dimensions that obtains excess risk @math with probability at least @math . The core technique is to boost the confidence of recent in-expectation @math excess risk bounds for empirical risk minimization (ERM), without sacrificing the rate, by leveraging a Bernstein condition which holds due to exp-concavity. We also show that with probability @math the standard ERM method obtains excess risk @math . We further show that a regret bound for any online learner in this setting translates to a high probability excess risk bound for the corresponding online-to-batch conversion of the online learner. Lastly, we present two high probability bounds for the exp-concave model selection aggregation problem that are quantile-adaptive in a certain sense. The first bound is a purely exponential weights type algorithm, obtains a nearly optimal rate, and has no explicit dependence on the Lipschitz continuity of the loss. The second bound requires Lipschitz continuity but obtains the optimal rate. We consider a finite random walk on a weighted graph G; we show that the fraction of time spent in a set of vertices A converges to the stationary probability @math with error probability exponentially small in the length of the random walk and the square of the size of the deviation from @math . The exponential bound is in terms of the expansion of G and improves previous results of [D. Aldous, Probab. Engrg. Inform. Sci., 1 (1987), pp. 33--46], [L. Lovasz and M. Simonovits, Random Structures Algorithms , 4 (1993), pp. 359--412], [M. Ajtai, J. Komlos, and E. Szemeredi, Deterministic simulation of logspace, in Proc. 19th ACM Symp. on Theory of Computing, 1987]. We show that taking the sample average from one trajectory gives a more efficient estimate of @math than the standard method of generating independent sample points from several trajectories. Using this more efficient sampling method, we improve the algorithms of Jerrum and Sinclair for approximating the number of perfect matchings in a dense graph and for approximating the partition function of a ferromagnetic Ising system, and we give an efficient algorithm to estimate the entropy of a random walk on an unweighted graph. We derive new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistics, that are simple to calculate for sorted data. We develop a randomized algorithm for the element distinctness problem whose time T and space S satisfy T in O (n^ 3 2 S^ 1 2 ), smaller than previous lower bounds for comparison-based algorithms, showing that element distinctness is strictly easier than sorting for randomized branching programs. This algorithm is based on a new time and space efficient algorithm for finding all collisions of a function f from a finite set to itself that are reachable by iterating f from a given set of starting points. We further show that our element distinctness algorithm can be extended at only a polylogarithmic factor cost to solve the element distinctness problem over sliding windows, where the task is to take an input of length 2n-1 and produce an output for each window of length n, giving n outputs in total. In contrast, we show a time-space tradeoff lower bound of T in Omega(n^2 S) for randomized branching programs to compute the number of distinct elements over sliding windows. The same lower bound holds for computing the low-order bit of F_0 and computing any frequency moment F_k, k neq 1. This shows that those frequency moments and the decision problem F_0 mod 2 are strictly harder than element distinctness. We complement this lower bound with a T in O(n^2 S) comparison-based deterministic RAM algorithm for exactly computing F_k over sliding windows, nearly matching both our lower bound for the sliding-window version and the comparison-based lower bounds for the single-window version. We further exhibit a quantum algorithm for F_0 over sliding windows with T in O(n^ 3 2 S^ 1 2 ). Finally, we consider the computations of order statistics over sliding windows. In most algorithmic applications which compare two distributions, information theoretic distances are more natural than standard l p norms. In this paper we design streaming and sublinear time property testing algorithms for entropy and various information theoretic distances. posed the problem of property testing with respect to the Jensen-Shannon distance. We present optimal algorithms for estimating bounded, symmetric f-divergences (including the Jensen-Shannon divergence and the Hellinger distance) between distributions in various property testing frameworks. Along the way, we close a (log n) H gap between the upper and lower bounds for estimating entropy H, yielding an optimal algorithm over all values of the entropy. In a data stream setting (sublinear space), we give the first algorithm for estimating the entropy of a distribution. Our algorithm runs in polylogarithmic space and yields an asymptotic constant factor approximation scheme. An integral part of the algorithm is an interesting use of an F 0 (the number of distinct elements in a set) estimation algorithm; we also provide other results along the space time approximation tradeoff curve.Our results have interesting structural implications that connect sublinear time and space constrained algorithms. The mediating model is the random order streaming model, which assumes the input is a random permutation of a multiset and was first considered by Munro and Paterson in 1980. We show that any property testing algorithm in the combined oracle model for calculating a permutation invariant functions can be simulated in the random order model in a single pass. This addresses a question raised by regarding the relationship between property testing and stream algorithms. Further, we give a polylog-space PTAS for estimating the entropy of a one pass random order stream. This bound cannot be achieved in the combined oracle (generalized property testing) model. The paper tackles the power of randomization in the context of locality by analyzing the ability to boost' the success probability of deciding a distributed language. The main outcome of this analysis is that the distributed computing setting contrasts significantly with the sequential one as far as randomization is concerned. Indeed, we prove that in some cases, the ability to increase the success probability for deciding distributed languages is rather limited. Informally, a (p,q)-decider for a language L is a distributed randomized algorithm which accepts instances in L with probability at least p and rejects instances outside of L with probability at least q. It is known that every hereditary language that can be decided in t rounds by a (p,q)-decider, where p^2+q>1, can actually be decided deterministically in O(t) rounds. In one of our results we give evidence supporting the conjecture that the above statement holds for all distributed languages. This is achieved by considering the restricted case of path topologies. We then turn our attention to the range below the aforementioned threshold, namely, the case where p^2+q . We define B_k(t) to be the set of all languages decidable in at most t rounds by a (p,q)-decider, where p^ 1+1 k +q>1. It is easy to see that every language is decidable (in zero rounds) by a (p,q)-decider satisfying p+q=1. Hence, the hierarchy B_k provides a spectrum of complexity classes between determinism and complete randomization. We prove that all these classes are separated: for every integer k 1, there exists a language L satisfying L B_ k+1 (0) but L B_k(t) for any t=o(n). In addition, we show that B_ (t) does not contain all languages, for any t=o(n). Finally, we show that if the inputs can be restricted in certain ways, then the ability to boost the success probability becomes almost null. In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson J. Comput. System Sci., 68 (2004), pp. 442-470]. We first develop a closed-form formula to compute the probability of a complex-valued normally distributed bivariate random vector to be in a given angular region. This formula allows us to compute the expected value of a randomized (with a specific rounding rule) solution based on the optimal solution of the complex semidefinite programming relaxation problem. In particular, we present an @math -approximation algorithm, and then study the limit of that model, in which the problem remains NP-hard. We show that if the objective is to maximize a positive semidefinite Hermitian form, then the randomization-rounding procedure guarantees a worst-case performance ratio of @math , which is better than the ratio of @math for its counterpart in the real case due to Nesterov. Furthermore, if the objective matrix is real-valued positive semidefinite with nonpositive off-diagonal elements, then the performance ratio improves to 0.9349. Hoeffding's U-statistics model combinatorial-type matrix parameters (appearing in CS theory) in a natural way. This paper proposes using these statistics for analyzing random compressed sensing matrices, in the non-asymptotic regime (relevant to practice). The aim is to address certain pessimisms of worst-case restricted isometry analyses, as observed by both Blanchard and Dossal, We show how U-statistics can obtain average-case analyses, by relating to statistical restricted isometry property (StRIP) type recovery guarantees. However unlike standard StRIP, random signal models are not required; the analysis used here holds in the almost sure (probabilistic) sense. For Gaussian bounded entry matrices, we show that both @math -minimization and LASSO essentially require on the order of @math measurements to respectively recover at least @math fraction, and @math fraction, of the signals. Noisy conditions are considered. Empirical evidence suggests our analysis to compare well to Donoho and Tanner's recent large deviation bounds for @math -equivalence, in the regime of block lengths @math with high undersampling ( @math measurements); similar system sizes are found in recent CS implementation. In this work, it is assumed throughout that matrix columns are independently sampled. We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order- @math tensor @math of the form @math , where @math is a signal-to-noise ratio, @math is a unit vector, and @math is a random noise tensor, the goal is to recover the planted vector @math . For the case that @math has iid standard Gaussian entries, we give an efficient algorithm to recover @math whenever @math , and certify that the recovered vector is close to a maximum likelihood estimator, all with high probability over the random choice of @math . The previous best algorithms with provable guarantees required @math . In the regime @math , natural tensor-unfolding-based spectral relaxations for the underlying optimization problem break down (in the sense that their integrality gap is large). To go beyond this barrier, we use convex relaxations based on the sum-of-squares method. Our recovery algorithm proceeds by rounding a degree- @math sum-of-squares relaxations of the maximum-likelihood-estimation problem for the statistical model. To complement our algorithmic results, we show that degree- @math sum-of-squares relaxations break down for @math , which demonstrates that improving our current guarantees (by more than logarithmic factors) would require new techniques or might even be intractable. Finally, we show how to exploit additional problem structure in order to solve our sum-of-squares relaxations, up to some approximation, very efficiently. Our fastest algorithm runs in nearly-linear time using shifted (matrix) power iteration and has similar guarantees as above. The analysis of this algorithm also confirms a variant of a conjecture of Montanari and Richard about singular vectors of tensor unfoldings. When faced with a complex task, is it better to be systematic or to proceed by making random adjustments? We study aspects of this problem in the context of generating random elements of a finite group. For example, suppose we want to fill n empty spaces with zeros and ones such that the probability of configuration x = (x1, . . . , xn) is θ n−|x|(1− θ)|x|, with |x| the number of ones in x. A systematic scan approach works left to right, filling each successive place with a θ coin toss. A random scan approach picks places at random, and a given site may be hit many times before all sites are hit. The systematic approach takes order n steps and the random approach takes order 1 4n log n steps. Realistic versions of this toy problem arise in image analysis and Ising-like simulations, where one must generate a random array by a Monte Carlo Markov chain. Systematic updating and random updating are competing algorithms that are discussed in detail in Section 2. There are some successful analyses for random scan algorithms, but the intuitively appealing systematic scan algorithms have resisted analysis. Our main results show that the binary problem just described is exceptional; for the examples analyzed in this paper, systematic and random scans converge in about the same number of steps. Let W be a finite Coxeter group generated by simple reflections s1, s2, . . . , sn, where s2 i = id. For example, W may be the permutation group Sn+1 with si = (i, i + 1). The length function (w) is the smallest k such that w = si1si2 · · · sik . Fix 0 < θ ≤ 1 and define a probability distribution on W by π(w) = θ − (w) PW (θ−1) , where PW(θ −1) = ∑ Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253 We obtain an improved finite-sample guarantee on the linear convergence of stochastic gradient descent for smooth and strongly convex objectives, improving from a quadratic dependence on the conditioning @math (where @math is a bound on the smoothness and @math on the strong convexity) to a linear dependence on @math . Furthermore, we show how reweighting the sampling distribution (i.e. importance sampling) is necessary in order to further improve convergence, and obtain a linear dependence in the average smoothness, dominating previous results. We also discuss importance sampling for SGD more broadly and show how it can improve convergence also in other scenarios. Our results are based on a connection we make between SGD and the randomized Kaczmarz algorithm, which allows us to transfer ideas between the separate bodies of literature studying each of the two methods. In particular, we recast the randomized Kaczmarz algorithm as an instance of SGD, and apply our results to prove its exponential convergence, but to the solution of a weighted least squares problem rather than the original least squares problem. We then present a modified Kaczmarz algorithm with partially biased sampling which does converge to the original least squares solution with the same exponential convergence rate.