Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass (ITCS 2016), yet their broader combinatorial and spectral properties remain poorly understood. We develop a combinatorial characterization of the spectral structure of HD-walks on two-sided local-spectral expanders (Dinur and Kaufman FOCS 2017), which offer a broad generalization of the well-studied Johnson and Grassmann graphs. Our characterization, which shows that the spectra of HD-walks lie tightly concentrated in a few combinatorially structured strips, leads to novel structural theorems such as a tight ℓ2-characterization of edge-expansion, as well as to a new understanding of local-to-global graph algorithms on HDX.
Towards the latter, we introduce a novel spectral complexity measure called Stripped Threshold Rank, and show how it can replace the (much larger) threshold rank as a parameter controlling the performance of algorithms on structured objects. Combined with a sum-of-squares proof for the former ℓ2-characterization, we give a concrete application of this framework to algorithms for unique games on HD-walks, where in many cases we improve the state of the art (Barak, Raghavendra, and Steurer FOCS 2011, and Arora, Barak, and Steurer JACM 2015) from nearly-exponential to polynomial time (e.g. for sparsifications of Johnson graphs or of slices of the q-ary hypercube). Our characterization of expansion also holds an interesting connection to hardness of approximation, where an ℓ∞-variant for the Grassmann graphs was recently used to resolve the 2-2 Games Conjecture (Khot, Minzer, and Safra FOCS 2018). We give a reduction from a related ℓ∞-variant to our ℓ2-characterization, but it loses factors in the regime of interest for hardness where the gap between ℓ2 and ℓ∞ structure is large. Nevertheless, our results open the door for further work on the use of HDX in hardness of approximation and their general relation to unique games.
more »
« less
A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case
We give a tight characterization of the (vectorized Euclidean) norm of weights
required to realize a function f : Rd → R as a single hidden-layer ReLU network
with an unbounded number of units (infinite width), extending the univariate characterization of Savarese et al. (2019) to the multivariate case.
more »
« less
- Award ID(s):
- 1764032
- NSF-PAR ID:
- 10167329
- Date Published:
- Journal Name:
- International Conference on Learning Representations (ICLR 2020)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Experimental science is enabled by the combination of synthesis, imaging, and functional characterization organized into evolving discovery loop. Synthesis of new material is typically followed by a set of characterization steps aiming to provide feedback for optimization or discover fundamental mechanisms. However, the sequence of synthesis and characterization methods and their interpretation, or research workflow, has traditionally been driven by human intuition and is highly domain specific. Here, we explore concepts of scientific workflows that emerge at the interface between theory, characterization, and imaging. We discuss the criteria by which these workflows can be constructed for special cases of multiresolution structural imaging and functional characterization, as a part of more general material synthesis workflows. Some considerations for theory–experiment workflows are provided. We further pose that the emergence of user facilities and cloud labs disrupts the classical progression from ideation, orchestration, and execution stages of workflow development. To accelerate this transition, we propose the framework for workflow design, including universal hyperlanguages describing laboratory operation, ontological domain matching, reward functions and their integration between domains, and policy development for workflow optimization. These tools will enable knowledge-based workflow optimization; enable lateral instrumental networks, sequential and parallel orchestration of characterization between dissimilar facilities; and empower distributed research.
-
Line-edge roughness (LER) characterization is vital in the semiconductor industry to this day. This paper presents an EKEI (enhanced knife edge interferometry)-based system for photomask LER characterization. From the given EKEI-based system, the LER on the photomask pattern can be characterized. In this paper, the Fresnel (F) number-based geometrical optical model was developed for the LER-induced edge diffraction fringe simulation. The LER here was defined by three times the standard deviation of the edge profile on the photomask. Periodic rectangular functions were employed to characterize LER effects on the diffraction fringe patterns in simulation. The simulation-generated fringe pattern was then analyzed by cross-correlation. From the simulation result, the fringe pattern will get attenuated when adding the LER onto the line edge profile. Once the LER value increases, some of the high-order fringes vanish. A negative correlation between the similarity and the LER value was discovered. From the F number-based simulation model, the real photomask decorated with different LER values was designed and fabricated. After the photomask writing process, we used the EKEI system to scan the LER-programmed pattern for photomask LER characterization. By using the cross-correlation, the same trend was found in the experiment and simulation results. The fringe pattern from the edge was attenuated while the LER was added to the edge. The geometrical-based simulation and analysis model for photomask LER characterization was validated. From the simulation results, the fringe pattern from the edge was attenuated when adding LER on the edge. The experiment results show good agreement with the simulation ones. In sum, the proposed EKEI-based system has great potential to be utilized for on-machine photomask LER characterization and those defect inspection. The F number-based geometrical optical model also has the potential for diffraction-free pattern design and analysis.more » « less
-
Crosstalk is a major source of noise in Noisy Intermediate-Scale Quantum (NISQ) systems and is a fundamental challenge for hardware design. When multiple instructions are executed in parallel, crosstalk between the instructions can corrupt the quantum state and lead to incorrect program execution. Our goal is to mitigate the application impact of crosstalk noise through software techniques. This requires (i) accurate characterization of hardware crosstalk, and (ii) intelligent instruction scheduling to serialize the affected operations. Since crosstalk characterization is computationally expensive, we develop optimizations which reduce the characterization overhead. On 3 20-qubit IBMQ systems, we demonstrate two orders of magnitude reduction in characterization time (compute time on the QC device) compared to all-pairs crosstalk measurements. Informed by these characterization, we develop a scheduler that judiciously serializes high crosstalk instructions balancing the need to mitigate crosstalk and exponential decoherence errors from serialization. On real-system runs on 3 IBMQ systems, our scheduler improves the error rate of application circuits by up to 5.6x, compared to the IBM instruction scheduler and offers near-optimal crosstalk mitigation in practice. In a broader picture, the difficulty of mitigating crosstalk has recently driven QC vendors to move towards sparser qubit connectivity or disabling nearby operations entirely in hardware, which can be detrimental to performance. Our work makes the case for software mitigation of crosstalk errors.more » « less
-
more » « less
Abstract High‐resolution characterization of hydraulic properties and dense nonaqueous phase liquid (DNAPL) contaminant source is crucial to develop efficient remediation strategies. However, DNAPL characterization suffers from a limited number of borehole data in the field, resulting in a low‐resolution estimation. Moreover, high‐resolution DNAPL characterization requires a large number of unknowns to be estimated, presenting a computational bottleneck. In this paper, a low‐cost geophysical approach, the self‐potential method, is used as additional information for hydraulic properties characterization. Joint inversion of hydraulic head and self‐potential measurements is proposed to improve hydraulic conductivity estimation, which is then used to characterize the DNAPL saturation distribution by inverting partitioning tracer measurements. The computational barrier is overcome by (a) solving the inversion by the principal component geostatistical approach, in which the covariance matrix is replaced by a low‐rank approximation, thus reducing the number of forward model runs; (b) using temporal moments of concentrations instead of individual concentration data points for faster forward simulations. To assess the ability of the proposed approach, numerical experiments are conducted in a 3‐D aquifer with 104unknown hydraulic conductivities and DNAPL saturations. Results show that with realistic DNAPL sources and a limited number of hydraulic heads, the traditional hydraulic/partitioning tracer tomography roughly reconstructs subsurface heterogeneity but fails to resolve the DNAPL distribution. By adding self‐potential data, the error is reduced by 24% in hydraulic conductivity estimation and 68% in DNAPL saturation characterization. The proposed sequential inversion framework utilizes the complementary information from multi‐source hydrogeophysical data sets, and can provide high‐resolution characterizations for realistic DNAPL sources.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
