{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T07:18:26Z","timestamp":1772090306471,"version":"3.50.1"},"reference-count":126,"publisher":"IEEE","license":[{"start":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T00:00:00Z","timestamp":1762905600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T00:00:00Z","timestamp":1762905600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,11,12]]},"DOI":"10.1109\/icdm65498.2025.00049","type":"proceedings-article","created":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T20:53:50Z","timestamp":1772052830000},"page":"417-426","source":"Crossref","is-referenced-by-count":0,"title":["Fast Sampling for Privacy-Preserving Lazy Multiplicative Weight Update"],"prefix":"10.1109","author":[{"given":"Xiaoyu","family":"Li","sequence":"first","affiliation":[{"name":"Stevens Institute of Technology,United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhao","family":"Song","sequence":"additional","affiliation":[{"name":"University of California,Berkeley,United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiale","family":"Zhao","sequence":"additional","affiliation":[{"name":"Guangdong University of Technology,China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688086"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.39"},{"key":"ref5","first-page":"116","article-title":"Follow the compressed leader: Faster online learning of eigenvectors and faster mmwu","volume-title":"ICML","author":"Allen-Zhu","year":"2017"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.24"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1109\/JSYST.2021.3114393"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0738"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772758"},{"key":"ref10","article-title":"Non-stochastic bandit slate problems","volume":"23","author":"Kale","year":"2010","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/3164539"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/24"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.1706.03762"},{"key":"ref14","article-title":"Mongoose: A learnable lsh framework for efficient neural network training","author":"Chen","year":"2020","journal-title":"ICLR"},{"key":"ref15","article-title":"An image is worth 16\u00d716 words: Transformers for image recognition at scale","volume-title":"International Conference on Learning Representations","author":"Dosovitskiy","year":"2020"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"ref17","first-page":"43 544","article-title":"Differentially private approximate near neighbor counting in high dimensions","volume":"36","author":"Andoni","year":"2023","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref18","article-title":"Differentially private one permutation hashing and bin-wise consistent weighted sampling","author":"Li","year":"2023","journal-title":"arXiv preprint"},{"key":"ref19","article-title":"Robust algorithms on adaptive inputs from bounded adversaries","volume-title":"arXiv preprint","author":"Cherapanamjeri"},{"key":"ref20","first-page":"32 418","article-title":"Sketching meets differential privacy: fast algorithm for dynamic kronecker projection maintenance","volume-title":"ICML","author":"Song","year":"2023"},{"key":"ref21","article-title":"On differential privacy for adaptively solving search problems via sketching","author":"Feng","year":"2025","journal-title":"ICML"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574267"},{"key":"ref23","article-title":"Dpbloom-filter: Securing bloom filters with differential privacy","author":"Ke","year":"2025","journal-title":"arXiv preprint"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/3436755"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.14649"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.4236\/jsea.2024.171001"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v38i18.29967"},{"key":"ref28","article-title":"Differentially private attention computation","author":"Gao","year":"2023","journal-title":"arXiv preprint"},{"key":"ref29","article-title":"Differential privacy of cross-attention with provable guarantee","author":"Liang","year":"2024","journal-title":"arXiv preprint"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1109\/WACV61041.2025.00234"},{"key":"ref31","article-title":"Differentially private kernel density estimation","author":"Liu","year":"2024","journal-title":"arXiv preprint"},{"key":"ref32","article-title":"On differentially private string distances","author":"Hu","year":"2024","journal-title":"arXiv preprint"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.85"},{"key":"ref34","article-title":"Differential privacy for growing databases","volume":"31","author":"Cummings","year":"2018","journal-title":"Advances in NeurIPS"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132597"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.21"},{"key":"ref39","first-page":"32463","article-title":"A nearly-optimal bound for fast regression with \u2113\u221e guarantee","volume-title":"ICML","author":"Song","year":"2023"},{"key":"ref40","article-title":"Revisiting quantum algorithms for linear regressions: Quadratic speedups without data-dependent parameters","author":"Song","year":"2023","journal-title":"arXiv preprint"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591819"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897639"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055431"},{"key":"ref44","volume-title":"Near optimal sketching of low-rank tensor regression","author":"Haupt","year":"2017"},{"key":"ref45","first-page":"224","article-title":"Subspace embedding and linear regression with orlicz norm","volume-title":"ICML","author":"Andoni","year":"2018"},{"key":"ref46","first-page":"10111","article-title":"Average case column subset selection for entrywise \u21131-norm loss","volume":"32","author":"Song","year":"2019","journal-title":"Advances in Neural Information Processing Systems (NeurIPS)"},{"key":"ref47","first-page":"6123","article-title":"Towards a zero-one law for column subset selection","volume":"32","author":"Song","year":"2019","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref48","article-title":"Efficient alternating minimization with applications to weighted low rank approximation","author":"Song","year":"2023","journal-title":"arXiv preprint"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498295"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897646"},{"key":"ref51","article-title":"Solving attention kernel regression problem via pre-conditioner","author":"Song","year":"2023","journal-title":"arXiv preprint"},{"key":"ref52","article-title":"A fast optimization view: Reformulating single layer attention in llm based on tensor and svm trick, and solving it in matrix multiplication time","author":"Gao","year":"2023","journal-title":"arXiv preprint"},{"key":"ref53","article-title":"An iterative algorithm for rescaled hyperbolic functions regression","author":"Gao","year":"2023","journal-title":"arXiv preprint"},{"key":"ref54","first-page":"32365","article-title":"Sketching for first order method: efficient algorithm for low-bandwidth channel and vulnerability","volume-title":"ICML","author":"Song","year":"2023"},{"key":"ref55","article-title":"Planning with general objective functions: Going beyond total rewards","volume-title":"Annual Conference on Neural Information Processing Systems (NeurIPS)","author":"Wang","year":"2020"},{"key":"ref56","article-title":"Sublinear least-squares value iteration via locality sensitive hashing","author":"Shrivastava","year":"2021","journal-title":"arXiv preprint"},{"key":"ref57","first-page":"5576","article-title":"Breaking the linear iteration cost barrier for some well-known conditional gradient methods using maxip data-structures","volume":"34","author":"Xu","year":"2021","journal-title":"Advances in NeurIPS"},{"key":"ref58","article-title":"Federated empirical risk minimization via second-order method","author":"Bian","year":"2023","journal-title":"arXiv preprint"},{"key":"ref59","article-title":"Does preprocessing help training over-parameterized neural networks?","volume":"34","author":"Song","year":"2021","journal-title":"Advances in NeurIPS"},{"key":"ref60","article-title":"Training multilayer over-parametrized neural network in subquadratic time","author":"Song","year":"2021","journal-title":"arXiv preprint"},{"key":"ref61","first-page":"2258","article-title":"Subspace embeddings for the polynomial kernel","author":"Avron","year":"2014","journal-title":"Advances in Neural Information Processing Systems 27"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1145\/2493252.2493254"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487591"},{"key":"ref64","first-page":"1299","article-title":"Sketching for kronecker product regression and p-splines","volume-title":"AIstats","author":"Diao","year":"2018"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.172"},{"key":"ref66","article-title":"Faster robust tensor power method for arbitrary order","author":"Deng","year":"2023","journal-title":"arXiv preprint"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i8.16902"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384284"},{"key":"ref69","article-title":"Low rank matrix completion via robust alternating minimization in nearly linear time","author":"Gu","year":"2023","journal-title":"arXiv preprint"},{"key":"ref70","first-page":"2275","article-title":"Bourgan: generative networks with metric embeddings","author":"Xiao","year":"2018","journal-title":"NeurIPS"},{"key":"ref71","first-page":"2140","article-title":"Solving empirical risk minimization in the current matrix multiplication time","volume-title":"Conference on Learning Theory","author":"Lee","year":"2019"},{"key":"ref72","article-title":"Faster dynamic matrix inverse for faster lps","author":"Jiang","year":"2021","journal-title":"STOC. arXiv preprint"},{"key":"ref73","first-page":"9835","article-title":"Oblivious sketching-based central path method for linear programming","volume-title":"ICML","author":"Song","year":"2021"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014464"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/389"},{"key":"ref76","first-page":"4202","article-title":"One-pass diversified sampling with application to terabyte-scale genomic sequence streams","volume-title":"ICML","author":"Coleman","year":"2022"},{"key":"ref77","article-title":"Fast and accurate stochastic gradient estimation","volume":"32","author":"Chen","year":"2019","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref78","article-title":"Locality sensitive teaching","volume":"34","author":"Xu","year":"2021","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref79","first-page":"2319","article-title":"A tale of two efficient and informative negative sampling distributions","volume-title":"ICML","author":"Daghaghi","year":"2021"},{"key":"ref80","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"ref81","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.76"},{"key":"ref83","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746553"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.4"},{"key":"ref85","article-title":"Adaptive online gradient descent","volume":"20","author":"Hazan","year":"2007","journal-title":"Advances in neural information processing systems"},{"key":"ref86","article-title":"On the universality of online mirror descent","volume":"24","author":"Srebro","year":"2011","journal-title":"Advances in neural information processing systems"},{"key":"ref87","doi-asserted-by":"publisher","DOI":"10.1145\/2465529.2465533"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.1109\/MCS.2011.940571"},{"key":"ref89","first-page":"101","article-title":"An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization","volume-title":"AIstats","author":"Qin","year":"2023"},{"key":"ref90","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.11.003"},{"key":"ref91","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2006.872343"},{"key":"ref92","doi-asserted-by":"publisher","DOI":"10.1198\/10857110260141193"},{"issue":"3","key":"ref93","first-page":"47","article-title":"Support vector machines with binary tree architecture for multiclass classification","volume":"2","author":"Cheong","year":"2004","journal-title":"Neural Information Processing-Letters and Reviews"},{"key":"ref94","doi-asserted-by":"publisher","DOI":"10.1145\/570738.570750"},{"key":"ref95","doi-asserted-by":"publisher","DOI":"10.1145\/2629582"},{"key":"ref96","doi-asserted-by":"publisher","DOI":"10.1145\/1095890.1095904"},{"key":"ref97","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214082"},{"key":"ref98","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"ref99","doi-asserted-by":"publisher","DOI":"10.1145\/6617.6621"},{"key":"ref100","doi-asserted-by":"publisher","DOI":"10.1145\/50087.50096"},{"key":"ref101","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"ref102","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2198"},{"key":"ref103","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109693"},{"key":"ref104","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq697"},{"key":"ref105","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.03.011"},{"key":"ref106","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/978-3-540-70575-8_32","article-title":"Succinct data structures for retrieval and approximate membership","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Dietzfelbinger","year":"2008"},{"key":"ref107","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45030-3_47"},{"key":"ref108","article-title":"Space-efficient interior point method, with applications to linear programming and maximum weight bipartite matching","author":"Liu","year":"2020","journal-title":"arXiv preprint"},{"key":"ref109","doi-asserted-by":"publisher","DOI":"10.1145\/3424305"},{"key":"ref110","article-title":"Faster dynamic matrix inverse for faster lps","author":"Jiang","year":"2020","journal-title":"arXiv preprint"},{"key":"ref111","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384309"},{"key":"ref112","volume-title":"Matrix theory: optimization, concentration, and algorithms","author":"Song","year":"2019"},{"key":"ref113","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00089"},{"key":"ref114","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00029"},{"key":"ref115","article-title":"A faster small treewidth sdp solver","author":"Gu","year":"2022","journal-title":"arXiv preprint"},{"key":"ref116","article-title":"Streaming semidefinite programs: o(\\\u221a{n}) passes, small space and fast runtime","author":"Song","year":"2023","journal-title":"arXiv preprint"},{"key":"ref117","first-page":"1","article-title":"Solving tall dense sdps in the current matrix multiplication time","volume":"6","author":"Huang","year":"2021","journal-title":"arXiv preprint"},{"key":"ref118","article-title":"Faster algorithm for structured john ellipsoid computation","author":"Song","year":"2022","journal-title":"arXiv preprint"},{"key":"ref119","article-title":"Fast john ellipsoid computation with differential privacy optimization","author":"Li","year":"2024","journal-title":"arXiv preprint"},{"key":"ref120","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.129"},{"key":"ref121","article-title":"Accelerating frank-wolfe algorithm using low-dimensional and adaptive data structures","author":"Song","year":"2022","journal-title":"arXiv preprint"},{"key":"ref122","article-title":"Dissecting submission limit in deskrejections: A mathematical analysis of fairness in ai conference policies","volume-title":"arXiv preprint","author":"Cao","year":"2025"},{"key":"ref123","article-title":"Accept more, reject less: Reducing up to 19% unnecessary desk-rejections over 11 years of iclr data","author":"Li","year":"2025","journal-title":"arXiv preprint"},{"key":"ref124","article-title":"Faster algorithms for structured linear and kernel support vector machines","author":"Gu","year":"2023","journal-title":"arXiv preprint"},{"key":"ref125","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"ref126","first-page":"89","article-title":"Tight analysis of privacy and utility tradeoff in approximate differential privacy","volume-title":"AIstats","author":"Geng","year":"2020"}],"event":{"name":"2025 IEEE International Conference on Data Mining (ICDM)","location":"Washington DC, DC, USA","start":{"date-parts":[[2025,11,12]]},"end":{"date-parts":[[2025,11,15]]}},"container-title":["2025 IEEE International Conference on Data Mining (ICDM)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx8\/11391637\/11391711\/11391940.pdf?arnumber=11391940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T06:50:05Z","timestamp":1772088605000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/11391940\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,12]]},"references-count":126,"URL":"https:\/\/doi.org\/10.1109\/icdm65498.2025.00049","relation":{},"subject":[],"published":{"date-parts":[[2025,11,12]]}}}