{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T05:08:15Z","timestamp":1737176895472,"version":"3.33.0"},"reference-count":105,"publisher":"IEEE","license":[{"start":{"date-parts":[[2024,12,15]],"date-time":"2024-12-15T00:00:00Z","timestamp":1734220800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2024,12,15]],"date-time":"2024-12-15T00:00:00Z","timestamp":1734220800000},"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":[[2024,12,15]]},"DOI":"10.1109\/bigdata62323.2024.10825010","type":"proceedings-article","created":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T18:31:23Z","timestamp":1737052283000},"page":"44-53","source":"Crossref","is-referenced-by-count":0,"title":["Faster Sampling Algorithms for Polytopes with Small Treewidth"],"prefix":"10.1109","author":[{"given":"Yekun","family":"Ke","sequence":"first","affiliation":[{"name":"University of Washington,Department of Computer Science,Seattle,WA"}]},{"given":"Xiaoyu","family":"Li","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology,Department of Computer Science,Hoboken,NJ"}]},{"given":"Zhao","family":"Song","sequence":"additional","affiliation":[{"name":"The Simons Institute for the Theory of Computing University of California, Berkeley,Berkeley,CA"}]},{"given":"Tianyi","family":"Zhou","sequence":"additional","affiliation":[{"name":"University of Southern California,Department of Computer Science,Los Angeles,CA"}]}],"member":"263","reference":[{"issue":"1","key":"ref1","first-page":"4017","article-title":"Efficient sampling from time-varying log-concave distributions","volume":"18","author":"Narayanan","year":"2017","journal-title":"The Journal of Machine Learning Research"},{"key":"ref2","article-title":"Fast mcmc sampling algorithms on polytopes","author":"Chen","year":"2018","journal-title":"J. Mach. Learn. Res."},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188774"},{"article-title":"Faster sampling from log-concave distributions over polytopes via a soft-threshold dikin walk","year":"2022","author":"Mangoubi","key":"ref4"},{"issue":"4","key":"ref5","first-page":"747","article-title":"Iterative solution of problems of linear and quadratic programming","volume-title":"Doklady Akademii Nauk","volume":"174","author":"Dikin","year":"1967"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63500"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1142\/9789814354363_0021"},{"key":"ref8","first-page":"187","article-title":"Extremum problems with inequalities as subsidiary conditions","volume-title":"Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948.","author":"John","year":"1948"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"ref10","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718881","volume-title":"Direct methods for sparse linear systems.","author":"Davis","year":"2006"},{"issue":"105","key":"ref11","article-title":"Lower bounds based on the exponential time hypothesis","volume":"3","author":"Lokshtanov","year":"2013","journal-title":"Bulletin of EATCS"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01516-y"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1145\/3186898"},{"article-title":"A nearly-linear time algorithm for structured support vector machines","year":"2023","author":"Gu","key":"ref14"},{"issue":"1-2","key":"ref15","first-page":"1","article-title":"A tourist guide through treewidth","volume":"11","author":"Bodlaender","year":"1994","journal-title":"Acta cybernetica"},{"article-title":"Space-efficient interior point method, with applications to linear programming and maximum weight bipartite matching","year":"2022","author":"Liu","key":"ref16"},{"article-title":"Faster algorithm for structured john ellipsoid computation","year":"2022","author":"Song","key":"ref17"},{"article-title":"Faster sinkhorn\u2019s algorithm with small treewidth","year":"2023","author":"Song","key":"ref18"},{"article-title":"A faster small treewidth sdp solver","year":"2022","author":"Gu","key":"ref19"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103439"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20135"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.28"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004973"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1029962595"},{"key":"ref25","article-title":"Finite-time analysis of projected langevin monte carlo","volume":"28","author":"Bubeck","year":"2015","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref26","first-page":"319","article-title":"Sampling from a log-concave distribution with compact support with proximal langevin monte carlo","volume-title":"Conference on learning theory","author":"Brosse"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536491"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1214\/15-AAP1104"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2016.07.005"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055416"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.96"},{"key":"ref32","article-title":"Hit-and-run is fast and fun","author":"Lov\u00e1sz","year":"2003","journal-title":"preprint, Microsoft Research"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2017.8262876"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451018"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316303"},{"key":"ref36","article-title":"Solving empirical risk minimization in the current matrix multiplication time","author":"Lee","year":"2019","journal-title":"COLT"},{"key":"ref37","article-title":"Faster dynamic matrix inverse for faster lps","author":"Jiang","year":"2021","journal-title":"STOC. arXiv preprint arXiv"},{"article-title":"Oblivious sketching-based central path method for solving linear programming problems","volume-title":"38th International Conference on Machine Learning (ICML)","author":"Song","key":"ref38"},{"key":"ref39","article-title":"Space-efficient interior point method, with applications to linear programming and maximum weight bipartite matching","author":"Liu","year":"2023","journal-title":"ICALP"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00089"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00029"},{"key":"ref42","first-page":"101","article-title":"An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization","volume-title":"International Conference on Artificial Intelligence and Statistics (AISTATS)","author":"Qin"},{"article-title":"Solving regularized exp, cosh and sinh regression problems","year":"2023","author":"Li","key":"ref43"},{"article-title":"Attention scheme inspired softmax regression","year":"2023","author":"Deng","key":"ref44"},{"article-title":"A mathematical abstraction for balancing the trade-off between creativity and reality in large language models","year":"2023","author":"Sinha","key":"ref45"},{"article-title":"An iterative algorithm for rescaled hyperbolic functions regression","year":"2023","author":"Gao","key":"ref46"},{"article-title":"Gradientcoin: A peer-to-peer decentralized large language models","year":"2023","author":"Gao","key":"ref47"},{"article-title":"Convergence of two-layer regression with nonlinear units","year":"2023","author":"Deng","key":"ref48"},{"article-title":"How to protect copyright data in optimization of large language models?","year":"2023","author":"Chu","key":"ref49"},{"article-title":"A tighter complexity analysis of sparsegpt","year":"2024","author":"Li","key":"ref50"},{"article-title":"Fine-grained attention i\/o complexity: Comprehensive analysis for backward passes","year":"2024","author":"Li","key":"ref51"},{"article-title":"Bypassing the exponential dependency: Looped transformers efficiently learn in-context by multi-step gradient descent","year":"2024","author":"Chen","key":"ref52"},{"article-title":"Tensor attention training: Provably efficient learning of higher-order transformers","year":"2024","author":"Liang","key":"ref53"},{"article-title":"Beyond linear approximations: A novel pruning approach for attention matrix","year":"2024","author":"Liang","key":"ref54"},{"article-title":"Hsr-enhanced sparse attention acceleration","year":"2024","author":"Chen","key":"ref55"},{"key":"ref56","article-title":"A $\\sqrt n $ passes streaming algorithm for solving bipartite matching exactly","author":"Brand","year":"2023","journal-title":"Manuscript"},{"key":"ref57","article-title":"Learning overparameterized neural networks via stochastic gradient descent on structured data","volume":"31","author":"Li","year":"2018","journal-title":"Advances in neural information processing systems"},{"article-title":"Gradient descent provably optimizes over-parameterized neural networks","year":"2018","author":"Du","key":"ref58"},{"key":"ref59","first-page":"242","article-title":"A convergence theory for deep learning via over-parameterization","volume-title":"International Conference on machine learning","author":"Allen-Zhu"},{"key":"ref60","article-title":"On the convergence rate of training recurrent neural networks","volume":"32","author":"Allen-Zhu","year":"2019","journal-title":"Advances in neural information processing systems"},{"key":"ref61","first-page":"322","article-title":"Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks","volume-title":"International Conference on Machine Learning","author":"Arora"},{"key":"ref62","article-title":"On exact computation with an infinitely wide neural net","volume":"32","author":"Arora","year":"2019","journal-title":"Advances in neural information processing systems"},{"article-title":"Quadratic suffices for over-parametrization via matrix chernoff bound","year":"2019","author":"Song","key":"ref63"},{"article-title":"Gram-gauss-newton method: Learning overparameterized neural networks for regression problems","year":"2019","author":"Cai","key":"ref64"},{"key":"ref65","article-title":"Fast convergence of natural gradient descent for over-parameterized neural networks","volume":"32","author":"Zhang","year":"2019","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref66","article-title":"Generalization bounds of stochastic gradient descent for wide and deep neural networks","volume":"32","author":"Cao","year":"2019","journal-title":"Advances in neural information processing systems"},{"key":"ref67","article-title":"An improved analysis of training over-parameterized deep neural networks","volume":"32","author":"Zou","year":"2019","journal-title":"Advances in neural information processing systems"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1109\/JSAIT.2020.2991332"},{"article-title":"Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks","year":"2019","author":"Ji","key":"ref69"},{"key":"ref70","first-page":"10775","article-title":"Generalized leverage score sampling for neural networks","volume":"33","author":"Lee","year":"2020","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref71","first-page":"4423","article-title":"Fl-ntk: A neural tangent kernel-based framework for federated learning analysis","volume-title":"International Conference on Machine Learning","author":"Huang"},{"key":"ref72","first-page":"679","article-title":"Over-parameterized adversarial training: An analysis overcoming the curse of dimensionality","volume":"33","author":"Zhang","year":"2020","journal-title":"Advances in Neural Information Processing Systems"},{"article-title":"Training (overparametrized) neural networks in near-linear time","year":"2020","author":"Brand","key":"ref73"},{"key":"ref74","first-page":"15383","article-title":"Why are adaptive methods good for attention models?","volume":"33","author":"Zhang","year":"2020","journal-title":"Advances in Neural Information Processing Systems"},{"article-title":"Training multi-layer overparametrized neural network in subquadratic time","year":"2021","author":"Song","key":"ref75"},{"article-title":"Bypass exponential time preprocessing: Fast neural network training via weight-data correlation preprocessing","year":"2022","author":"Alman","key":"ref76"},{"key":"ref77","first-page":"16083","article-title":"Bounding the width of neural networks via coupled initialization a worst case analysis","volume-title":"International Conference on Machine Learning","author":"Munteanu"},{"key":"ref78","article-title":"Speeding up optimizations via data structures: Faster search, sample and maintenance","volume-title":"Ph.D. dissertation, Master\u2019s thesis","author":"Zhang","year":"2022"},{"article-title":"An over-parameterized exponential regression","year":"2023","author":"Gao","key":"ref79"},{"article-title":"Efficient sgd neural network training via sublinear activated neuron identification","year":"2023","author":"Qin","key":"ref80"},{"article-title":"Multi-layer transformers gradient can be approximated in almost linear time","year":"2024","author":"Liang","key":"ref81"},{"article-title":"Differential privacy mechanisms in neural tangent kernel regression","year":"2024","author":"Gu","key":"ref82"},{"article-title":"Advancing the understanding of fixed point iterations in deep neural networks: A detailed analytical study","year":"2024","author":"Ke","key":"ref83"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"ref85","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.21"},{"key":"ref86","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488621"},{"key":"ref87","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897639"},{"article-title":"Low rank approximation with entrywise \u21131-norm error","volume-title":"Proceedings of the 49th Annual Symposium on the Theory of Computing (STOC)","author":"Song","key":"ref88"},{"key":"ref89","article-title":"Near optimal sketching of low-rank tensor regression","author":"Haupt","year":"2017","journal-title":"ICML"},{"key":"ref90","first-page":"224","article-title":"Subspace embedding and linear regression with orlicz norm","volume-title":"International Conference on Machine Learning (ICML)","author":"Andoni"},{"key":"ref91","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":"ref92","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":"ref93","article-title":"Optimal sketching for kronecker product regression and low rank approximation","volume":"32","author":"Diao","year":"2019","journal-title":"Advances in neural information processing systems"},{"article-title":"Low rank matrix completion via robust alternating minimization in nearly linear time","year":"2023","author":"Gu","key":"ref94"},{"key":"ref95","article-title":"Speeding up optimizations via data structures: Faster search, sample and maintenance","volume-title":"Master\u2019s thesis","author":"Zhang","year":"2022"},{"key":"ref96","first-page":"8253","article-title":"Fetchsgd: Communication-efficient federated learning with sketching","volume-title":"International Conference on Machine Learning","author":"Rothchild"},{"key":"ref97","first-page":"32365","article-title":"Sketching for first order method: efficient algorithm for low-bandwidth channel and vulnerability","volume-title":"International Conference on Machine Learning (ICML)","author":"Song"},{"key":"ref98","first-page":"32418","article-title":"Sketching meets differential privacy: fast algorithm for dynamic kronecker projection maintenance","volume-title":"International Conference on Machine Learning (ICML)","author":"Song"},{"key":"ref99","first-page":"166","article-title":"Modular multitask reinforcement learning with policy sketches","volume-title":"International Conference on Machine Learning","author":"Andreas"},{"article-title":"Planning with general objective functions: Going beyond total rewards","volume-title":"Annual Conference on Neural Information Processing Systems (NeurIPS)","author":"Wang","key":"ref100"},{"key":"ref101","article-title":"Sublinear least-squares value iteration via locality sensitive hashing","author":"Shrivastava","year":"2021","journal-title":"CoRR"},{"key":"ref102","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574267"},{"key":"ref103","first-page":"849","article-title":"A near-optimal algorithm for approximating the john ellipsoid","volume-title":"Conference on Learning Theory","author":"Cohen"},{"article-title":"Fast john ellipsoid computation with differential privacy optimization","year":"2024","author":"Li","key":"ref104"},{"article-title":"Quantum speedups for approximating the john ellipsoid","year":"2024","author":"Li","key":"ref105"}],"event":{"name":"2024 IEEE International Conference on Big Data (BigData)","start":{"date-parts":[[2024,12,15]]},"location":"Washington, DC, USA","end":{"date-parts":[[2024,12,18]]}},"container-title":["2024 IEEE International Conference on Big Data (BigData)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx8\/10824975\/10824942\/10825010.pdf?arnumber=10825010","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T08:18:30Z","timestamp":1737101910000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10825010\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,15]]},"references-count":105,"URL":"https:\/\/doi.org\/10.1109\/bigdata62323.2024.10825010","relation":{},"subject":[],"published":{"date-parts":[[2024,12,15]]}}}