Relevant bibliographies by topics / Sparsification

Academic literature on the topic 'Sparsification'

Author: Grafiati
Published: 4 June 2021
Last updated: 25 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Sparsification.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Sparsification"

1

Chen, Yuhan, Haojie Ye, Sanketh Vedula, Alex Bronstein, Ronald Dreslinski, Trevor Mudge, and Nishil Talati. "Demystifying Graph Sparsification Algorithms in Graph Properties Preservation." Proceedings of the VLDB Endowment 17, no. 3 (November 2023): 427–40. http://dx.doi.org/10.14778/3632093.3632106.

Full text
Abstract:
Graph sparsification is a technique that approximates a given graph by a sparse graph with a subset of vertices and/or edges. The goal of an effective sparsification algorithm is to maintain specific graph properties relevant to the downstream task while minimizing the graph's size. Graph algorithms often suffer from long execution time due to the irregularity and the large real-world graph size. Graph sparsification can be applied to greatly reduce the run time of graph algorithms by substituting the full graph with a much smaller sparsified graph, without significantly degrading the output quality. However, the interaction between numerous sparsifiers and graph properties is not widely explored, and the potential of graph sparsification is not fully understood. In this work, we cover 16 widely-used graph metrics, 12 representative graph sparsification algorithms, and 14 real-world input graphs spanning various categories, exhibiting diverse characteristics, sizes, and densities. We developed a framework to extensively assess the performance of these sparsification algorithms against graph metrics, and provide insights to the results. Our study shows that there is no one sparsifier that performs the best in preserving all graph properties, e.g. sparsifiers that preserve distance-related graph properties (eccentricity) struggle to perform well on Graph Neural Networks (GNN). This paper presents a comprehensive experimental study evaluating the performance of sparsification algorithms in preserving essential graph metrics. The insights inform future research in incorporating matching graph sparsification to graph algorithms to maximize benefits while minimizing quality degradation. Furthermore, we provide a framework to facilitate the future evaluation of evolving sparsification algorithms, graph metrics, and ever-growing graph data.
APA, Harvard, Vancouver, ISO, and other styles
2

Parchas, Panos, Nikolaos Papailiou, Dimitris Papadias, and Francesco Bonchi. "Uncertain Graph Sparsification." IEEE Transactions on Knowledge and Data Engineering 30, no. 12 (December 1, 2018): 2435–49. http://dx.doi.org/10.1109/tkde.2018.2819651.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Li, Tao, Wencong Jiao, Li-Na Wang, and Guoqiang Zhong. "Automatic DenseNet Sparsification." IEEE Access 8 (2020): 62561–71. http://dx.doi.org/10.1109/access.2020.2984130.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Eppstein, David, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. "Separator Based Sparsification." Journal of Computer and System Sciences 52, no. 1 (February 1996): 3–27. http://dx.doi.org/10.1006/jcss.1996.0002.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Lobacheva, Ekaterina, Nadezhda Chirkova, Alexander Markovich, and Dmitry Vetrov. "Structured Sparsification of Gated Recurrent Neural Networks." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 4989–96. http://dx.doi.org/10.1609/aaai.v34i04.5938.

Full text
Abstract:
One of the most popular approaches for neural network compression is sparsification — learning sparse weight matrices. In structured sparsification, weights are set to zero by groups corresponding to structure units, e. g. neurons. We further develop the structured sparsification approach for the gated recurrent neural networks, e. g. Long Short-Term Memory (LSTM). Specifically, in addition to the sparsification of individual weights and neurons, we propose sparsifying the preactivations of gates. This makes some gates constant and simplifies an LSTM structure. We test our approach on the text classification and language modeling tasks. Our method improves the neuron-wise compression of the model in most of the tasks. We also observe that the resulting structure of gate sparsity depends on the task and connect the learned structures to the specifics of the particular tasks.
APA, Harvard, Vancouver, ISO, and other styles
6

Farina, Gabriele, and Tuomas Sandholm. "Fast Payoff Matrix Sparsification Techniques for Structured Extensive-Form Games." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 5 (June 28, 2022): 4999–5007. http://dx.doi.org/10.1609/aaai.v36i5.20431.

