Zhao Song

CoRR, 2024

Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Study.

[BibT_eX]

[DOI]

CoRR, 2024

Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descent.

[BibT_eX]

[DOI]

CoRR, 2024

Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrix.

[BibT_eX]

[DOI]

CoRR, 2024

HSR-Enhanced Sparse Attention Acceleration.

[BibT_eX]

[DOI]

CoRR, 2024

Fine-grained Attention I/O Complexity: Comprehensive Analysis for Backward Passes.

[BibT_eX]

[DOI]

CoRR, 2024

Looped ReLU MLPs May Be All You Need as Practical Programmable Computers.

[BibT_eX]

[DOI]

CoRR, 2024

Log-concave Sampling over a Convex Body with a Barrier: a Robust and Unified Dikin Walk.

[BibT_eX]

[DOI]

CoRR, 2024

Differentially Private Kernel Density Estimation.

[BibT_eX]

[DOI]

CoRR, 2024

Quantum Speedups for Approximating the John Ellipsoid.

[BibT_eX]

[DOI]

Xiaoyu Li

Junwei Yu

CoRR, 2024

Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time.

[BibT_eX]

[DOI]

CoRR, 2024

A Tighter Complexity Analysis of SparseGPT.

[BibT_eX]

[DOI]

CoRR, 2024

Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method.

[BibT_eX]

[DOI]

CoRR, 2024

Fast John Ellipsoid Computation with Differential Privacy Optimization.

[BibT_eX]

[DOI]

CoRR, 2024

Differential Privacy of Cross-Attention with Provable Guarantee.

[BibT_eX]

[DOI]

CoRR, 2024

Differential Privacy Mechanisms in Neural Tangent Kernel Regression.

[BibT_eX]

[DOI]

CoRR, 2024

On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs).

[BibT_eX]

[DOI]

CoRR, 2024

Toward Infinite-Long Prefix in Transformer.

[BibT_eX]

[DOI]

CoRR, 2024

Computational Limits of Low-Rank Adaptation (LoRA) for Transformer-Based Models.

[BibT_eX]

[DOI]

CoRR, 2024

Unraveling the Smoothness Properties of Diffusion Models: A Gaussian Mixture Perspective.

[BibT_eX]

[DOI]

CoRR, 2024

Tensor Attention Training: Provably Efficient Learning of Higher-order Transformers.

[BibT_eX]

[DOI]

CoRR, 2024

Binary Hypothesis Testing for Softmax Models and Leverage Score Models.

[BibT_eX]

[DOI]

Yuzhou Gu

CoRR, 2024

Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers.

[BibT_eX]

[DOI]

CoRR, 2024

Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyond.

[BibT_eX]

[DOI]

CoRR, 2024

How to Inverting the Leverage Score Distribution?

[BibT_eX]

[DOI]

CoRR, 2024

Attention is Naturally Sparse with Gaussian Distributed Input.

[BibT_eX]

[DOI]

CoRR, 2024

Fourier Circuits in Neural Networks: Unlocking the Potential of Large Language Models in Mathematical Reasoning and Modular Arithmetic.

[BibT_eX]

[DOI]

CoRR, 2024

Quantum Speedup for Spectral Approximation of Kronecker Products.

[BibT_eX]

[DOI]

CoRR, 2024

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models.

[BibT_eX]

[DOI]

Josh Alman

CoRR, 2024

Enhancing Stochastic Gradient Descent: A Unified Framework and Novel Acceleration Methods for Faster Convergence.

[BibT_eX]

[DOI]

CoRR, 2024

Convex Minimization with Integer Minima in Õ(n4) Time.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis.

[BibT_eX]

[DOI]

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models.

[BibT_eX]

[DOI]

Jan van den Brand

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Twelfth International Conference on Learning Representations, 2024

A Sublinear Adversarial Training Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Twelfth International Conference on Learning Representations, 2024

How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation.

[BibT_eX]

[DOI]

Josh Alman

Proceedings of the Twelfth International Conference on Learning Representations, 2024

A General Algorithm for Solving Rank-one Matrix Sensing.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2024

Solving Attention Kernel Regression Problem via Pre-conditioner.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2024

Fast Dynamic Sampling for Determinantal Point Processes.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2024

How to Protect Copyright Data in Optimization of Large Language Models?

[BibT_eX]

[DOI]

Timothy Chu

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

