We study the problem of agnostically learning halfspaces which is defined by a fixed but unknown distribution @math on @math . We define @math as the least error of a halfspace classifier for @math . A learner who can access @math has to return a hypothesis whose error is small compared to @math . Using the recently developed method of the author, Linial and Shalev-Shwartz we prove hardness of learning results under a natural assumption on the complexity of refuting random @math - @math formulas. We show that no efficient learning algorithm has non-trivial worst-case performance even under the guarantees that @math for arbitrarily small constant @math , and that @math is supported in @math . Namely, even under these favorable conditions its error must be @math for every @math . In particular, no efficient algorithm can achieve a constant approximation ratio. Under a stronger version of the assumption (where @math can be poly-logarithmic in @math ), we can take @math for arbitrarily small @math . Interestingly, this is even stronger than the best known lower bounds (Arora et. al. 1993, Feldamn et. al. 2006, Guruswami and Raghavendra 2006) for the case that the learner is restricted to return a halfspace classifier (i.e. proper learning).
When we restrict the algorithms to return a halfspace classifier, the problem of learning halfspaces is essentially equivalent @cite_64 to the computational problem of minimizing disagreements . In this problem we are given a sample @math , and the goal is to find a vector @math that minimizes the fraction of pairs with @math . The optimal fraction is called the error of the sample. As a standard" and basic computational problem, much is known about it. The problem have been shown @math -hard already in Karp's famous paper @cite_25 . Soon after the discovery of the PCP theorem, Arora, Babai, Stern and Sweedyk @cite_70 have shown that assuming that no quasi-polynomial time algorithm can solve @math -hard problems, there is no efficient algorithm with an approximation ratio of @math . Later on, the corresponding maximization problem was considered by several authors @cite_59 @cite_10 @cite_31 @cite_35 @cite_54 , culminating with Feldman, Gopalan, Khot and Ponnuswami @cite_49 who showed that assuming that no quasi-polynomial time algorithm can solve @math hard problems, no efficient algorithm can distinguish samples with error @math from samples with error @math .
@cite_35 @cite_64 @cite_70 @cite_54 @cite_59 @cite_49 @cite_31 @cite_10 @cite_25
2069278600 2153656574 2065923584 2001663593
We present a new efficient algorithm for the search version of the approximate Closest Vector Problem with Preprocessing (CVPP). Our algorithm achieves an approximation factor of O(n sqrt log n ), improving on the previous best of O(n^ 1.5 ) due to Lag arias, Lenstra, and Schnorr hkzbabai . We also show, somewhat surprisingly, that only O(n) vectors of preprocessing advice are sufficient to solve the problem (with the slightly worse approximation factor of O(n)). We remark that this still leaves a large gap with respect to the decisional version of CVPP, where the best known approximation factor is O(sqrt n log n ) due to Aharonov and Regev AharonovR04 . To achieve these results, we show a reduction to the same problem restricted to target points that are close to the lattice and a more efficient reduction to a harder problem, Bounded Distance Decoding with preprocessing (BDDP). Combining either reduction with the previous best-known algorithm for BDDP by Liu, Lyubashevsky, and Micciancio LiuLM06 gives our main result. In the setting of CVP without preprocessing, we also give a reduction from (1+eps)gamma approximate CVP to gamma approximate CVP where the target is at distance at most 1+1 eps times the minimum distance (the length of the shortest non-zero vector) which relies on the lattice sparsification techniques of Dadush and Kun DadushK13 . As our final and most technical contribution, we present a substantially more efficient variant of the LLM algorithm (both in terms of run-time and amount of preprocessing advice), and via an improved analysis, show that it can decode up to a distance proportional to the reciprocal of the smoothing parameter of the dual lattice MR04 . We show that this is never smaller than the LLM decoding radius, and that it can be up to an wide tilde Omega (sqrt n ) factor larger. We consider the problem of learning an unknown large-margin halfspace in the context of parallel computation, giving both positive and negative results. As our main positive result, we give a parallel algorithm for learning a large-margin half-space, based on an algorithm of Nesterov's that performs gradient descent with a momentum term. We show that this algorithm can learn an unknown γ-margin halfspace over n dimensions using n ċ poly(1 γ) processors and running in time O(1 γ)+O(log n). In contrast, naive parallel algorithms that learn a γ-margin halfspace in time that depends polylogarithmically on n have an inverse quadratic running time dependence on the margin parameter γ. Our negative result deals with boosting, which is a standard approach to learning large-margin halfspaces. We prove that in the original PAC framework, in which a weak learning algorithm is provided as an oracle that is called by the booster, boosting cannot be parallelized. More precisely, we show that, if the algorithm is allowed to call the weak learner multiple times in parallel within a single boosting stage, this ability does not reduce the overall number of successive stages of boosting needed for learning by even a single stage. Our proof is information-theoretic and does not rely on unproven assumptions. Learning an unknown halfspace (also called a perceptron) from labeled examples is one of the classic problems in machine learning. In the noise-free case, when a halfspace consistent with all the training examples exists, the problem can be solved in polynomial time using linear programming. However, under the promise that a halfspace consistent with a fraction @math of the examples exists (for some small constant @math ), it was not known how to efficiently find a halfspace that is correct on even 51 of the examples. Nor was a hardness result that ruled out getting agreement on more than 99.9 of the examples known. In this work, we close this gap in our understanding and prove that even a tiny amount of worst-case noise makes the problem of learning halfspaces intractable in a strong sense. Specifically, for arbitrary @math , we prove that given a set of examples-label pairs from the hypercube, a fraction @math of which can be explained by a halfspace, it is NP-hard to find a halfspace that correctly labels a fraction @math of the examples. The hardness result is tight since it is trivial to get agreement on @math the examples. In learning theory parlance, we prove that weak proper agnostic learning of halfspaces is hard. This settles a question that was raised by , in their work on learning halfspaces in the presence of random classification noise [Algorithmica, 22 (1998), pp. 35-52], and raised by authors of some more recent works as well. Along the way, we also obtain a strong hardness result for another basic computational problem: solving a linear system over the rationals. par>We prove some non-approximability results for restrictions of basic combinatorial optimization problems to instances of bounded “degreeror bounded “width.” Specifically: We prove that the Max 3SAT problem on instances where each variable occurs in at most B clauses, is hard to approximate to within a factor @math , unless @math . H stad [18] proved that the problem is approximable to within a factor @math in polynomial time, and that is hard to approximate to within a factor @math . Our result uses a new randomized reduction from general instances of Max 3SAT to bounded-occurrences instances. The randomized reduction applies to other Max SNP problems as well. We observe that the Set Cover problem on instances where each set has size at most B is hard to approximate to within a factor @math unless @math . The result follows from an appropriate setting of parameters in Feige's reduction [11]. This is essentially tight in light of the existence of @math -approximate algorithms [20, 23, 9] We present a new PCP construction, based on applying parallel repetition to the inner verifier,'' and we provide a tight analysis for it. Using the new construction, and some modifications to known reductions from PCP to Hitting Set, we prove that Hitting Set with sets of size B is hard to approximate to within a factor @math . The problem can be approximated to within a factor B [19], and it is the Vertex Cover problem for B =2. The relationship between hardness of approximation and set size seems to have not been explored before. We observe that the Independent Set problem on graphs having degree at most B is hard to approximate to within a factor @math , unless P = NP . This follows from a comination of results by Clementi and Trevisan [28] and Reingold, Vadhan and Wigderson [27]. It had been observed that the problem is hard to approximate to within a factor @math unless P = NP [1]. An algorithm achieving factor @math is also known [21, 2, 30, 16 .