Full text
Abstract:
The practical scalability of many optimization algorithms for large extensive-form games is often limited by the games' huge payoff matrices. To ameliorate the issue, Zhang and Sandholm recently proposed a sparsification technique that factorizes the payoff matrix A into a sparser object A = Â + UVᵀ, where the total combined number of nonzeros of Â, U, and V, is significantly smaller. Such a factorization can be used in place of the original payoff matrix in many optimization algorithm, such as interior-point and second-order methods, thus increasing the size of games that can be handled. Their technique significantly sparsifies poker (end)games, standard benchmarks used in computational game theory, AI, and more broadly. We show that the existence of extremely sparse factorizations in poker games can be tied to their particular Kronecker-product structure. We clarify how such structure arises and introduce the connection between that structure and sparsification. By leveraging such structure, we give two ways of computing strong sparsifications of poker games (as well as any other game with a similar structure) that are i) orders of magnitude faster to compute, ii) more numerically stable, and iii) produce a dramatically smaller number of nonzeros than the prior technique. Our techniques enable—for the first time—effective computation of high-precision Nash equilibria and strategies subject to constraints on the amount of allowed randomization. Furthermore, they significantly speed up parallel first-order game-solving algorithms; we show state-of-the-art speed on a GPU.
APA, Harvard, Vancouver, ISO, and other styles
7

Batson, Joshua, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng. "Spectral sparsification of graphs." Communications of the ACM 56, no. 8 (August 2013): 87–94. http://dx.doi.org/10.1145/2492007.2492029.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Bonnet, Édouard, and Vangelis Th Paschos. "Sparsification and subexponential approximation." Acta Informatica 55, no. 1 (October 12, 2016): 1–15. http://dx.doi.org/10.1007/s00236-016-0281-2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Spielman, Daniel A., and Shang-Hua Teng. "Spectral Sparsification of Graphs." SIAM Journal on Computing 40, no. 4 (January 2011): 981–1025. http://dx.doi.org/10.1137/08074489x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Butti, Silvia, and Stanislav Živný. "Sparsification of Binary CSPs." SIAM Journal on Discrete Mathematics 34, no. 1 (January 2020): 825–42. http://dx.doi.org/10.1137/19m1242446.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Sparsification"

1

Camacho, Martin Ayalde. "Spectral sparsification." Thesis, Harvard University, 2014. http://nrs.harvard.edu/urn-3:HUL.InstRepos:12553868.

Full text
Abstract:
We survey recent literature focused on the following spectral sparsification question: Given an integer n and > 0, does there exist a function N(n; ) such that for every collection of C1; : : : ;Cm of n n real symmetric positive semidefinite matrices whose sum is the identity, there exists a weighted subset of size N(n; ) whose sum has eigenvalues lying between 1 and 1 + ? We present the algorithms for solving this problem given in [4, 8, 10]. These algorithms obtain N(n; ) = O(n= 2), which is optimal up to constant factors, through use of the barrier method, a proof technique involving potential functions which control the locations of the eigenvalues of a matrix under certain matrix updates. We then survey the applications of this sparsification result and its proof techniques to graph sparsification [4, 10], low-rank matrix approximation [8], and estimating the covariance of certain distributions of random matrices [32, 26]. We end our survey by examining a multivariate generalization of the barrier method used in Marcus, Spielman, and Srivastava’s recent proof [19] of the Kadison-Singer conjecture.
APA, Harvard, Vancouver, ISO, and other styles
2

Oliveira, Rafael (Rafael Mendes de Oliveira). "Spectral sparsification and spectrally thin trees." Thesis, Massachusetts Institute of Technology, 2012. http://hdl.handle.net/1721.1/88906.

Full text
Abstract:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2012.
Cataloged from PDF version of thesis.
Includes bibliographical references (page 31).
We provide results of intensive experimental data in order to investigate the existence of spectrally thin trees and unweighted spectral sparsifiers for graphs with small expansion. In addition, we also survey and prove some partial results on the existence of spectrally thin trees on dense graphs with high enough expansion.
by Rafael Oliveira.
M. Eng.
APA, Harvard, Vancouver, ISO, and other styles
3