Local Convergence of Approximate Newton Method for Two Layer Nonlinear Regression.

[BibT_eX]

[DOI]

CoRR, 2023

Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters.

[BibT_eX]

[DOI]

CoRR, 2023

One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Space.

[BibT_eX]

[DOI]

CoRR, 2023

A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformer.

[BibT_eX]

[DOI]

CoRR, 2023

The Expressibility of Polynomial based Attention Scheme.

[BibT_eX]

[DOI]

Guangyi Xu

CoRR, 2023

Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weights.

[BibT_eX]

[DOI]

CoRR, 2023

Superiority of Softmax: Unveiling the Performance Edge Over Linear Attention.

[BibT_eX]

[DOI]

CoRR, 2023

An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descent.

[BibT_eX]

[DOI]

CoRR, 2023

Fine-tune Language Models to Approximate Unbiased In-context Learning.

[BibT_eX]

[DOI]

Timothy Chu

CoRR, 2023

A Unified Scheme of ResNet and Softmax.

[BibT_eX]

[DOI]

Weixin Wang

CoRR, 2023

Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?

[BibT_eX]

[DOI]

Baocheng Sun

CoRR, 2023

A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time.

[BibT_eX]

[DOI]

CoRR, 2023

Streaming Semidefinite Programs: O(√n) Passes, Small Space and Fast Runtime.

[BibT_eX]

[DOI]

Mingquan Ye

CoRR, 2023

Clustered Linear Contextual Bandits with Knapsacks.

[BibT_eX]

[DOI]

Michalis Mamakos

CoRR, 2023

GradientCoin: A Peer-to-Peer Decentralized Large Language Models.

[BibT_eX]

[DOI]

CoRR, 2023

Convergence of Two-Layer Regression with Nonlinear Units.

[BibT_eX]

[DOI]

Shenghao Xie

CoRR, 2023

Zero-th Order Algorithm for Softmax Attention Optimization.

[BibT_eX]

[DOI]

CoRR, 2023

Fast Quantum Algorithm for Attention Computation.

[BibT_eX]

[DOI]

CoRR, 2023

A Nearly-Linear Time Algorithm for Structured Support Vector Machines.

[BibT_eX]

[DOI]

Yuzhou Gu

CoRR, 2023

Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification.

[BibT_eX]

[DOI]

Yuanyuan Yang

CoRR, 2023

In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trick.

[BibT_eX]

[DOI]

Shenghao Xie

CoRR, 2023

H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models.

[BibT_eX]

[DOI]

CoRR, 2023

Efficient Algorithm for Solving Hyperbolic Programs.

[BibT_eX]

[DOI]

CoRR, 2023

Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation.

[BibT_eX]

[DOI]

CoRR, 2023

Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basis.

[BibT_eX]

[DOI]

CoRR, 2023

Sparse Convolution for Approximate Sparse Instance.

[BibT_eX]

[DOI]

Xiaoxiao Li

Guangyi Zhang

CoRR, 2023

A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models.

[BibT_eX]

[DOI]

Ritwik Sinha

CoRR, 2023

Faster Robust Tensor Power Method for Arbitrary Order.

[BibT_eX]

[DOI]

CoRR, 2023

Federated Empirical Risk Minimization via Second-Order Method.

[BibT_eX]

[DOI]

Song Bian

CoRR, 2023

Fast Submodular Function Maximization.

[BibT_eX]

[DOI]

Yitan Wang

CoRR, 2023

Fast and Efficient Matching Algorithm with Deadline Instances.

[BibT_eX]

[DOI]

Weixin Wang

Chenbo Yin

CoRR, 2023

Efficient Asynchronize Stochastic Gradient Algorithm with Structured Data.

[BibT_eX]

[DOI]

Mingquan Ye

CoRR, 2023

Differentially Private Attention Computation.

[BibT_eX]

[DOI]

Xin Yang

CoRR, 2023

An Iterative Algorithm for Rescaled Hyperbolic Functions Regression.

[BibT_eX]

[DOI]

CoRR, 2023

The Closeness of In-Context Learning and Weight Shifting for Softmax Regression.

[BibT_eX]

[DOI]

CoRR, 2023

Attention Scheme Inspired Softmax Regression.

[BibT_eX]

[DOI]

Zhihang Li

CoRR, 2023

Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension.

[BibT_eX]

[DOI]

Sridhar Mahadevan

