TY - GEN
T1 - New algorithms for learning in presence of errors
AU - Arora, Sanjeev
AU - Ge, Rong
N1 - Funding Information:
Research supported by NSF Grants CCF-0832797, 0830673, and 0528414.
PY - 2011
Y1 - 2011
N2 - We give new algorithms for a variety of randomly-generated instances of computational problems using a linearization technique that reduces to solving a system of linear equations. These algorithms are derived in the context of learning with structured noise, a notion introduced in this paper. This notion is best illustrated with the learning parities with noise (LPN) problem -well-studied in learning theory and cryptography. In the standard version, we have access to an oracle that, each time we press a button, returns a random vector together with a bit that was computed as a•u+η, where is a secret vector, and is a noise bit that is 1 with some probability p. Say p = 1/3. The goal is to recover u. This task is conjectured to be intractable. In the structured noise setting we introduce a slight (?) variation of the model: upon pressing a button, we receive (say) 10 random vectors , and corresponding bits b 1, b 2, ..., b 10, of which at most 3 are noisy. The oracle may arbitrarily decide which of the 10 bits to make noisy. We exhibit a polynomial-time algorithm to recover the secret vector u given such an oracle. We think this structured noise model may be of independent interest in machine learning. We discuss generalizations of our result, including learning with more general noise patterns. We also give the first nontrivial algorithms for two problems, which we show fit in our structured noise framework. We give a slightly subexponential algorithm for the well-known learning with errors (LWE) problem over introduced by Regev for cryptographic uses. Our algorithm works for the case when the gaussian noise is small; which was an open problem. Our result also clarifies why existing hardness results fail at this particular noise rate. We also give polynomial-time algorithms for learning the MAJORITY OF PARITIES function of Applebaum et al. for certain parameter values. This function is a special case of Goldreich's pseudorandom generator. The full version is available at http://www.eccc.uni-trier.de/report/ 2010/066/ .
AB - We give new algorithms for a variety of randomly-generated instances of computational problems using a linearization technique that reduces to solving a system of linear equations. These algorithms are derived in the context of learning with structured noise, a notion introduced in this paper. This notion is best illustrated with the learning parities with noise (LPN) problem -well-studied in learning theory and cryptography. In the standard version, we have access to an oracle that, each time we press a button, returns a random vector together with a bit that was computed as a•u+η, where is a secret vector, and is a noise bit that is 1 with some probability p. Say p = 1/3. The goal is to recover u. This task is conjectured to be intractable. In the structured noise setting we introduce a slight (?) variation of the model: upon pressing a button, we receive (say) 10 random vectors , and corresponding bits b 1, b 2, ..., b 10, of which at most 3 are noisy. The oracle may arbitrarily decide which of the 10 bits to make noisy. We exhibit a polynomial-time algorithm to recover the secret vector u given such an oracle. We think this structured noise model may be of independent interest in machine learning. We discuss generalizations of our result, including learning with more general noise patterns. We also give the first nontrivial algorithms for two problems, which we show fit in our structured noise framework. We give a slightly subexponential algorithm for the well-known learning with errors (LWE) problem over introduced by Regev for cryptographic uses. Our algorithm works for the case when the gaussian noise is small; which was an open problem. Our result also clarifies why existing hardness results fail at this particular noise rate. We also give polynomial-time algorithms for learning the MAJORITY OF PARITIES function of Applebaum et al. for certain parameter values. This function is a special case of Goldreich's pseudorandom generator. The full version is available at http://www.eccc.uni-trier.de/report/ 2010/066/ .
UR - http://www.scopus.com/inward/record.url?scp=79960014155&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960014155&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22006-7_34
DO - 10.1007/978-3-642-22006-7_34
M3 - Conference contribution
AN - SCOPUS:79960014155
SN - 9783642220050
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 403
EP - 415
BT - Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
T2 - 38th International Colloquium on Automata, Languages and Programming, ICALP 2011
Y2 - 4 July 2011 through 8 July 2011
ER -