Moitra, Ankur. "Vertex sparsification and universal rounding algorithms." Thesis, Massachusetts Institute of Technology, 2011. http://hdl.handle.net/1721.1/66019.

Full text
Abstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011.
Cataloged from PDF version of thesis.
Includes bibliographical references (p. 125-129).
Suppose we are given a gigantic communication network, but are only interested in a small number of nodes (clients). There are many routing problems we could be asked to solve for our clients. Is there a much smaller network - that we could write down on a sheet of paper and put in our pocket - that approximately preserves all the relevant communication properties of the original network? As we will demonstrate, the answer to this question is YES, and we call this smaller network a vertex sparsifier. In fact, if we are asked to solve a sequence of optimization problems characterized by cuts or flows, we can compute a good vertex sparsifier ONCE and discard the original network. We can run our algorithms (or approximation algorithms) on the vertex sparsifier as a proxy - and still recover approximately optimal solutions in the original network. This novel pattern saves both space (because the network we store is much smaller) and time (because our algorithms run on a much smaller graph). Additionally, we apply these ideas to obtain a master theorem for graph partitioning problems - as long as the integrality gap of a standard linear programming relaxation is bounded on trees, then the integrality gap is at most a logarithmic factor larger for general networks. This result implies optimal bounds for many well studied graph partitioning problems as a special case, and even yields optimal bounds for more challenging problems that had not been studied before. Morally, these results are all based on the idea that even though the structure of optimal solutions can be quite complicated, these solution values can be approximated by crude (even linear) functions.
by Ankur Moitra.
Ph.D.
APA, Harvard, Vancouver, ISO, and other styles
4

Vial, John Francis Stephen. "Conservative Sparsification for Efficient Approximate Estimation." Thesis, The University of Sydney, 2013. http://hdl.handle.net/2123/9907.

Full text
Abstract:
Linear Gaussian systems often exhibit sparse structures. For systems which grow as a function of time, marginalisation of past states will eventually introduce extra non-zero elements into the information matrix of the Gaussian distribution. These extra non-zeros can lead to dense problems as these systems progress through time. This thesis proposes a method that can delete elements of the information matrix while maintaining guarantees about the conservativeness of the resulting estimate with a computational complexity that is a function of the connectivity of the graph rather than the problem dimension. This sparsification can be performed iteratively and minimises the Kullback Leibler Divergence (KLD) between the original and approximate distributions. This new technique is called Conservative Sparsification (CS). For large sparse graphs employing a Junction Tree (JT) for estimation, efficiency is related to the size of the largest clique. Conservative Sparsification can be applied to clique splitting in JTs, enabling approximate and efficient estimation in JTs with the same conservative guarantees as CS for information matrices. In distributed estimation scenarios which use JTs, CS can be performed in parallel and asynchronously on JT cliques. This approach usually results in a larger KLD compared with the optimal CS approach, but an upper bound on this increased divergence can be calculated with information locally available to each clique. This work has applications in large scale distributed linear estimation problems where the size of the problem or communication overheads make optimal linear estimation difficult.
APA, Harvard, Vancouver, ISO, and other styles
5

Ortmann, Mark [Verfasser]. "Combinatorial Algorithms for Graph Sparsification / Mark Ortmann." Konstanz : Bibliothek der Universität Konstanz, 2017. http://d-nb.info/1173616438/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Di, Jinchao. "Gene Co-expression Network Mining Using Graph Sparsification." The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1367583964.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Dahlin, Oskar. "Implementing and Evaluating sparsification methods in probabilistic networks." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-428591.

Full text
Abstract:
Most queries on probabilistic networks assume a possible world semantic, which causes an exponential increase in execution time. Deterministic networks can apply sparsification methods to reduce their sizes while preserving some structural properties, but there have not been any equivalent methods for probabilistic networks until recently. As a first work in the field, Parchas, Papailiou, Papadias and Bonchi have proposed sparsification methods for probabilistic networks by adapting a gradient descent and expectation-maximization algorithm. In this report the two proposed algorithms, Gradient Descent Backbone (GDB) and Expectation-Maximization Degree (EMD), were implemented and evaluated on different input parameters by comparing how well the general graph properties, expected vertex degrees and ego betweenness approximations are preserved after sparsifying different datasets. In the sparsified networks we found that the entropies had mostly gone down to zero, effectively creating a deterministic network. EMD generally showed better results than GDB specifically when using the relative discrepancies, however on lower alpha values the EMD methods can generate disconnected networks, more so when using absolute discrepancies. The methods produced unexpected results on higher alpha values which suggests they're not stable. Our evaluations have confirmed that the proposed algorithms produce acceptable results in some cases, however finding the right input parameters for specific networks can be time consuming. Therefore further testing on diverse structures of networks with different input parameters is recommended.Tryckt av:
APA, Harvard, Vancouver, ISO, and other styles
8