CoRR, 2023

Convex Minimization with Integer Minima in Õ(n4) Time.

[BibT_eX]

[DOI]

CoRR, 2023

Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models.

[BibT_eX]

[DOI]

Jan van den Brand

CoRR, 2023

An Over-parameterized Exponential Regression.

[BibT_eX]

[DOI]

Sridhar Mahadevan

CoRR, 2023

Solving Regularized Exp, Cosh and Sinh Regression Problems.

[BibT_eX]

[DOI]

Zhihang Li

CoRR, 2023

An Improved Sample Complexity for Rank-1 Matrix Sensing.

[BibT_eX]

[DOI]

Zhihang Li

CoRR, 2023

A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph.

[BibT_eX]

[DOI]

CoRR, 2023

Streaming Kernel PCA Algorithm With Small Space.

[BibT_eX]

[DOI]

CoRR, 2023

Faster Sinkhorn's Algorithm with Small Treewidth.

[BibT_eX]

[DOI]

CoRR, 2023

Super-resolution and Robust Sparse Continuous Fourier Transform in Any Constant Dimension: Nearly Linear Time and Sample Complexity.

[BibT_eX]

[DOI]

Yaonan Jin

Daogao Liu

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understanding.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Fast Attention Requires Bounded Entries.

[BibT_eX]

[DOI]

Josh Alman

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Federated Adversarial Learning: A Framework with Convergence Analysis.

[BibT_eX]

[DOI]

Xiaoxiao Li

Jiaming Yang

Proceedings of the International Conference on Machine Learning, 2023

A Nearly-Optimal Bound for Fast Regression with ℓ∞ Guarantee.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Space-Efficient Interior Point Method, with Applications to Linear Programming and Maximum Weight Bipartite Matching.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Quartic Samples Suffice for Fourier Interpolation.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Online Adaptive Mahalanobis Distance Estimation.

[BibT_eX]

[DOI]

Aravind Reddy

Proceedings of the IEEE International Conference on Big Data, 2023

Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Conference on Big Data, 2023

Solving Tensor Low Cycle Rank Approximation.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Conference on Big Data, 2023

A Tale of Two Efficient Value Iteration Algorithms for Solving Linear MDPs with Large Action Space.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2023

An Online and Unified Algorithm for Projection Matrix Vector Multiplication with Application to Empirical Risk Minimization.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2023

Smoothed Online Combinatorial Optimization Using Imperfect Predictions.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

An improved quantum-inspired algorithm for linear regression.

[BibT_eX]

[DOI]

András Gilyén

Ewin Tang

Quantum, 2022

Differentially Oblivious Relational Database Operators.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2022

Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Adore: Differentially Oblivious Relational Database Operators.

[BibT_eX]

[DOI]

CoRR, 2022

A Faster k-means++ Algorithm.

[BibT_eX]

[DOI]

CoRR, 2022

Dynamic Kernel Sparsifiers.

[BibT_eX]

[DOI]

CoRR, 2022

Faster Algorithm for Structured John Ellipsoid Computation.

[BibT_eX]

[DOI]

CoRR, 2022

A Faster Small Treewidth SDP Solver.

[BibT_eX]

[DOI]

Yuzhou Gu

CoRR, 2022

Discrepancy Minimization in Input-Sparsity Time.

[BibT_eX]

[DOI]

Omri Weinstein

CoRR, 2022

Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance.

[BibT_eX]

[DOI]

CoRR, 2022

A Nearly Optimal Size Coreset Algorithm with Nearly Linear Time.

[BibT_eX]

[DOI]

CoRR, 2022

An O(k log n) Time Fourier Set Query Algorithm.

[BibT_eX]

[DOI]

Baocheng Sun

CoRR, 2022

Training Overparametrized Neural Networks in Sublinear Time.

[BibT_eX]

[DOI]

CoRR, 2022

Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory.

[BibT_eX]

[DOI]

CoRR, 2022

Sublinear Time Algorithm for Online Weighted Bipartite Matching.

[BibT_eX]

[DOI]

CoRR, 2022

Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structures.

[BibT_eX]

[DOI]

CoRR, 2022

Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction.

[BibT_eX]

[DOI]

CoRR, 2022

Speeding Up Sparsification using Inner Product Search Data Structures.

[BibT_eX]

[DOI]

CoRR, 2022

