检索结果-内蒙古大学图书馆

linear threshold functions in decision lists, decision trees, and depth-2 circuits

INFORMATION PROCESSING LETTERS 2024年 183卷

作者： Dahiya, Yogesh Vignesh, K. Mahajan, Meena Sreenivasaiah, Karteek CI Homi Bhabha Natl Inst Inst Math Sci CIT Campus Chennai 600113 Tamil Nadu India Indian Inst Technol Hyderabad Hyderabad 502285 Telangana India

We show that polynomial-size constant-rank linear decision trees (LDTs) can be converted to polynomial-size depth-2 threshold circuits LTF o LTF. An intermediate construct is polynomial-size decision lists that query a conjunction of a constant number of linear threshold functions (LTFs);we show that these are equivalent to polynomial-size exact linear decision lists (ELDLs) i.e. decision lists querying exact threshold functions (ELTFs).& COPY;2023 Elsevier B.V. All rights reserved.

关键词： Computational complexity linear threshold functions Decision trees Depth-2 circuits Tree rank

来源：评论

学校读者我要写书评

暂无评论

On the Approximation Resistance of Balanced linear threshold functions 2019

On the Approximation Resistance of Balanced Linear Threshold...

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Potechin, Aaron Univ Chicago Chicago IL 60637 USA

In this paper, we show that there exists a balanced linear threshold function (LTF) which is unique games hard to approximate, refuting a conjecture of Austrin, Benabbas, and Magen. We also show that the almost monarc... 详细信息

ISBN: (纸本)9781450367059

关键词： constraint satisfaction problems hardness of approximation linear threshold functions

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise 35

Near-Optimal Statistical Query Hardness of Learning Halfspac...

引用

35th Conference on Learning Theory (COLT)

作者： Diakonikolas, Ilias Kane, Daniel M. Univ Wisconsin Madison WI 53706 USA Univ Calif San Diego San Diego CA 92103 USA

We study the problem of PAC learning halfspaces with Massart noise. Given labeled samples (x;y) from a distribution D on R-d x {+/- 1} such that the marginal D-x on the examples is arbitrary and the label y of example x is generated from the target halfspace corrupted by a Massart adversary with flipping probability eta(x) <= eta <= 1/2, the goal is to compute a hypothesis with small misclassification error. The best known poly(d, 1/epsilon)-time algorithms for this problem achieve error of eta + epsilon, which can be far from the optimal bound of OPT + epsilon, where OPT = E-x similar to Dx [eta(x)]. While it is known that achieving OPT + o(1) error requires super-polynomial time in the Statistical Query model, a large gap remains between known upper and lower bounds. In this work, we essentially characterize the efficient learnability of Massart halfspaces in the Statistical Query (SQ) model. Specifically, we show that no efficient SQ algorithm for learning Massart halfspaces on R-d can achieve error better than Omega(eta), even if OPT = 2(-log c (d)), for any universal constant epsilon is an element of (0, 1). Furthermore, when the noise upper bound eta is close to 1/2, our error lower bound becomes eta - o eta (1), where the o(eta) (1) term goes to 0 when eta approaches 1/2. Our results provide strong evidence that known learning algorithms for Massart halfspaces are nearly best possible.

关键词： Statistical Query Model Halfspaces linear threshold functions Massart Noise

来源：评论

学校读者我要写书评

暂无评论

HALF-SPACES WITH INFLUENTIAL VARIABLE

引用

THEORY OF PROBABILITY AND ITS APPLICATIONS 2020年第1期65卷 114-120页

作者： Dzindzalieta, D. Goetze, F. Vilnius Univ Fac Math & Informat LT-01513 Vilnius Lithuania Univ Bielefeld Fak Math D-33615 Bielefeld Germany

We consider Boolean functions f defined on Boolean cube {-1, 1}(n) of half-spaces, i.e., functions of the form f (x) = sign(omega.x-theta). Half-space functions are often called linear threshold functions. We assume that the Boolean cube {-1,1}(n) is equipped with a uniform measure. We also assume that parallel to omega parallel to(2 )<= 1 and parallel to omega parallel to(infinity) = delta for some delta > 0. Let 0 <= epsilon <= 1 be such that vertical bar Ef vertical bar <= 1 - epsilon. We prove that there exists a constant C > 0 such that max,(Inf(i),f) >= C delta epsilon, where Inf(i) f denotes the influence of the ith coordinate of the function f. This establishes the lower bound obtained earlier by Matulef et al. [SIAM J. Comput., 39 (2010), pp. 2004-2047]. We also show that the optimal constant in this inequality exceeds 3-root 2/64 approximate to 0.066. As an auxiliary result we prove a lower bound for small ball inequalities of linear combinations of Rademacher random variables.

关键词： Boolean functions small ball inequalities linear threshold functions Boolean cube influence

来源：评论

学校读者我要写书评

暂无评论

Enumerating Hassett's Wall and Chamber Decomposition of the Moduli Space of Weighted Stable Curves

引用

EXPERIMENTAL MATHEMATICS 2020年第1期29卷 36-53页

作者： Ascher, Kenneth Dube, Connor Gershenson, Daniel Hou, Elaine MIT Dept Math Cambridge MA 02139 USA Yale Univ Dept Math New Haven CT 06520 USA

Hassett constructed a class of modular compactifications of by adding weights to the marked points. This leads to a natural wall and chamber decomposition of the domain of admissible weights , where the moduli space and universal family remain constant inside a chamber, and may change upon crossing a wall. The goal of this paper is to count the number of chambers in this decomposition. We relate these chambers to a class of boolean functions known as linear threshold functions (LTFs), and discover a subclass of LTFs which are in bijection with the chambers. Using this relation, we prove an asymptotic formula for the number of chambers, and compute the exact number of chambers for n <= 9. In addition, we provide an algorithm for the enumeration of chambers of and prove results in computational complexity.

关键词： Moduli spaces stable curves wall-and-chamber linear threshold functions birational geometry

来源：评论

学校读者我要写书评

暂无评论

Efficient, Noise-Tolerant, and Private Learning via Boosting 33

Efficient, Noise-Tolerant, and Private Learning via Boosting

引用

33rd Conference on Learning Theory (COLT)

作者： Bun, Mark Carmosino, Marco Leandro Sorrell, Jessica Boston Univ Dept Comp Sci 111 Cummington Mall Boston MA 02215 USA Simon Fraser Univ Sch Comp Sci 8888 Univ Dr Burnaby BC V5A 1S6 Canada Univ Calif San Diego Dept Comp Sci & Engn 9500 Gilman Dr La Jolla CA 92093 USA

We introduce a simple framework for designing private boosting algorithms. We give natural conditions under which these algorithms are differentially private, efficient, and noise-tolerant PAC learners. To demonstrate our framework, we use it to construct noise-tolerant and private PAC learners for large-margin halfspaces whose sample complexity does not depend on the dimension. We give two sample complexity bounds for our large-margin halfspace learner. One bound is based only on differential privacy, and uses this guarantee as an asset for ensuring generalization. This first bound illustrates a general methodology for obtaining PAC learners from privacy, which may be of independent interest. The second bound uses standard techniques from the theory of large-margin classification (the fat-shattering dimension) to match the best known sample complexity for differentially private learning of large-margin halfspaces, while additionally tolerating random label noise.

关键词： Boosting Differential Privacy Learning with Noise linear threshold functions

来源：评论

学校读者我要写书评

暂无评论

Limits on Representing Boolean functions by linear Combinations of Simple functions: thresholds, ReLUs, and Low-Degree Polynomials 33

Limits on Representing Boolean Functions by Linear Combinati...

引用

33rd Computational Complexity Conference (CCC)

作者： Williams, Richard Ryan MIT EECS 32 Vassar St Cambridge MA 02139 USA MIT CSAIL 32 Vassar St Cambridge MA 02139 USA

ISBN: (纸本)9783959770699

We consider the problem of representing Boolean functions exactly by "sparse" linear combinations (over R) of functions from some "simple" class C. In particular, given C we are interested in finding low-complexity functions lacking sparse representations. When C forms a basis for the space of Boolean functions (e.g., the set of PARITY functions or the set of conjunctions) this sort of problem has a well-understood answer;the problem becomes interesting when C is "overcomplete" and the set of functions is not linearly independent. We focus on the cases where C is the set of linear threshold functions, the set of rectified linear units (ReLUs), and the set of low-degree polynomials over a finite field, all of which are well-studied in different contexts. We provide generic tools for proving lower bounds on representations of this kind. Applying these, we give several new lower bounds for "semi-explicit" Boolean functions. Let alpha(n) be an unbounded function such that n(alpha(n)) is time constructible (e.g. alpha(n) = log(star)(n)). We show: functions in NTIME[n(alpha(n))] that require super-polynomially many linear threshold functions to represent (depth-two neural networks with sign activation function, a special case of depthtwo threshold circuit lower bounds). functions in NTIME[n(alpha(n))] that require super-polynomially many ReLU gates to represent (depth-two neural networks with ReLU activation function). functions in NTIME[n(alpha(n))] that require super-polynomially many O(1)-degree F-p-polynomials to represent exactly, for every prime p (related to problems regarding Higher-Order "Uncertainty Principles"). We also obtain a function in E-NP requiring 2(Omega(n)) linear combinations. functions in NTIME[n(poly(log n))] that require super-polynomially many ACC o THR circuits to represent exactly (further generalizing the recent lower bounds of Murray and the author). We also obtain "fixed-polynomial" lower bounds for functions in NP, for the first three repre

关键词： linear threshold functions lower bounds neural networks low-degree polynomials

来源：评论

学校读者我要写书评

暂无评论

New Algorithms and Lower Bounds for Circuits With linear threshold Gates

引用

THEORY OF COMPUTING 2018年 14卷

作者： Williams, R. Ryan MIT Elect Engn & Comp Sci 77 Massachusetts Ave Cambridge MA 02139 USA

Let ACC circle THR be the class of constant-depth circuits comprised of AND, OR, and MODm gates (for some constant m > 1), with a bottom layer of gates computing arbitrary linear threshold functions. This class of circuits can be seen as a "midpoint" between ACC (where we know nontrivial lower bounds) and depth- two linear threshold circuits (where nontrivial lower bounds remain open). We give an algorithm for evaluating an arbitrary symmetric function of 2(no(1)) ACC circle THR circuits of size 2(no(1)), on all possible inputs, in 2(n) . poly (n) time. Several consequences are derived: The number of satisfying assignments to an ACC circle THR circuit of 2(no(1)) size is computable in 2(n-n epsilon) time (where e epsilon > 0 depends on the depth and modulus of the circuit). NEXP does not have quasi- polynomial size ACC circle THR circuits, and NEXP does not have quasi-polynomial size ACC circle SYM circuits. Nontrivial size lower bounds were not known even for AND circle OR circle THR circuits. Every 0-1 integer linear program with n Boolean variables and s linear constraints is solvable in 2(n-Omega n(n/log4(sM(logn)))) . poly (s, n, M) time with high probability, where M <= 2(no(1)) is an upper bound on the bit-length of the coefficients. (For example, 0-1 integer programs with weights in [-2(no(1)), 2(no(1))] and poly (n) constraints can be solved in 2(n-Omega n(n/log4n)) time.) We also present an algorithm for evaluating depth-two linear threshold circuits ( also known as THR circle THR) with exponential weights and 2(n/24) size on all 2(n) input assignments, running in 2n . poly (n) time. This is evidence that non-uniform lower bounds for THR circle THR are within reach.

关键词： circuit complexity satisfiability algorithms linear threshold functions

来源：评论

学校读者我要写书评

暂无评论

Limits on representing boolean functions by linear combinations of simple functions: thresholds, reLUs, and low-degree polynomials 18

Limits on representing boolean functions by linear combinati...

引用

Proceedings of the 33rd Computational Complexity Conference

作者： Richard Ryan Williams EECS and CSAIL

ISBN: (纸本)9783959770699