Tran, Gia-Lac. "Advances in Deep Gaussian Processes : calibration and sparsification." Electronic Thesis or Diss., Sorbonne université, 2020. https://accesdistant.sorbonne-universite.fr/login?url=https://theses-intra.sorbonne-universite.fr/2020SORUS410.pdf.

Full text
Abstract:
L'intégration des Convolutional Neural Networks (CNNs) et des GPs est une solution prometteuse pour améliorer le pouvoir de représentation des méthodes contemporaines. Dans notre première étude, nous utilisons des diagrammes de fiabilité pour montrer que les combinaisons actuelles de cnns et GPs sont mal calibrées, ce qui donne lieu à des prédictions trop confiantes. En utilisant des Random Feature et la technique d'inférence variationnelle, nous proposons une nouvelle solution correctement calibrée pour combinaisons des CNNs et des GPs. Nous proposons également une extension intuitive de cette solution, utilisant des Structured Random Features afin d'améliorer la précision du modèle et réduire la complexité des calculs. En termes de coût de calcul, la complexité du GPs exact est cubique en la taille de l'ensemble d'entrainement, ce qui le rend inutilisable lorsque celle-ci dépasse quelques milliers d'éléments. Afin de faciliter l'extension des GPs à des quantités massives de données, nous sélectionnons un petit ensemble de points actifs ou points d'induction par une distillation globale à partir de toutes les observations. Nous utilisons ensuite ces points actifs pour faire des prédictions. Plusieurs travaux similaires se basent sur l'étude Titsias et al en 2009 [5] and Hensman et al en 2015 [6]. Cependant, il est encore difficile de traiter le cas général, et il est toujours possible que le nombre de points actifs requis dépasse un budget de calcul donné. Dans notre deuxième étude, nous proposons Sparse-within-Sparse Gaussian Processes (SWSGP) qui permet l'approximation avec un grand nombre de points inducteurs sans cout de calcul prohibitif
Gaussian Processes (GPs) are an attractive specific way of doing non-parametric Bayesian modeling in a supervised learning problem. It is well-known that GPs are able to make inferences as well as predictive uncertainties with a firm mathematical background. However, GPs are often unfavorable by the practitioners due to their kernel's expressiveness and the computational requirements. Integration of (convolutional) neural networks and GPs are a promising solution to enhance the representational power. As our first contribution, we empirically show that these combinations are miscalibrated, which leads to over-confident predictions. We also propose a novel well-calibrated solution to merge neural structures and GPs by using random features and variational inference techniques. In addition, these frameworks can be intuitively extended to reduce the computational cost by using structural random features. In terms of computational cost, the exact Gaussian Processes require the cubic complexity to training size. Inducing point-based Gaussian Processes are a common choice to mitigate the bottleneck by selecting a small set of active points through a global distillation from available observations. However, the general case remains elusive and it is still possible that the required number of active points may exceed a certain computational budget. In our second study, we propose Sparse-within-Sparse Gaussian Processes which enable the approximation with a large number of inducing points without suffering a prohibitive computational cost
APA, Harvard, Vancouver, ISO, and other styles
9

Kanapka, Joseph D. (Joseph Daniel) 1972. "Fast methods for extraction and sparsification of substrate coupling." Thesis, Massachusetts Institute of Technology, 2002. http://hdl.handle.net/1721.1/29236.