A Dynamic Fast Gaussian Transform.

[BibT_eX]

[DOI]

CoRR, 2022

Dynamic Tensor Product Regression.

[BibT_eX]

[DOI]

Aravind Reddy

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Fast Distance Oracles for Any Symmetric Norm.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Symmetric Sparse Boolean Matrix Factorization and Applications.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Bounding the Width of Neural Networks via Coupled Initialization A Worst Case Analysis.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Perfectly Balanced: Improving Transfer and Robustness of Supervised Contrastive Learning.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models.

[BibT_eX]

[DOI]

Proceedings of the Tenth International Conference on Learning Representations, 2022

Solving SDP Faster: A Robust IPM Framework and Efficient Implementation.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Conference on Big Data, 2022

A Convergence Theory for Federated Average: Beyond Smoothness.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Conference on Big Data, 2022

Hyperbolic Concentration, Anti-Concentration, and Discrepancy.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2022

Fast Graph Neural Tangent Kernel via Kronecker Sketching.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

Solving Linear Programs in the Current Matrix Multiplication Time.

[BibT_eX]

[DOI]

Michael B. Cohen

J. ACM, 2021

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

On Convergence of Federated Averaging Langevin Dynamics.

[BibT_eX]

[DOI]

CoRR, 2021

Online MAP Inference and Learning for Nonsymmetric Determinantal Point Processes.

[BibT_eX]

[DOI]

CoRR, 2021

An Interpretable Graph Generative Model with Heterophily.

[BibT_eX]

[DOI]

CoRR, 2021

Scatterbrain: Unifying Sparse and Low-rank Attention Approximation.

[BibT_eX]

[DOI]

CoRR, 2021

Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing.

[BibT_eX]

[DOI]

CoRR, 2021

FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysis.

[BibT_eX]

[DOI]

CoRR, 2021

Symmetric Boolean Factor Analysis with Applications to InstaHide.

[BibT_eX]

[DOI]

CoRR, 2021

Solving Tall Dense SDPs in the Current Matrix Multiplication Time.

[BibT_eX]

[DOI]

CoRR, 2021

When is particle filtering efficient for planning in partially observed linear dynamical systems?

[BibT_eX]

[DOI]

Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, 2021

A faster algorithm for solving general LPs.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances.

[BibT_eX]

[DOI]

Jan van den Brand

Yang P. Liu

Thatchaphol Saranurak

Aaron Sidford

Di Wang

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Does Preprocessing Help Training Over-parameterized Neural Networks?

[BibT_eX]

[DOI]

Shuo Yang

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Evaluating Gradient Inversion Attacks and Defenses in Federated Learning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Scatterbrain: Unifying Sparse and Low-rank Attention.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Training (Overparametrized) Neural Networks in Near-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Analysis.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Oblivious Sketching-based Central Path Method for Linear Programming.

[BibT_eX]

[DOI]

Zheng Yu

Proceedings of the 38th International Conference on Machine Learning, 2021

Fast Sketching of Polynomial Kernels of Polynomial Degree.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

MONGOOSE: A Learnable LSH Framework for Efficient Neural Network Training.

[BibT_eX]

[DOI]

Christopher Ré

Proceedings of the 9th International Conference on Learning Representations, 2021

On InstaHide, Phase Retrieval, and Sparse Matrix Factorization.

[BibT_eX]

[DOI]

Proceedings of the 9th International Conference on Learning Representations, 2021

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

InstaHide's Sample Complexity When Mixing Two Private Images.

[BibT_eX]

[DOI]

CoRR, 2020

On InstaHide, Phase Retrieval, and Sparse Matrix Factorization.

[BibT_eX]

[DOI]

Sitan Chen

Danyang Zhuo

CoRR, 2020

MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery.

[BibT_eX]

[DOI]

CoRR, 2020

Hyperbolic Polynomials I : Concentration and Discrepancy.

[BibT_eX]

[DOI]

CoRR, 2020

When is Particle Filtering Efficient for POMDP Sequential Planning?

[BibT_eX]

[DOI]

CoRR, 2020

A robust multi-dimensional sparse Fourier transform in the continuous setting.

[BibT_eX]

[DOI]

Yaonan Jin

Daogao Liu

CoRR, 2020

Average Case Column Subset Selection for Entrywise 𝓁1-Norm Loss.

[BibT_eX]

[DOI]

