Kaczmarz algorithm is an efficient iterative algorithm to solve overdetermined consistent system of linear equations. During each updating step, Kaczmarz chooses a hyperplane based on an individual equation and projects the current estimate for the exact solution onto that space to get a new estimate. Many vairants of Kaczmarz algorithms are proposed on how to choose better hyperplanes. Using the property of randomly sampled data in high-dimensional space, we propose an accelerated algorithm based on clustering information to improve block Kaczmarz and Kaczmarz via Johnson-Lindenstrauss lemma. Additionally, we theoretically demonstrate convergence improvement on block Kaczmarz algorithm.
The exact greedy idea has been highlighted in @cite_9 when they proposed RKA-JL algorithm. The idea is quite simple but reasonable. At the @math -th updating step, we can choose the hyperplane @math to project on where @math and update the estimate as Eq). But, after thinking of the practical issue, we may find that it is unaffordable to sweep through all rows of @math to pick the best one at each iteration. Thus, @cite_9 proposed a procedure to approximate the best hyperplane before performing each updating step, which is the key component of RKA-JL algorithm.
@cite_9
2036835849
This paper proves that an "old dog", namely -- the classical Johnson-Lindenstrauss transform, "performs new tricks" -- it gives a novel way of preserving differential privacy. We show that if we take two databases, @math and @math , such that (i) @math is a rank-1 matrix of bounded norm and (ii) all singular values of @math and @math are sufficiently large, then multiplying either @math or @math with a vector of iid normal Gaussians yields two statistically close distributions in the sense of differential privacy. Furthermore, a small, deterministic and alteration of the input is enough to assert that all singular values of @math are large. We apply the Johnson-Lindenstrauss transform to the task of approximating cut-queries: the number of edges crossing a @math -cut in a graph. We show that the JL transform allows us to that preserves edge differential privacy (where two graphs are neighbors if they differ on a single edge) while adding only @math random noise to any given query (w.h.p). Comparing the additive noise of our algorithm to existing algorithms for answering cut-queries in a differentially private manner, we outperform all others on small cuts ( @math ). We also apply our technique to the task of estimating the variance of a given matrix in any given direction. The JL transform allows us to that preserves differential privacy w.r.t bounded changes (each row in the matrix can change by at most a norm-1 vector) while adding random noise of magnitude independent of the size of the matrix (w.h.p). In contrast, existing algorithms introduce an error which depends on the matrix dimensions. Let @math be a graph with a threshold function @math such that @math for every vertex @math of @math , where @math is the degree of @math in @math . Suppose we are given a target set @math . This paper considers the following repetitive process on @math . At time step @math the vertices of @math are colored black and the other vertices are colored white. After that, at each time step @math , the colors of white vertices (if any) are updated according to the following rule. All white vertices @math that have at least @math black neighbors at the time step @math are colored black, and the colors of the other vertices do not change. The process runs until no more white vertices can update colors from white to black. The following optimization problem is called Target Set Selection: Find a target set @math of smallest possible size such that all vertices in @math are black at the end of the process. Such an @math is called an optimal target set for @math under the th... We study online regret minimization algorithms in an experts setting. In this setting, the algorithm chooses a distribution over experts at each time step and receives a gain that is a weighted average of the experts' instantaneous gains. We consider a bicriteria setting, examining not only the standard notion of regret to the best expert, but also the regret to the average of all experts, the regret to any given fixed mixture of experts, or the regret to the worst expert. This study leads both to new understanding of the limitations of existing no-regret algorithms, and to new algorithms with novel performance guarantees. More specifically, we show that any algorithm that achieves only @math cumulative regret to the best expert on a sequence of T trials must, in the worst case, suffer regret @math to the average, and that for a wide class of update rules that includes many existing no-regret algorithms (such as Exponential Weights and Follow the Perturbed Leader), the product of the regret to the best and the regret to the average is, in the worst case, ?(T). We then describe and analyze two alternate new algorithms that both achieve cumulative regret only @math to the best expert and have only constant regret to any given fixed distribution over experts (that is, with no dependence on either T or the number of experts N). The key to the first algorithm is the gradual increase in the "aggressiveness" of updates in response to observed divergences in expert performances. The second algorithm is a simple twist on standard exponential-update algorithms. Distributed training of @math regularized classifiers has received great attention recently. Most existing methods approach this problem by taking steps obtained from approximating the objective by a quadratic approximation that is decoupled at the individual variable level. These methods are designed for multicore and MPI platforms where communication costs are low. They are inefficient on systems such as Hadoop running on a cluster of commodity machines where communication costs are substantial. In this paper we design a distributed algorithm for @math regularization that is much better suited for such systems than existing algorithms. A careful cost analysis is used to support these points and motivate our method. The main idea of our algorithm is to do block optimization of many variables on the actual objective function within each computing node; this increases the computational cost per step that is matched with the communication cost, and decreases the number of outer iterations, thus yielding a faster overall method. Distributed Gauss-Seidel and Gauss-Southwell greedy schemes are used for choosing variables to update in each step. We establish global convergence theory for our algorithm, including Q-linear rate of convergence. Experiments on two benchmark problems show our method to be much faster than existing methods. We propose a novel stochastic gradient method---semi-stochastic coordinate descent (S2CD)---for the problem of minimizing a strongly convex function represented as the average of a large number of smooth convex functions: @math . Our method first performs a deterministic step (computation of the gradient of @math at the starting point), followed by a large number of stochastic steps. The process is repeated a few times, with the last stochastic iterate becoming the new starting point where the deterministic step is taken. The novelty of our method is in how the stochastic steps are performed. In each such step, we pick a random function @math and a random coordinate @math ---both using nonuniform distributions---and update a single coordinate of the decision vector only, based on the computation of the @math partial derivative of @math at two different points. Each random step of the method constitutes an unbiased estimate of the gradient of @math and moreover, the squared norm of the steps goes to zero in expectation, meaning that the stochastic estimate of the gradient progressively improves. The complexity of the method is the sum of two terms: @math evaluations of gradients @math and @math evaluations of partial derivatives @math , where @math is a novel condition number. We adapt a well known streaming algorithm for approximating item frequencies to the matrix sketching setting. The algorithm receives the rows of a large matrix @math one after the other in a streaming fashion. It maintains a sketch matrix @math such that for any unit vector @math [ |Ax |^2 |Bx |^2 |Ax |^2 - |A |_ f ^2 .] Sketch updates per row in @math require @math operations in the worst case. A slight modification of the algorithm allows for an amortized update time of @math operations per row. The presented algorithm stands out in that it is: deterministic, simple to implement, and elementary to prove. It also experimentally produces more accurate sketches than widely used approaches while still being computationally competitive. This paper analyzes circulant Johnson-Lindenstrauss (JL) embeddings which, as an important class of structured random JL embeddings, are formed by randomizing the column signs of a circulant matrix generated by a random vector. With the help of recent decoupling techniques and matrix-valued Bernstein inequalities, we obtain a new bound @math for Gaussian circulant JL embeddings. Moreover, by using the Laplace transform technique (also called Bernstein's trick), we extend the result to subgaussian case. The bounds in this paper offer a small improvement over the current best bounds for Gaussian circulant JL embeddings for certain parameter regimes and are derived using more direct methods. We present the best known algorithms for approximating the minimum-size undirected @math -edge connected spanning subgraph. For simple graphs our approximation ratio is @math . The more precise version of this bound requires @math , and for all such @math it improves the long-standing performance ratio of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528-560], @math . The improvement comes in two steps. First we show that for simple @math -edge connected graphs, any laminar family of degree @math sets is smaller than the general bound ( @math versus @math ). This immediately implies that iterated rounding improves the performance ratio of Cheriyan and Thurimella. The second step carefully chooses good edges for rounding. For multigraphs our approximation ratio is @math . This improves the previous ratio @math [H. N. Gabow, M. X. Goemans, E. Tardos, and D. P. Williamson, Networks, 53 (2009), pp. 345-357]. It is of interest since it is known that for some constant @math , an approximation ratio @math implies @math . Our approximation ratio extends to the minimum-size Steiner network problem, where @math denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding. We present improved combinatorial approximation algorithms for the uncapacitated facility location problem. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which achieves an approximation ratio of @math in @math time. This also yields a bicriteria approximation tradeoff of @math for facility cost versus service cost which is better than previously known tradeoffs and close to the best possible. Combining greedy improvement and cost scaling with a recent primal-dual algorithm for facility location due to Jain and Vazirani, we get an approximation ratio of @math in @math time. This is very close to the approximation guarantee of the best known algorithm which is linear programming (LP)-based. Further, combined with the best known LP-based algorithm for facility location, we get a very slight improvement in the approximation factor for facility location, achieving @math . We also consider a variant of the capacitated facility location problem and present improved approximation algorithms for this. Many conjugate gradient-like methods for solving linear systems @math use recursion formulas for updating residual vectors instead of computing the residuals directly. For such methods it is shown that the difference between the actual residuals and the updated approximate residual vectors generated in finite precision arithmetic depends on the machine precision @math and on the maximum norm of an iterate divided by the norm of the true solution. It is often observed numerically, and can sometimes be proved, that the norms of the updated approximate residual vectors converge to zero or, at least, become orders of magnitude smaller than the machine precision. In such cases, the actual residual norm reaches the level @math times the maximum ratio of the norm of an iterate to that of the true solution. Using exact arithmetic theory to bound the size of the iterates, we give a priori estimates of the size of the final residual for a number of algorithms. We present an algorithm for computing @math , the @math th moment of an @math -dimensional frequency vector of a data stream, for @math , to within @math factors, @math with high constant probability. Let @math be the number of stream records and @math be the largest magnitude of a stream update. The algorithm uses space in bits @math where, @math . Here @math is @math for @math and @math for @math . This improves upon the space required by current algorithms iw:stoc05,bgks:soda06,ako:arxiv10,bo:arxiv10 by a factor of at least @math . The update time is @math . We use a new technique for designing estimators for functions of the form @math , where, @math is a random variable and @math is a smooth function, based on a low-degree Taylor polynomial expansion of @math around an estimate of @math . We introduce a new approach to isolate the real roots of a square-free polynomial @math with real coefficients. It is assumed that each coefficient of @math can be approximated to any specified error bound. The presented method is exact, complete and deterministic. Due to its similarities to the Descartes method, we also consider it practical and easy to implement. Compared to previous approaches, our new method achieves a significantly better bit complexity. It is further shown that the hardness of isolating the real roots of @math is exclusively determined by the geometry of the roots and not by the complexity or the size of the coefficients. For the special case where @math has integer coefficients of maximal bitsize @math , our bound on the bit complexity writes as @math which improves the best bounds known for existing practical algorithms by a factor of @math . The crucial idea underlying the new approach is to run an approximate version of the Descartes method, where, in each subdivision step, we only consider approximations of the intermediate results to a certain precision. We give an upper bound on the maximal precision that is needed for isolating the roots of @math . For integer polynomials, this bound is by a factor @math lower than that of the precision needed when using exact arithmetic explaining the improved bound on the bit complexity. We prove an incidence theorem for points and planes in the projective space @math over any field @math , whose characteristic @math An incidence is viewed as an intersection along a line of a pair of two-planes from two canonical rulings of the Klein quadric. The Klein quadric can be traversed by a generic hyperplane, yielding a line-line incidence problem in a three-quadric, the Klein image of a regular line complex. This hyperplane can be chosen so that at most two lines meet. Hence, one can apply an algebraic theorem of Guth and Katz, with a constraint involving @math if @math . This yields a bound on the number of incidences between @math points and @math planes in @math , with @math as @math where @math is the maximum number of collinear planes, provided that @math if @math . Examples show that this bound cannot be improved without additional assumptions. This gives one a vehicle to establish geometric incidence estimates when @math . For a non-collinear point set @math and a non-degenerate symmetric or skew-symmetric bilinear form @math , the number of distinct values of @math on pairs of points of @math is @math . This is also the best known bound over @math , where it follows from the Szemer 'edi-Trotter theorem. Also, a set @math , not supported in a single semi-isotropic plane contains a point, from which @math distinct distances to other points of @math are attained. In a combinatorial auction with item bidding, agents participate in multiple single-item second-price auctions at once. As some items might be substitutes, agents need to strategize in order to maximize their utilities. A number of results indicate that high welfare can be achieved this way, giving bounds on the welfare at equilibrium. Recently, however, criticism has been raised that equilibria are hard to compute and therefore unlikely to be attained. In this paper, we take a different perspective. We study simple best-response dynamics. That is, agents are activated one after the other and each activated agent updates his strategy myopically to a best response against the other agents' current strategies. Often these dynamics may take exponentially long before they converge or they may not converge at all. However, as we show, convergence is not even necessary for good welfare guarantees. Given that agents' bid updates are aggressive enough but not too aggressive, the game will remain in states of good welfare after each agent has updated his bid at least once. In more detail, we show that if agents have fractionally subadditive valuations, natural dynamics reach and remain in a state that provides a @math approximation to the optimal welfare after each agent has updated his bid at least once. For subadditive valuations, we can guarantee an @math approximation in case of @math items that applies after each agent has updated his bid at least once and at any point after that. The latter bound is complemented by a negative result, showing that no kind of best-response dynamics can guarantee more than an @math fraction of the optimal social welfare. We present and analyze an efficient new algorithm for generating a random variate distributed according to a dynamically changing set of weights. The algorithm can generate the random variate and update a weight each in @math expected time. (For all feasible values of @math , @math is at most 5.) The @math expected update time is amortized; in the worst-case the expected update time is @math . The algorithm is simple, practical, and easy to implement. Given a matrix A e ℝ m ×n of rank r, and an integer k < r, the top k singular vectors provide the best rank-k approximation to A. When the columns of A have specific meaning, it is desirable to find (provably) "good" approximations to A k which use only a small number of columns in A. Proposed solutions to this problem have thus far focused on randomized algorithms. Our main result is a simple greedy deterministic algorithm with guarantees on the performance and the number of columns chosen. Specifically, our greedy algorithm chooses c columns from A with @math such that @math where C gr is the matrix composed of the c columns, @math is the pseudo-inverse of C gr ( @math is the best reconstruction of A from C gr), and ¼(A) is a measure of the coherence in the normalized columns of A. The running time of the algorithm is O(SVD(A k) + mnc) where SVD(A k) is the running time complexity of computing the first k singular vectors of A. To the best of our knowledge, this is the first deterministic algorithm with performance guarantees on the number of columns and a (1 + e) approximation ratio in Frobenius norm. The algorithm is quite simple and intuitive and is obtained by combining a generalization of the well known sparse approximation problem from information theory with an existence result on the possibility of sparse approximation. Tightening the analysis along either of these two dimensions would yield improved results. We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any @math , given cost and demand graphs with edge weights @math respectively, we can find a set @math with @math at most @math times the optimal non-uniform sparsest cut value, in time @math provided @math . Here @math is the @math 'th smallest generalized eigenvalue of the Laplacian matrices of cost and demand graphs; @math (resp. @math ) is the weight of edges crossing the @math cut in cost (resp. demand) graph and @math is the sparsity of the optimal cut. In words, we show that the non-uniform sparsest cut problem is easy when the generalized spectrum grows moderately fast. To the best of our knowledge, there were no results based on higher order spectra for non-uniform sparsest cut prior to this work. Even for uniform sparsest cut, the quantitative aspects of our result are somewhat stronger than previous methods. Similar results hold for other expansion measures like edge expansion, normalized cut, and conductance, with the @math 'th smallest eigenvalue of the normalized Laplacian playing the role of @math in the latter two cases. Our proof is based on an l1-embedding of vectors from a semi-definite program from the Lasserre hierarchy. The embedded vectors are then rounded to a cut using standard threshold rounding. We hope that the ideas connecting @math -embeddings to Lasserre SDPs will find other applications. Another aspect of the analysis is the adaptation of the column selection paradigm from our earlier work on rounding Lasserre SDPs [GS11] to pick a set of edges rather than vertices. This feature is important in order to extend the algorithms to non-uniform sparsest cut. We give efficient algorithms for volume sampling, i.e., for picking @math -subsets of the rows of any given matrix with probabilities proportional to the squared volumes of the simplices defined by them and the origin (or the squared volumes of the parallelepipeds defined by these subsets of rows). In other words, we can efficiently sample @math -subsets of @math with probabilities proportional to the corresponding @math by @math principal minors of any given @math by @math positive semi definite matrix. This solves an open problem from the monograph on spectral algorithms by Kannan and Vempala (see Section @math of KV , also implicit in BDM, DRVW ). Our first algorithm for volume sampling @math -subsets of rows from an @math -by- @math matrix runs in @math arithmetic operations (where @math is the exponent of matrix multiplication) and a second variant of it for @math -approximate volume sampling runs in @math arithmetic operations, which is almost linear in the size of the input (i.e., the number of entries) for small @math . Our efficient volume sampling algorithms imply the following results for low-rank matrix approximation: (1) Given @math , in @math arithmetic operations we can find @math of its rows such that projecting onto their span gives a @math -approximation to the matrix of rank @math closest to @math under the Frobenius norm. This improves the @math -approximation of Boutsidis, Drineas and Mahoney BDM and matches the lower bound shown in DRVW . The method of conditional expectations gives a algorithm with the same complexity. The running time can be improved to @math at the cost of losing an extra @math in the approximation factor. (2) The same rows and projection as in the previous point give a @math -approximation to the matrix of rank @math closest to @math under the spectral norm. In this paper, we show an almost matching lower bound of @math , even for @math . Motivated by applications in blockchains and sensor networks, we consider a model of @math nodes trying to reach consensus on their majority bit. Each node @math is assigned a bit at time zero, and is a finite automaton with @math bits of memory (i.e., @math states) and a Poisson clock. When the clock of @math rings, @math can choose to communicate, and is then matched to a uniformly chosen node @math . The nodes @math and @math may update their states based on the state of the other node. Previous work has focused on minimizing the time to consensus and the probability of error, while our goal is minimizing the number of communications. We show that when @math , consensus can be reached at linear communication cost, but this is impossible if @math . We also study a synchronous variant of the model, where our upper and lower bounds on @math for achieving linear communication cost are @math and @math , respectively. A key step is to distinguish when nodes can become aware of knowing the majority bit and stop communicating. We show that this is impossible if their memory is too low. One of the key steps at each iteration of a randomized block coordinate descent method consists in determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is solved exactly. In this work, we relax this requirement and allow for the subproblem to be solved inexactly, leading to an inexact block coordinate descent method. Our approach incorporates the best known results for exact updates as a special case. Moreover, these theoretical guarantees are complemented by practical considerations: the use of iterative techniques to determine the update and the use of preconditioning for further acceleration.