Full text
Abstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.
Includes bibliographical references (p. 107-111).
Substrate coupling effects have had an increasing impact on circuit performance in recent years. As a result, there is strong demand for substrate simulation tools. Past work has concentrated on fast substrate solvers that are applied once per contact to get the dense conductance matrix G. We develop a method of using any underlying substrate solver a near-constant number of times to obtain a sparse approximate representation G [approximately equal to] QGwtQ' in a new basis. This method differs from previous matrix sparsification techniques in that it requires only a "black box" which can apply G quickly; it doesn't need an analytical representation of the underlying kernel or access to individual entries of G. The change-of-basis matrix Q is also sparse. For our largest example, with 10240 contacts, we obtained a Gwt with 130 times fewer nonzeros than the dense G (and Q more than twice as sparse as Gwt), with 20 times fewer solves than the naive method, and fewer than 4 percent of the QGwtQ' entries had relative error more than 10% compared to the exact G.
by Joseph Daniel Kanapka.
Ph.D.
APA, Harvard, Vancouver, ISO, and other styles
10

Geppert, Jakob Alexander [Verfasser]. "Adaptive Sparsification Mechanisms in Signal Recovery / Jakob Alexander Geppert." Göttingen : Niedersächsische Staats- und Universitätsbibliothek Göttingen, 2021. http://d-nb.info/1231542098/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Sparsification"

1

Cárdenas, Marcelo, Pascal Peter, and Joachim Weickert. "Sparsification Scale-Spaces." In Lecture Notes in Computer Science, 303–14. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-22368-7_24.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Goranci, Gramoz, and Harald Räcke. "Vertex Sparsification in Trees." In Approximation and Online Algorithms, 103–15. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-51741-4_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Gionis, Aristides, Polina Rozenshtein, Nikolaj Tatti, and Evimaria Terzi. "Community-aware network sparsification." In Proceedings of the 2017 SIAM International Conference on Data Mining, 426–34. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017. http://dx.doi.org/10.1137/1.9781611974973.48.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Soma, Tasuku, and Yuichi Yoshida. "Spectral Sparsification of Hypergraphs." In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2570–81. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2019. http://dx.doi.org/10.1137/1.9781611975482.159.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Ahmed, Reyan, Keaton Hamm, Stephen Kobourov, Mohammad Javad Latifi Jebelli, Faryad Darabi Sahneh, and Richard Spence. "Multi-priority Graph Sparsification." In Lecture Notes in Computer Science, 1–12. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-34347-6_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Mouysset, Sandrine, and Ronan Guivarch. "Sparsification on Parallel Spectral Clustering." In Lecture Notes in Computer Science, 249–60. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-38718-0_25.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Gollub, Tim, and Benno Stein. "Unsupervised Sparsification of Similarity Graphs." In Studies in Classification, Data Analysis, and Knowledge Organization, 71–79. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-10745-0_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Jansen, Bart M. P. "On Sparsification for Computing Treewidth." In Parameterized and Exact Computation, 216–29. Cham: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-319-03898-8_19.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Schleif, Frank-Michael, Christoph Raab, and Peter Tino. "Sparsification of Indefinite Learning Models." In Lecture Notes in Computer Science, 173–83. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-97785-0_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Santhanam, Rahul, and Srikanth Srinivasan. "On the Limits of Sparsification." In Automata, Languages, and Programming, 774–85. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31594-7_65.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Sparsification"

1

Li, Huan, and Aaron Schild. "Spectral Subspace Sparsification." In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2018. http://dx.doi.org/10.1109/focs.2018.00044.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Woerner, Peter C., Aditya G. Nair, Kunihiko Taira, and William S. Oates. "Network Theoretic Approach to Atomistic Material Modeling Using Spectral Sparsification." In ASME 2017 Conference on Smart Materials, Adaptive Structures and Intelligent Systems. American Society of Mechanical Engineers, 2017. http://dx.doi.org/10.1115/smasis2017-3917.

Full text
Abstract:
Network theory is used to formulate an atomistic material network. Spectral sparsification is applied to the network as a method for approximating the interatomic forces. Local molecular forces and the total force balance is quantified when the internal forces are approximated. In particular, we compare spectral sparsification to conventional thresholding (radial cut-off distance) of molecular forces for a Lennard-Jones potential and a Coulomb potential. The spectral sparsification for the Lennard-Jones potential yields comparable results while spectral sparsification of the Coulomb potential outperforms the thresholding approach. The results show promising opportunities which may accelerate molecular simulations containing long-range electrical interactions which are relevant to many multifunctional materials.
APA, Harvard, Vancouver, ISO, and other styles
3