CoRR, 2020

Faster Dynamic Matrix Inverse for Faster LPs.

[BibT_eX]

[DOI]

CoRR, 2020

Privacy-preserving Learning via Deep Net Pruning.

[BibT_eX]

[DOI]

CoRR, 2020

An improved cutting plane method for convex optimization, convex-concave games, and its applications.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Learning mixtures of linear regressions in subexponential time via Fourier moments.

[BibT_eX]

[DOI]

Sitan Chen

Jerry Li

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Solving tall dense linear programs in nearly linear time.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Reducing approximate Longest Common Subsequence to approximate Edit Distance.

[BibT_eX]

[DOI]

Aviad Rubinstein

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Generalized Leverage Score Sampling for Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Meta-learning for Mixed Linear Regression.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

InstaHide: Instance-hiding Schemes for Private Distributed Learning.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

A Faster Interior Point Method for Semidefinite Programming.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Aaron Sidford

Di Wang

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Algorithms and Hardness for Linear Algebra on Geometric Graphs.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

TextHide: Tackling Data Privacy for Language Understanding Tasks.

[BibT_eX]

[DOI]

Proceedings of the Findings of the Association for Computational Linguistics: EMNLP 2020, 2020

Sketching Transformed Matrices with Applications to Natural Language Processing.

[BibT_eX]

[DOI]

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

Non-Convex Matrix Completion and Related Problems via Strong Duality.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2019

Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound.

[BibT_eX]

[DOI]

Xin Yang

CoRR, 2019

Efficient Model-free Reinforcement Learning in Metric Spaces.

[BibT_eX]

[DOI]

Wen Sun

CoRR, 2019

Stronger L2/L2 Compressed Sensing; Without Iterating.

[BibT_eX]

[DOI]

Vasileios Nakos

CoRR, 2019

Four Deviations Suffice for Rank 1 Matrices.

[BibT_eX]

[DOI]

Rasmus Kyng

Kyle Luh

CoRR, 2019

Stronger l2/l2 compressed sensing; without iterating.

[BibT_eX]

[DOI]

Vasileios Nakos

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Provable Non-linear Inductive Matrix Completion.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Average Case Column Subset Selection for Entrywise 퓁1-Norm Loss.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Towards a Zero-One Law for Column Subset Selection.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Efficient Symmetric Norm Regression via Linear Sketching.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Total Least Squares Regression in Input Sparsity Time.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Optimal Sketching for Kronecker Product Regression and Low Rank Approximation.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

On the Convergence Rate of Training Recurrent Neural Networks.

[BibT_eX]

[DOI]

Zeyuan Allen-Zhu

Yuanzhi Li

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

A Convergence Theory for Deep Learning via Over-Parameterization.

[BibT_eX]

[DOI]

Zeyuan Allen-Zhu

Yuanzhi Li

Proceedings of the 36th International Conference on Machine Learning, 2019

The Limitations of Adversarial Training and the Blind-Spot Attack.

[BibT_eX]

[DOI]

Proceedings of the 7th International Conference on Learning Representations, 2019

Approximation Algorithms for LCS and LIS with Truly Improved Running Times.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless.

[BibT_eX]

[DOI]

Vasileios Nakos

Zhengyu Wang

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Solving Empirical Risk Minimization in the Current Matrix Multiplication Time.

[BibT_eX]

[DOI]

Qiuyi Zhang

Proceedings of the Conference on Learning Theory, 2019

Towards a Theoretical Understanding of Hashing-Based Neural Nets.

[BibT_eX]

[DOI]

Yibo Lin

Lin F. Yang

Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

2018

Topic Modeling in Online Social Media, User Features and Social Networks for.

[BibT_eX]

[DOI]

Bo Hu

Priya Ranjan Sinha Mahapatra

Martin Ester

Proceedings of the Encyclopedia of Social Network Analysis and Mining, 2nd Edition, 2018

Optimizing squares covering a set of points.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Relative Error Tensor Low Rank Approximation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities.

[BibT_eX]

[DOI]

Santosh S. Vempala

CoRR, 2018

Towards a Zero-One Law for Entrywise Low Rank Approximation.

[BibT_eX]

[DOI]

CoRR, 2018

Nonlinear Inductive Matrix Completion based on One-layer Neural Networks.

[BibT_eX]

[DOI]

CoRR, 2018

Sensitivity Sampling Over Dynamic Geometric Data Streams with Applications to k-Clustering.

[BibT_eX]

[DOI]

Lin F. Yang

CoRR, 2018

A matrix expander Chernoff bound.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Learning Long Term Dependencies via Fourier Recurrent Units.

[BibT_eX]

[DOI]

Proceedings of the 35th International Conference on Machine Learning, 2018

Towards Fast Computation of Certified Robustness for ReLU Networks.

[BibT_eX]

[DOI]

Proceedings of the 35th International Conference on Machine Learning, 2018

A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees.

[BibT_eX]

[DOI]

Rasmus Kyng

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Parallel Graph Connectivity in Log Diameter Rounds.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Stochastic Multi-armed Bandits in Constant Space.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018

Sketching for Kronecker Product Regression and P-splines.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018

2017

Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels.

[BibT_eX]

[DOI]

Kai Zhong

Inderjit S. Dhillon

CoRR, 2017

Fast Regression with an $\ell_\infty$ Guarantee.

[BibT_eX]

[DOI]

Eric Price

CoRR, 2017

Low rank approximation with entrywise l1-norm error.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Recovery Guarantees for One-hidden-layer Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Machine Learning, 2017

Fast Regression with an $ell_infty$ Guarantee.

[BibT_eX]

[DOI]

Eric Price

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

The p-Center Problem in Tree Networks Revisited.

[BibT_eX]

[DOI]

Aritra Banik

Sandip Das

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Weighted low rank approximations with provable guarantees.

[BibT_eX]

[DOI]

Ilya P. Razenshteyn

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Sublinear Time Orthogonal Tensor Decomposition.

[BibT_eX]

[DOI]

Huan Zhang

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Maximum Sustainable Yield Problem for Robot Foraging and Construction System.

[BibT_eX]

[DOI]

Ruohan Zhang

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016

Fourier-Sparse Interpolation without a Frequency Gap.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks.

[BibT_eX]

[DOI]

Binay Bhattacharya

Discret. Appl. Math., 2015

A Robust Sparse Fourier Transform in the Continuous Setting.

[BibT_eX]

[DOI]

Eric Price

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Novel power grid reduction method based on L1 regularization.

[BibT_eX]

[DOI]

Constantine Caramanis

Proceedings of the 52nd Annual Design Automation Conference, 2015

Global Policy Construction in Modular Reinforcement Learning.

[BibT_eX]

[DOI]

Ruohan Zhang

Dana H. Ballard

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014

Topic Modeling in Online Social Media, User Features, and Social Networks for.

[BibT_eX]

[DOI]

Bo Hu

Martin Ester

Encyclopedia of Social Network Analysis and Mining, 2014

Batch Codes through Dense Graphs without Short Cycles.

[BibT_eX]

[DOI]

Alexandros G. Dimakis

Anna Gál

Ankit Singh Rawat

Electron. Colloquium Comput. Complex., 2014

A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree Network.

[BibT_eX]

[DOI]

Algorithmica, 2014

Improved Minmax Regret 1-Center Algorithms for Cactus Networks with c Cycles.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Back-Up 2-Center on a Path/Tree/Cycle/Unicycle.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 20th International Conference, 2014

Optimizing Squares Covering a Set of Points.

[BibT_eX]

[DOI]

Sandip Das

Priya Ranjan Sinha Mahapatra

Proceedings of the Combinatorial Optimization and Applications, 2014

Probabilistic recharging model in uncertain environments.

[BibT_eX]

[DOI]

Wen Sun

Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2014

2013

Sustainable robot foraging: Adaptive fine-grained multi-robot task allocation for maximum sustainable yield of biological resources.

[BibT_eX]

[DOI]

Richard T. Vaughan

Proceedings of the 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2013

Graphical Model-Based Learning in High Dimensional Feature Spaces.

[BibT_eX]

[DOI]

Yuke Zhu

Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013

2012

Computing Minmax Regret 1-Median on a Tree Network with Positive/Negative Vertex Weights.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

User Features and Social Networks for Topic Modeling in Online Social Media.

[BibT_eX]

[DOI]

Bo Hu

Martin Ester

Proceedings of the International Conference on Advances in Social Networks Analysis and Mining, 2012

MO-LOST: adaptive ant trail untangling in multi-objective multi-colony robot foraging.

[BibT_eX]

[DOI]