國立虎尾科技大學 |

Continuous LWE and Its Applications.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Continuous LWE and Its Applications./
Author:	Song, Min Jae.
Description:	1 online resource (128 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 85-01, Section: B.
Contained By:	Dissertations Abstracts International85-01B.
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9798379773878

Continuous LWE and Its Applications.
Song, Min Jae.

Continuous LWE and Its Applications. - 1 online resource (128 pages)

Source: Dissertations Abstracts International, Volume: 85-01, Section: B.

Thesis (Ph.D.)--New York University, 2023.

Includes bibliographical references

Efficiently extracting useful information from high-dimensional data is a major challenge in machine learning (ML). Oftentimes, the challenge comes not from a lack of data, but from its high dimensionality and computational constraints. For instance, when data exhibits a low-dimensional structure, one could in principle exhaustively search over all candidate structures, and obtain estimators with strong statistical guarantees. Of course, such brute-force approach is prohibitively expensive in high dimensions, necessitating the need for computationally efficient alternatives. When our problem, however, persistently eludes efficient algorithms, we may find ourselves asking the following perplexing question: is the failure due to our lack of algorithmic ingenuity or is the problem just too hard? Is there a gap between what we can achieve statistically and what we can achieve computationally?This thesis is one attempt at answering such questions on the computational complexity of statistical inference. We provide results of both positive and negative nature on the complexity of canonical learning problems by establishing connections between ML and lattice-based cryptography. The continuous learning with errors (CLWE) problem, which can be seen as a continuous variant of the well-known learning with errors (LWE) problem from lattice-based cryptography, lies at the center of this fruitful connection.In the first part of this thesis, we show that CLWE enjoys essentially the same average-case hardness guarantees as LWE. This result has several important applications. For example, it shows that estimating the density of high-dimensional Gaussian mixtures is computationally hard, and gives rise to "backdoored" Gaussian distributions that can be used to plant undetectable backdoors in ML models and construct novel public-key encryption schemes.Next, we focus on the ``backdoored'' Gaussian distributions, which we refer to as Gaussian pancakes, and the problem of distinguishing these distributions from the standard Gaussian. We provide evidence for the hardness of this distinguishing problem based on a reduction from CLWE and lower bounds against restricted classes of algorithms, such as algorithms that compute low-degree polynomials of the observations.Finally, we end on a positive note by showing that the Lenstra-Lenstra-Lov\\'asz (LLL) algorithm, commonly used in computational number theory and lattice-based cryptography, has surprising implications for noiseless inference. In particular, we show that LLL solves both CLWE and Gaussian pancakes in the noiseless setting, showing that noise is necessary for hardness. This strengthens the analogy between LWE and CLWE since LWE is also easy in the noiseless case. A minor modification of our LLL-based method in fact surpasses sum-of-squares and approximate message passing algorithms, two methods often conjectured to be optimal among polynomial-time algorithms, on other noiseless problems such as Gaussian clustering and Gaussian phase retrieval.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798379773878Subjects--Topical Terms:

573171
Computer science.
Subjects--Index Terms:

Computational complexityIndex Terms--Genre/Form:

554714
Electronic books.

Continuous LWE and Its Applications.
LDR:04390ntm a22003977 4500 001 1143740
005 20240517104940.5
006 m o d
007 cr mn ---uuuuu
008 250605s2023 xx obm 000 0 eng d
020 $a 9798379773878
035 $a (MiAaPQ)AAI30314941
035 $a AAI30314941
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Song, Min Jae. $3 1468523
245 1 0 $a Continuous LWE and Its Applications.
264 0 $c 2023
300 $a 1 online resource (128 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 85-01, Section: B.
500 $a Advisor: Bruna, Joan;Regev, Oded.
502 $a Thesis (Ph.D.)--New York University, 2023.
504 $a Includes bibliographical references
520 $a Efficiently extracting useful information from high-dimensional data is a major challenge in machine learning (ML). Oftentimes, the challenge comes not from a lack of data, but from its high dimensionality and computational constraints. For instance, when data exhibits a low-dimensional structure, one could in principle exhaustively search over all candidate structures, and obtain estimators with strong statistical guarantees. Of course, such brute-force approach is prohibitively expensive in high dimensions, necessitating the need for computationally efficient alternatives. When our problem, however, persistently eludes efficient algorithms, we may find ourselves asking the following perplexing question: is the failure due to our lack of algorithmic ingenuity or is the problem just too hard? Is there a gap between what we can achieve statistically and what we can achieve computationally?This thesis is one attempt at answering such questions on the computational complexity of statistical inference. We provide results of both positive and negative nature on the complexity of canonical learning problems by establishing connections between ML and lattice-based cryptography. The continuous learning with errors (CLWE) problem, which can be seen as a continuous variant of the well-known learning with errors (LWE) problem from lattice-based cryptography, lies at the center of this fruitful connection.In the first part of this thesis, we show that CLWE enjoys essentially the same average-case hardness guarantees as LWE. This result has several important applications. For example, it shows that estimating the density of high-dimensional Gaussian mixtures is computationally hard, and gives rise to "backdoored" Gaussian distributions that can be used to plant undetectable backdoors in ML models and construct novel public-key encryption schemes.Next, we focus on the ``backdoored'' Gaussian distributions, which we refer to as Gaussian pancakes, and the problem of distinguishing these distributions from the standard Gaussian. We provide evidence for the hardness of this distinguishing problem based on a reduction from CLWE and lower bounds against restricted classes of algorithms, such as algorithms that compute low-degree polynomials of the observations.Finally, we end on a positive note by showing that the Lenstra-Lenstra-Lov\\'asz (LLL) algorithm, commonly used in computational number theory and lattice-based cryptography, has surprising implications for noiseless inference. In particular, we show that LLL solves both CLWE and Gaussian pancakes in the noiseless setting, showing that noise is necessary for hardness. This strengthens the analogy between LWE and CLWE since LWE is also easy in the noiseless case. A minor modification of our LLL-based method in fact surpasses sum-of-squares and approximate message passing algorithms, two methods often conjectured to be optimal among polynomial-time algorithms, on other noiseless problems such as Gaussian clustering and Gaussian phase retrieval.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
650 4 $a Information technology. $3 559429
653 $a Computational complexity
653 $a Deep learning
653 $a Hypothesis testing
653 $a Lattice-based cryptography
653 $a Machine learning
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0800
690 $a 0489
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a New York University. $b Computer Science. $3 1184382
773 0 $t Dissertations Abstracts International $g 85-01B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30314941 $z click for full text (PQDT)