Shi, Shaohuai, Kaiyong Zhao, Qiang Wang, Zhenheng Tang, and Xiaowen Chu. "A Convergence Analysis of Distributed SGD with Communication-Efficient Gradient Sparsification." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/473.

Full text
Abstract:
Gradient sparsification is a promising technique to significantly reduce the communication overhead in decentralized synchronous stochastic gradient descent (S-SGD) algorithms. Yet, many existing gradient sparsification schemes (e.g., Top-k sparsification) have a communication complexity of O(kP), where k is the number of selected gradients by each worker and P is the number of workers. Recently, the gTop-k sparsification scheme has been proposed to reduce the communication complexity from O(kP) to O(k logP), which significantly boosts the system scalability. However, it remains unclear whether the gTop-k sparsification scheme can converge in theory. In this paper, we first provide theoretical proofs on the convergence of the gTop-k scheme for non-convex objective functions under certain analytic assumptions. We then derive the convergence rate of gTop-k S-SGD, which is at the same order as the vanilla mini-batch SGD. Finally, we conduct extensive experiments on different machine learning models and data sets to verify the soundness of the assumptions and theoretical results, and discuss the impact of the compression ratio on the convergence performance.
APA, Harvard, Vancouver, ISO, and other styles
4

Garg, Rahul, and Rohit Khandekar. "Gradient descent with sparsification." In the 26th Annual International Conference. New York, New York, USA: ACM Press, 2009. http://dx.doi.org/10.1145/1553374.1553417.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Lovett, Shachar, and Jiapeng Zhang. "DNF sparsification beyond sunflowers." In STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing. New York, NY, USA: ACM, 2019. http://dx.doi.org/10.1145/3313276.3316323.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Tavakoli, Hamed R., Joachim Wabnig, Francesco Cricri, Honglei Zhang, Emre Aksu, and Iraj Saniee. "Hybrid Pruning And Sparsification." In 2021 IEEE International Conference on Image Processing (ICIP). IEEE, 2021. http://dx.doi.org/10.1109/icip42928.2021.9506632.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Meidiana, Amyra, Seok-Hee Hong, Jiajun Huang, Peter Eades, and Kwan-Liu Ma. "Topology-Based Spectral Sparsification." In 2019 IEEE 9th Symposium on Large Data Analysis and Visualization (LDAV). IEEE, 2019. http://dx.doi.org/10.1109/ldav48142.2019.8944358.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Mathioudakis, Michael, Francesco Bonchi, Carlos Castillo, Aristides Gionis, and Antti Ukkonen. "Sparsification of influence networks." In the 17th ACM SIGKDD international conference. New York, New York, USA: ACM Press, 2011. http://dx.doi.org/10.1145/2020408.2020492.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Zheng, Fei, Chaochao Chen, Lingjuan Lyu, and Binhui Yao. "Reducing Communication for Split Learning by Randomized Top-k Sparsification." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/519.

Full text
Abstract:
Split learning is a simple solution for Vertical Federated Learning (VFL), which has drawn substantial attention in both research and application due to its simplicity and efficiency. However, communication efficiency is still a crucial issue for split learning. In this paper, we investigate multiple communication reduction methods for split learning, including cut layer size reduction, top-k sparsification, quantization, and L1 regularization. Through analysis of the cut layer size reduction and top-k sparsification, we further propose randomized top-k sparsification, to make the model generalize and converge better. This is done by selecting top-k elements with a large probability while also having a small probability to select non-top-k elements. Empirical results show that compared with other communication-reduction methods, our proposed randomized top-k sparsification achieves a better model performance under the same compression level.
APA, Harvard, Vancouver, ISO, and other styles
10

Chakeri, Alireza, Hamidreza Farhidzadeh, and Lawrence O. Hall. "Spectral sparsification in spectral clustering." In 2016 23rd International Conference on Pattern Recognition (ICPR). IEEE, 2016. http://dx.doi.org/10.1109/icpr.2016.7899979.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Sparsification' for particular source types:
Journal articles Dissertations / Theses
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography