Reduces learning periodic neural networks to lattice problems, proving hardness under cryptographic assumptions.
problem Learning single periodic neurons in noisy environments.
method Reduction to worst-case lattice problems, using LLL algorithm.
result Polynomial-time algorithms for learning these functions are hard under cryptographic assumptions.
Hard to estimate L2-accurate scores without strong assumptions.
problem Estimating the score of unknown data distributions accurately.
method Reduction to generating samples and leveraging lattice-based cryptography hardness.
result Score estimation is computationally hard even with polynomial sample complexity.
Paper tackles efficient HMM learning with conditional samples.
problem Cryptographic hardness in learning HMMs from i.i.d. samples.
method Interactive access model, polynomial-time algorithms for conditional probabilities and latent low rank structures.
result Efficient algorithms for HMM learning in both exact and approximate conditional settings.
In our recent work (Bubeck, Price, Razenshteyn, arXiv:1805.10204) we argued that adversarial examples in machine learning might be due to an inherent computational hardness of the problem. More precisely, we constructed a binary classification task for which (i) a robust classifier exists; yet no non-trivial accuracy c…
This paper strengthens the computational separation between multimodal and unimodal learning, showing unimodal learning is hard on typical instances.
problem Theoretical justification for empirical success of multimodal machine learning.
method Introduced a stronger average-case computational separation between unimodal and multimodal learning.
result For typical instances, unimodal learning is computationally hard, while multimodal learning is easy.
Hardness proven for learning neural networks with polynomial size and Gaussian inputs.
problem Learning one hidden layer ReLU neural networks with polynomial size and Gaussian inputs.
method Based on the hardness of the Continuous Learning with Errors (CLWE) problem.
result Hardness of learning neural networks is proven under standard cryptographic assumptions.
Quantum computers outperform classical methods in density modeling.
problem Density modeling with quantum computers.
method Quantum-classical separation for density modeling.
result Quantum computers offer a super-polynomial advantage over classical algorithms for density modeling.
We continue the study of statistical/computational tradeoffs in learning robust classifiers, following the recent work of Bubeck, Lee, Price and Razenshteyn who showed examples of classification tasks where (a) an efficient robust classifier exists, in the small-perturbation regime; (b) a non-robust classifier can be l…
Over recent years, devising classification algorithms that are robust to adversarial perturbations has emerged as a challenging problem. In particular, deep neural nets (DNNs) seem to be susceptible to small imperceptible changes over test instances. However, the line of work in provable robustness, so far, has been fo…
Study learning from multiple thinkers providing step-by-step solutions to problems.
problem Learning from multiple, possibly different, thinkers providing step-by-step solutions to problems.
method Active learning algorithm that uses CoT data from multiple thinkers and end-result data.
result Learning can be hard from CoT supervision provided by two or a few different thinkers, but a generic algorithm can learn efficiently.
Paper investigates hardness of learning neural networks under manifold hypothesis.
problem Hardness of learning neural networks under the manifold hypothesis.
method Extending proofs of hardness in the SQ and cryptographic settings to the geometric setting.
result Learning is hard under input manifolds of bounded curvature but learnable with additional assumptions on manifold volume.
We discuss some applications of 3-manifold topology to cryptography. In particular, we propose a public-key and a symmetric-key cryptographic scheme based on the Thurston norm on the first cohomology of hyperbolic manifolds.
SOTERIA optimizes neural networks for secure inference with minimal overhead.
problem Protecting user privacy in ML-as-a-service models with low overhead.
method Neural architecture search with dual objectives of accuracy and cryptographic efficiency.
result SOTERIA constructs efficient models for secure inference.
Privacy concern has been increasingly important in many machine learning (ML) problems. We study empirical risk minimization (ERM) problems under secure multi-party computation (MPC) frameworks. Main technical tools for MPC have been developed based on cryptography. One of limitations in current cryptographically priva…
Proves SQ lower bounds for learning two-hidden-layer neural networks.
problem Learning two-hidden-layer ReLU networks with Gaussian inputs.
method Refined lifting procedure to reduce Boolean PAC learning to Gaussian.
result Superpolynomial SQ lower bounds for Gaussian inputs.
Origami uses SGX enclaves and blinding to protect deep neural network inference privacy.
problem Protecting deep neural network inference privacy in machine learning services.
method Combines enclave execution, cryptographic blinding, and accelerator-based computation.
result Demonstrates improved privacy-preserving inference performance compared to prior work.
PHAZE framework uses zkML and hashing for fast, verifiable LHC trigger decisions.
problem Inefficient inference on large machine learning models for LHC trigger performance.
method Cryptographic techniques like hashing and zkML for low latency, certifiable inference.
result Achieves nanosecond-order latency for LHC triggers, enabling dynamic low-level triggers.
Study selective classification with halfspaces, achieving error bounds under Gaussian distributions.
problem Modeling relationships in subsets of data defined by selection rules.
method Sparse linear classifiers for subsets defined by halfspaces, focusing on Gaussian feature distributions.
result First PAC-learning algorithm for homogeneous halfspace selectors with error guarantee $\bigO*{\sqrt{\mathrm{opt}}}$.
Quantum crypto-economics models price risks in blockchain technology.
problem Quantum technology's potential to undermine blockchain security.
method Building financial models to price quantum risk in blockchain scenarios.
result Quantum crypto-economics models can assess and price quantum risks in blockchain.
Paper proposes scalable privacy-preserving DNN for industrial applications.
problem Data isolation and scalability issues in deep neural networks.
method Split computation graph into private and neutral server parts; use cryptographic techniques for private data.
result Demonstrates practicality of the proposed scalable privacy-preserving DNN.
Local regularization fails in transductive learning for some multiclass problems.
problem Whether local regularization can learn all transductive multiclass problems.
method Provided a negative answer by exhibiting a specific multiclass problem.
result Local regularization cannot learn all transductive multiclass problems.
Approach to verify neural network training integrity.
problem Poisoning attacks during neural network training.
method Use of cryptographic mechanisms to verify training integrity.
result Provable verification of neural network training integrity.
Framework certifies fairness of machine learning models interactively and privately.
problem Certifying fairness of machine learning models in privacy-preserving scenarios.
method Interactive test with cryptographic techniques for fairness certification.
result Empirical evaluation of fairness for various models and definitions.
Federated learning platform for drug discovery without sharing data.
problem Lack of secure collaboration in drug discovery.
method Industry-scale federated learning platform using cryptographic aggregation.
result Generated new scientific discoveries in drug discovery.
Boosting algorithm reduces error in noisy data.
problem Improving weak learners in the presence of Massart noise.
method First computationally efficient boosting algorithm for Massart noise.
result Achieves misclassification error arbitrarily close to Massart noise threshold.
CryptoNAS improves PI accuracy by 3.4% with 2.4x less latency.
problem Private inference on machine learning models with limited latency.
method Developed CryptoNAS, a novel NAS method for finding models that maximize accuracy within a ReLU budget.
result Improves accuracy by 3.4% and latency by 2.4x over state-of-the-art methods.
There are recent cryptographic protocols that are based on Multiple Simultaneous Conjugacy Problems in braid groups. We improve an algorithm, due to Sang Jin Lee and Eonkyung Lee, to solve these problems, by applying a method developed by the author and Nuno Franco, originally intended to solve the Conjugacy Search Pro…
Privacy is a major issue in learning from distributed data. Recently the cryptographic literature has provided several tools for this task. However, these tools either reduce the quality/accuracy of the learning algorithm---e.g., by adding noise---or they incur a high performance penalty and/or involve trusting externa…
Safe-House secures DeFi by limiting losses and enhancing security.
problem Ongoing hacks and security concerns in DeFi.
method Safe-House uses blockchain principles to secure asset movements.
result Safe-House limits maximum one-time loss to specified limits.
New findings suggest minimax optimality doesn't guarantee distribution learning for GANs.
problem Understanding when GANs can truly learn the underlying distribution.
method Using cryptographic assumptions and ReLU network generators, the paper shows that achieving minimax optimality is insufficient for distribution learning.
result Achieving minimax optimality is insufficient for distribution learning in the usual statistical sense.
AriaNN enables private deep learning with minimal interaction and reduced key sizes.
problem Private deep learning with minimal interaction and reduced key sizes.
method Semi-honest 2-party computation protocol with function secret sharing, optimized primitives for neural network operations.
result Efficient private comparison for ReLU operations with reduced key size and improved performance.
We discuss several uses of blockchain (and, more generally, distributed ledger) technologies outside of cryptocurrencies with a pragmatic view. We mostly focus on three areas: the role of coin economies for what we refer to as data malls (specialized data marketplaces); data provenance (a historical record of data and …
How to train a machine learning model while keeping the data private and secure? We present CodedPrivateML, a fast and scalable approach to this critical problem. CodedPrivateML keeps both the data and the model information-theoretically private, while allowing efficient parallelization of training across distributed w…
Advances in fractional analysis suggest a new way for the physics understanding of Riemann's conjecture. It asserts that, if s is a complex number, the non trivial zeros of zeta function in the gap [0,1], is characterized by . This conjecture can be understood as a consequence of 1/2-order fractional differential chara…
Post-quantum cryptography needed for blockchain security.
problem Quantum computers threaten traditional blockchain cryptography.
method Review of theoretical cryptography and quantum information theory.
result Post-quantum cryptography is essential for blockchain security.
We propose a new randomized ensemble technique with a provable security guarantee against black-box transfer attacks. Our proof constructs a new security problem for random binary classifiers which is easier to empirically verify and a reduction from the security of this new model to the security of the ensemble classi…
This study calculates the maximum error of a famous estimation method.
problem Estimating rare items not seen in a sample.
method Characterizes the maximal mean-squared error of the Good-Turing estimator.
result Characterizes the maximal mean-squared error of the Good-Turing estimator.
In the last decade, deep learning algorithms have become very popular thanks to the achieved performance in many machine learning and computer vision tasks. However, most of the deep learning architectures are vulnerable to so called adversarial examples. This questions the security of deep neural networks (DNN) for ma…
Proposes measuring fairness through multiple stakeholder-curated stress tests.
problem Limited power of rigid fairness metrics and lack of stakeholder involvement in fairness discussions.
method Shift focus from fairness metrics to stress tests curated by stakeholders.
result Machine's performance under multiple stress tests reflects fairness.
As neural networks revolutionize many applications, significant privacy conflicts between model users and providers emerge. The cryptography community developed a variety of techniques for secure computation to address such privacy issues. As generic techniques for secure computation are typically prohibitively ineffec…
Neural Networks (NN) have recently emerged as backbone of several sensitive applications like automobile, medical image, security, etc. NNs inherently offer Partial Fault Tolerance (PFT) in their architecture; however, the biased PFT of NNs can lead to severe consequences in applications like cryptography and security …
We present two new statistical machine learning methods designed to learn on fully homomorphic encrypted (FHE) data. The introduction of FHE schemes following Gentry (2009) opens up the prospect of privacy preserving statistical machine learning analysis and modelling of encrypted data without compromising security con…
Novel algorithm for privacy-preserving distributed learning in analog domain.
problem Privacy-preserving distributed learning over analog data.
method Proposes a novel algorithm for analog data, leveraging real/complex number representation and information-theoretic security metrics.
result Demonstrates a fundamental trade-off between privacy and accuracy in analog domain distributed learning.
Paper proves hardness of learning various complex models under local pseudorandom generators.
problem Hardness of learning various complex models.
method Existence of local pseudorandom generators.
result Proves hardness of learning shallow ReLU neural networks and other models.
This work connects hardness of approximation and learning.
problem Hardness of approximation and learnability in machine learning.
method Shows a single hardness property implying both approximation and learning hardness.
result Obtains new results on hardness of approximation and learnability of specific functions.
Study on hard Legendrian unknots using normal rulings.
problem Understanding the complexity of Legendrian unknots in knot theory.
method Using normal rulings to obstruct and construct hard unknot diagrams.
result Construction of infinitely many smoothly hard max-tb unknot diagrams with bounds on minimum possible writhe.
Moving between 3-manifold triangulations is NP-hard
problem Moving between two triangulations of a 3-manifold
method Showing that the number of bistellar moves and sparse degree-two edge collapses is NP-hard
result First NP-hardness result concerning moves between two triangulations of a 3-manifold
Hard instances, which require a long time for a specific algorithm to solve, help (1) analyze the algorithm for accelerating it and (2) build a good benchmark for evaluating the performance of algorithms. There exist several efforts for automatic generation of hard instances. For example, evolutionary algorithms have b…