We consider the problem of representing Boolean functions exactly by "sparse" linear combinations (over R) of functions from some "simple" class C. In particular, given C we are interested in finding low-complexity functions lacking sparse representations. When C forms a basis for the space of Boolean functions (e.g., the set of PARITY functions or the set of conjunctions) this sort of problem has a well-understood answer; the problem becomes interesting when C is "overcomplete" and the set of functions is not linearly independent. We focus on the cases where C is the set of linear threshold functions, the set of rectified linear units (ReLUs), and the set of low-degree polynomials over a finite field, all of which are well-studied in different *** provide generic tools for proving lower bounds on representations of this kind. Applying these, we give several new lower bounds for "semi-explicit" Boolean functions. Let α(n) be an unbounded function such that nα(n) is time constructible (e.g. α(n) = log*(n)). We show:• functions in NTIME[nα(n)] that require super-polynomially many linear threshold functions to represent (depth-two neural networks with sign activation function, a special case of depth-two threshold circuit lower bounds).• functions in NTIME[nα(n)] that require super-polynomially many ReLU gates to represent (depth-two neural networks with ReLU activation function).• functions in NTIME[nα(n)] that require super-polynomially many O(1)-degree Fp-polynomials to represent exactly, for every prime p (related to problems regarding Higher-Order "Uncertainty Principles"). We also obtain a function in ENP requiring 2ω(n) linear combinations.• functions in NTIME[npoly(log n)] that require super-polynomially many ACC ∘ THR circuits to represent exactly (further generalizing the recent lower bounds of Murray and the author).We also obtain "fixed-polynomial" lower bounds for functions in NP, for the first three representation classes. All our lower bounds are

关键词： neural networks linear threshold functions lower bounds low-degree polynomials

来源：评论

学校读者我要写书评

暂无评论

A ROBUST KHINTCHINE INEQUALITY, AND ALGORITHMS FOR COMPUTING OPTIMAL CONSTANTS IN FOURIER ANALYSIS AND HIGH-DIMENSIONAL GEOMETRY

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2016年第2期30卷 1058-1094页

作者： De, Anindya Diakonikolas, Ilias Servedio, Rocco A. Univ Calif Berkeley Berkeley CA 94720 USA Univ Edinburgh Edinburgh EH8 9YL Midlothian Scotland Columbia Univ Dept Comp Sci New York NY 10027 USA

This paper makes two contributions towards determining some well-studied optimal constants in Fourier analysis of Boolean functions and high-dimensional geometry. It has been known since 1994 [C. Gotsman and N. Linial, Combinatorica, 14 (1994), pp. 35-50] that every linear threshold function (LTF) has a squared Fourier mass of at least 1/2 on its degree-0 and degree-1 coefficients. Let the minimum such Fourier mass be W-<= 1[LTF], where the minimum is taken over all n-variable LTFs and all n >= 0. Benjamini, Kalai, and Schramm [Publ. Math. Inst. Hautes Etudes Sci., 90 (1999), pp. 5-43] conjectured that the true value of W-<= 1[LTF] is 2/pi. We make progress on this conjecture by proving that W-<= 1[LTF] >= 1/2 + c for some absolute constant c > 0. The key ingredient in our proof is a "robust" version of the well-known Khintchine inequality in functional analysis, which we believe may be of independent interest. Let W-<= 1[LTFn] denote the minimum squared Fourier mass on the degree-0 and degree-1 coefficients of any n-variable LTF. We prove that for every eta > 0, there is a value K = K(eta) = poly(1/eta)such that W-<= 1[LTF] <= W-<= 1[LTFK] <= W-< 1[LTF] + eta. This easily yields an algorithm that runs in time 2(poly(1/eta)) and determines the value of W= 1[LTF] up to an additive error of +/-eta. We give an analogous structural result, and a similar 2(poly(1/eta))-time algorithm, to determine Tomaszewski's constant to within an additive error of +/-eta;this is the minimum (over all origin-centered hyperplanes H) fraction of points in {-1, 1}(n) that lie within a Euclidean distance 1 of H. Tomaszewski's constant is conjectured to be 1/2;lower bounds on it have been given by Holzman and Kleitman [Combinatorica, 12 (1992), pp. 303-316] and independently by Ben-Tal, Nemirovski, and Roos [SIAM J. Optim., 13 (2002), pp. 535-560]. Our structural results combine tools from anticoncentration of sums of independent random variables, Fourier analysis, and Hermite analysis of L

关键词： linear threshold functions halfspaces hyperplanes Khintchine inequality Fourier analysis

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：