Search

In federated frequency estimation (FFE), multiple clients work together to estimate the frequencies of their collective data by communicating with a server that respects the privacy constraints of Secure Summation (SecSum), a cryptographic multi-party computation protocol that ensures that the server can only access the sum of client-held vectors. For single-round FFE, it is known that count sketching is nearly information-theoretically optimal for achieving the fundamental accuracy-communication trade-offs [Chen et al., 2022]. However, we show that under the more practical multi-round FEE setting, simple adaptations of count sketching are strictly sub-optimal, and we propose a novel hybrid sketching algorithm that is provably more accurate. We also address the following fundamental question: how should a practitioner set the sketch size in a way that adapts to the hardness of the underlying problem? We propose a two-phase approach that allows for the use of a smaller sketch size for simpler problems (e.g. near-sparse or light-tailed distributions). We conclude our work by showing how differential privacy can be added to our algorithm and verifying its superior performance through extensive experiments conducted on large-scale datasets.

Recent research has observed that in machine learning optimization, gradient descent (GD) often operates at the edge of stability (EoS) [Cohen, et al., 2021], where the stepsizes are set to be large, resulting in non-monotonic losses induced by the GD iterates. This paper studies the convergence and implicit bias of constant-stepsize GD for logistic regression on linearly separable data in the EoS regime. Despite the presence of local oscillations, we prove that the logistic loss can be minimized by GD with any constant stepsize over a long time scale. Furthermore, we prove that with any constant stepsize, the GD iterates tend to infinity when projected to a max-margin direction (the hard-margin SVM direction) and converge to a fixed vector that minimizes a strongly convex potential when projected to the orthogonal complement of the max-margin direction. In contrast, we also show that in the EoS regime, GD iterates may diverge catastrophically under the exponential loss, highlighting the superiority of the logistic loss. These theoretical findings are in line with numerical simulations and complement existing theories on the convergence and implicit bias of GD, which are only applicable when the stepsizes are sufficiently small.

We consider a continual learning (CL) problem with two linear regression tasks in the fixed design setting, where the feature vectors are assumed fixed and the labels are assumed to be random variables. We consider an $\ell_2$-regularized CL algorithm, which computes an Ordinary Least Squares parameter to fit the first dataset, then computes another parameter that fits the second dataset under an $\ell_2$-regularization penalizing its deviation from the first parameter, and outputs the second parameter. For this algorithm, we provide tight bounds on the average risk over the two tasks. Our risk bounds reveal a provable trade-off between forgetting and intransigence of the $\ell_2$-regularized CL algorithm: with a large regularization parameter, the algorithm output forgets less information about the first task but is intransigent to extract new information from the second task; and vice versa. Our results suggest that catastrophic forgetting could happen for CL with dissimilar tasks (under a precise similarity measurement) and that a well-tuned $\ell_2$-regularization can partially mitigate this issue by introducing intransigence.

This paper considers the problem of learning a single ReLU neuron with squared loss (a.k.a., ReLU regression) in the overparameterized regime, where the input dimension can exceed the number of samples. We analyze a Perceptron-type algorithm called GLM-tron (Kakade et al., 2011) and provide its dimension-free risk upper bounds for high-dimensional ReLU regression in both well-specified and misspecified settings. Our risk bounds recover several existing results as special cases. Moreover, in the well-specified setting, we provide an instance-wise matching risk lower bound for GLM-tron. Our upper and lower risk bounds provide a sharp characterization of the high-dimensional ReLU regression problems that can be learned via GLM-tron. On the other hand, we provide some negative results for stochastic gradient descent (SGD) for ReLU regression with symmetric Bernoulli data: if the model is well-specified, the excess risk of SGD is provably no better than that of GLM-tron ignoring constant factors, for each problem instance; and in the noiseless case, GLM-tron can achieve a small risk while SGD unavoidably suffers from a constant risk in expectation. These results together suggest that GLM-tron might be preferable to SGD for high-dimensional ReLU regression., ICML 2023 camera ready

We study linear regression under covariate shift, where the marginal distribution over the input covariates differs in the source and the target domains, while the conditional distribution of the output given the input covariates is similar across the two domains. We investigate a transfer learning approach with pretraining on the source data and finetuning based on the target data (both conducted by online SGD) for this problem. We establish sharp instance-dependent excess risk upper and lower bounds for this approach. Our bounds suggest that for a large class of linear regression instances, transfer learning with $O(N^2)$ source data (and scarce or no target data) is as effective as supervised learning with $N$ target data. In addition, we show that finetuning, even with only a small amount of target data, could drastically reduce the amount of source data required by pretraining. Our theory sheds light on the effectiveness and limitation of pretraining as well as the benefits of finetuning for tackling covariate shift problems., 32 pages, 1 figure, 1 table

Details about this fiber laser system and the numerical simulation

Stochastic gradient descent (SGD) has achieved great success due to its superior performance in both optimization and generalization. Most of existing generalization analyses are made for single-pass SGD, which is a less practical variant compared to the commonly-used multi-pass SGD. Besides, theoretical analyses for multi-pass SGD often concern a worst-case instance in a class of problems, which may be pessimistic to explain the superior generalization ability for some particular problem instance. The goal of this paper is to sharply characterize the generalization of multi-pass SGD, by developing an instance-dependent excess risk bound for least squares in the interpolation regime, which is expressed as a function of the iteration number, stepsize, and data covariance. We show that the excess risk of SGD can be exactly decomposed into the excess risk of GD and a positive fluctuation error, suggesting that SGD always performs worse, instance-wisely, than GD, in generalization. On the other hand, we show that although SGD needs more iterations than GD to achieve the same level of excess risk, it saves the number of stochastic gradient evaluations, and therefore is preferable in terms of computational time., Comment: 28 pages, 2 figures

Stochastic gradient descent (SGD) has been shown to generalize well in many deep learning applications. In practice, one often runs SGD with a geometrically decaying stepsize, i.e., a constant initial stepsize followed by multiple geometric stepsize decay, and uses the last iterate as the output. This kind of SGD is known to be nearly minimax optimal for classical finite-dimensional linear regression problems (Ge et al., 2019). However, a sharp analysis for the last iterate of SGD in the overparameterized setting is still open. In this paper, we provide a problem-dependent analysis on the last iterate risk bounds of SGD with decaying stepsize, for (overparameterized) linear regression problems. In particular, for last iterate SGD with (tail) geometrically decaying stepsize, we prove nearly matching upper and lower bounds on the excess risk. Moreover, we provide an excess risk lower bound for last iterate SGD with polynomially decaying stepsize and demonstrate the advantage of geometrically decaying stepsize in an instance-wise manner, which complements the minimax rate comparison made in prior works., 35 pages, 2 figures, 1 table. In ICML 2022

Stochastic gradient descent (SGD) exhibits strong algorithmic regularization effects in practice, which has been hypothesized to play an important role in the generalization of modern machine learning approaches. In this work, we seek to understand these issues in the simpler setting of linear regression (including both underparameterized and overparameterized regimes), where our goal is to make sharp instance-based comparisons of the implicit regularization afforded by (unregularized) average SGD with the explicit regularization of ridge regression. For a broad class of least squares problem instances (that are natural in high-dimensional settings), we show: (1) for every problem instance and for every ridge parameter, (unregularized) SGD, when provided with logarithmically more samples than that provided to the ridge algorithm, generalizes no worse than the ridge solution (provided SGD uses a tuned constant stepsize); (2) conversely, there exist instances (in this wide problem class) where optimally-tuned ridge regression requires quadratically more samples than SGD in order to have the same generalization performance. Taken together, our results show that, up to the logarithmic factors, the generalization performance of SGD is always no worse than that of ridge regression in a wide range of overparameterized problems, and, in fact, could be much better for some problem instances. More generally, our results show how algorithmic regularization has important consequences even in simpler (overparameterized) convex settings., 33 pages, 1 figure. In NeurIPS 2021

Preventing catastrophic forgetting while continually learning new tasks is an essential problem in lifelong learning. Structural regularization (SR) refers to a family of algorithms that mitigate catastrophic forgetting by penalizing the network for changing its "critical parameters" from previous tasks while learning a new one. The penalty is often induced via a quadratic regularizer defined by an \emph{importance matrix}, e.g., the (empirical) Fisher information matrix in the Elastic Weight Consolidation framework. In practice and due to computational constraints, most SR methods crudely approximate the importance matrix by its diagonal. In this paper, we propose \emph{Sketched Structural Regularization} (Sketched SR) as an alternative approach to compress the importance matrices used for regularizing in SR methods. Specifically, we apply \emph{linear sketching methods} to better approximate the importance matrices in SR algorithms. We show that sketched SR: (i) is computationally efficient and straightforward to implement, (ii) provides an approximation error that is justified in theory, and (iii) is method oblivious by construction and can be adapted to any method that belongs to the structural regularization class. We show that our proposed approach consistently improves various SR algorithms' performance on both synthetic experiments and benchmark continual learning tasks, including permuted-MNIST and CIFAR-100.

There is an increasing realization that algorithmic inductive biases are central in preventing overfitting; empirically, we often see a benign overfitting phenomenon in overparameterized settings for natural learning algorithms, such as stochastic gradient descent (SGD), where little to no explicit regularization has been employed. This work considers this issue in arguably the most basic setting: constant-stepsize SGD (with iterate averaging or tail averaging) for linear regression in the overparameterized regime. Our main result provides a sharp excess risk bound, stated in terms of the full eigenspectrum of the data covariance matrix, that reveals a bias-variance decomposition characterizing when generalization is possible: (i) the variance bound is characterized in terms of an effective dimension (specific for SGD) and (ii) the bias bound provides a sharp geometric characterization in terms of the location of the initial iterate (and how it aligns with the data covariance matrix). More specifically, for SGD with iterate averaging, we demonstrate the sharpness of the established excess risk bound by proving a matching lower bound (up to constant factors). For SGD with tail averaging, we show its advantage over SGD with iterate averaging by proving a better excess risk bound together with a nearly matching lower bound. Moreover, we reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares (minimum-norm interpolation) and ridge regression. Experimental results on synthetic data corroborate our theoretical findings., Comment: 56 pages, 2 figures. A short version is accepted at the 34th Annual Conference on Learning Theory (COLT 2021)

A large number of Gas Insulated Switchgear (GIS) has been put into use, which has caused serious electromagnetic interference. Especially for the isolation switch in GIS, it doesn’t have the ability to extinguish the arc when operating with small capacitive currents, resulting in contact between the contacts. The steep voltage waves rapidly fold back and forth in a compact pipeline space to form a very fast transient overvoltage (VFTO). In this paper, the finite integration method suitable for solving the theory of electric dipole antennas in electrically large-scale space electromagnetic fields is combined with CST MWS software to analyze and calculate the radiation interference of VFTO. The electric field strength at a position one meters away from the disturbance source in the simulation model is 4–12 kV /m, the magnetic field strength is 100–420A/m. By optimizing the physical structure of the transformer, the electric field strength is reduced to 2.2–2.5 kV/m, and the magnetic field strength is reduced to 29–116 A/m.

In this work, we report a >100 W femtosecond (fs) burst mode all-fiber laser system at 1.0 µm that operates at an intra-burst repetition rate of up to 1.2 GHz. This fiber laser system provides the highest output power that has been reported so far for GHz fs fiber lasers, to the best of our knowledge. In addition to the superior output power, this fiber laser system also shows a promising overall figure of merit, specifically in terms of pulse width (473 fs), long-term reliability (

Understanding the algorithmic bias of \emph{stochastic gradient descent} (SGD) is one of the key challenges in modern machine learning and deep learning theory. Most of the existing works, however, focus on \emph{very small or even infinitesimal} learning rate regime, and fail to cover practical scenarios where the learning rate is \emph{moderate and annealing}. In this paper, we make an initial attempt to characterize the particular regularization effect of SGD in the moderate learning rate regime by studying its behavior for optimizing an overparameterized linear regression problem. In this case, SGD and GD are known to converge to the unique minimum-norm solution; however, with the moderate and annealing learning rate, we show that they exhibit different \emph{directional bias}: SGD converges along the large eigenvalue directions of the data matrix, while GD goes after the small eigenvalue directions. Furthermore, we show that such directional bias does matter when early stopping is adopted, where the SGD output is nearly optimal but the GD output is suboptimal. Finally, our theory explains several folk arts in practice used for SGD hyperparameter tuning, such as (1) linearly scaling the initial learning rate with batch size; and (2) overrunning SGD with high learning rate even when the loss stops decreasing., Comment: ICLR 2021 Camera Ready

The reservoir of Shaximiao Formation is mainly composed of channel coarse sandstone and fine sandstone. The rocks are dense, the lithology is single and the thickness is l arge. The physical properties of Shaximiao Formation are not clear for the northeast Sichuan area. Based on field and core physical property analysis of Shaximiao Formation in Northeast Sichuan Basin, the characteristics of porosity and permeability of Shaximiao Formation are defined, the porosity-permeability relation chart is established, and on this basis, The tight reservoir of Shaximiao Formation was evaluated, the result show that the favorable reservoir is mainly located in the intersection area of channel sand, the reservoirs are mainly of III type, followed by the reservoirs of II type, and the I type are the least.

The gradient noise of SGD is considered to play a central role in the observed strong generalization abilities of deep learning. While past studies confirm that the magnitude and the covariance structure of gradient noise are critical for regularization, it remains unclear whether or not the class of noise distributions is important. In this work we provide negative results by showing that noises in classes different from the SGD noise can also effectively regularize gradient descent. Our finding is based on a novel observation on the structure of the SGD noise: it is the multiplication of the gradient matrix and a sampling noise that arises from the mini-batch sampling procedure. Moreover, the sampling noises unify two kinds of gradient regularizing noises that belong to the Gaussian class: the one using (scaled) Fisher as covariance and the one using the gradient covariance of SGD as covariance. Finally, thanks to the flexibility of choosing noise class, an algorithm is proposed to perform noisy gradient descent that generalizes well, the variant of which even benefits large batch SGD training without hurting generalization., Comment: ICML 2020 near camera ready version

In this paper, the author studied the effect of laser quenching scan time on the wear resistance of 45# steel against plant abrasive by using alfalfa meal as a typical plant abrasive. The results showed that under the experimental conditions, the maximum surface hardness of the material can reach 735HV, and the maximum hardness of the material is between 0.5 and 0.8 mm from the surface; the wear resistance of 45# steel after laser quenching is much higher than that without laser; the higher hardness of the treated specimen, the better wear resistance; in comparison with the untreated specimen, the plow depth of the surface of the specimen after laser treatment is significantly shallower and narrower, and the degree of fatigue wear is also significantly smaller than untreated specimen.

The existing current standards for electronic transformers are formulated based on the equivalent of traditional electromagnetic transformers and secondary side protection equipments. In this situation, Although these products have can passed the type test, but there are still a large number of electromagnetic compatibility (EMC) problems still appeared in actual operation. In this paper, based on the actual field application, the interference mechanism of the AIS isolating switch and the electromagnetic transient process on the electronic transformers is simulated. The interference model of the transient electromagnetic field to the secondary side of the electronic transformers and the transmission cables are obtained. Then, a field system-level EMC test method of electronic transformers is proposed. This method is based on the actual equipment and wiring conditions in substations, and the anti-strong electromagnetic disturbance ability of the electronic transformers is evaluated under the condition of “conventional” or “unconventional” operations. Finally, Finally, the field application of system-level electromagnetic compatibility test was carried out in the 330kV Xinsheng Substation, and the fault electronic transformer was tested, which proved the effectiveness of the method.

Understanding the behavior of stochastic gradient descent (SGD) in the context of deep neural networks has raised lots of concerns recently. Along this line, we study a general form of gradient based optimization dynamics with unbiased noise, which unifies SGD and standard Langevin dynamics. Through investigating this general optimization dynamics, we analyze the behavior of SGD on escaping from minima and its regularization effects. A novel indicator is derived to characterize the efficiency of escaping from minima through measuring the alignment of noise covariance and the curvature of loss function. Based on this indicator, two conditions are established to show which type of noise structure is superior to isotropic noise in term of escaping efficiency. We further show that the anisotropic noise in SGD satisfies the two conditions, and thus helps to escape from sharp and poor minima effectively, towards more stable and flat minima that typically generalize well. We systematically design various experiments to verify the benefits of the anisotropic noise, compared with full gradient descent plus isotropic diffusion (i.e. Langevin dynamics)., Comment: ICML 2019 camera ready

Fire protection performance is one of the most important capabilities for aircraft engine, since the result may be hazardous in the case of a fire condition. According to fire protection regulation CCAR 33.17 of China Civil Aviation Regulations, fire-proof tests of a specific pipeline, a fuel tank and a fuel filter assembly were carried out. Test conditions include inlet fluid temperature, fluid pressure, fluid volume flow, fire temperature and heat flux density. The average flame temperature during the fire tests is 2000 degrees Fahrenheit, the heat flux density is 116kW/m2±10kW/m2 and the distance from burner exhaust to the test area is 100mm in these fire tests. Fire test of pipe passed, but the fire test of oil tank failed because of the failure of the oil circulation system and the melting of plastic pipe material in the ventilation pipe separately. The first fire test of the fuel filter failed because of design defect of one oil drainage path, but after design change of the oil drainage path, the second one succeeded. Based on the fire protection tests and results analysis, three essential factors of fire protection performance and type certification were presented: 1. Volume of medium retained in test parts; 2. Mass flow of medium; 3. Pressure in the test parts cavity.

This paper proposes a drawing method of frequency division fault maps for GIS partial discharge based on Ultra-high Frequency signals. By extracting Ultra-high Frequency partial discharge signals and filtering adaptively, interference signals are filtered out real-timely, and the effective frequency sequence is obtained adaptively. The characteristic quantity of each effective frequency point is calculated, and then dynamic fault map varying with effective frequency points, characteristics trend map for frequency division discharge and quantity trend map for effective frequency points are drawn. Compared with current fault maps for GIS partial discharge, test results show that the discharge law for different frequency points is drawn by contacting effective frequency points with partial discharge law proposed in this paper, which is helpful for research on discharge law with the frequency.

The paired-domain transcription factor PAX9 plays a critical role in tooth development, as heterozygous mutations in PAX9 have been shown to be associated with human tooth agenesis. In this study, we report 2 novel missense mutations, gly6arg (G6R) and ser43lys (S43K), in the paired domain of PAX9 in Chinese patients with varying degrees of nonsyndromic tooth agenesis. Excluding third molars, the individual with the G6R mutation was missing 2 mandibular incisors and a maxillary premolar, while the phenotype of individuals with the S43K mutation consisted of peg-shaped upper lateral incisors and missing molars, premolars and canines. As these 2 mutations occur at highly conserved amino acids in the PAX gene family and between different species, we further analyzed the effects of the mutations on the function of the resulting proteins. Immunofluorescence and immunoblotting studies showed that the mutations did not alter nuclear localization in mammalian cells. Gel shift and super shift assays indicate that both mutant proteins bound DNA at a lower level than the normal protein, with G6R having a greater affinity for DNA than S43K. Likewise, the G6R protein was able to transcriptionally activate a Bmp4 promoter construct to a greater extent than S43K. Our finding that the severity of tooth agenesis in the patients was correlated to the DNA-binding capacity of the mutated PAX9 9proteins supports the hypothesis that DNA binding is responsible for the genetic defect.

An 8–18 GHz broadband high power amplifier (HPA) with a hybrid integrated circuit (HIC) is designed and fabricated. This HPA is achieved with the use of a 4-fingered micro-strip Lange coupler in a GaAs MMIC process. In order to decrease electromagnetic interference, a multilayer AlN material with good heat dissipation is adopted as the carrier of the power amplifier. When the input power is 25 dBm, the saturated power of the continuous wave (CW) outputted by the power amplifier is more than 39 dBm within the frequency range of 8–13 GHz, while it is more than 38.6 dBm within other frequency ranges. We obtain the peak power output, 39.4 dBm, at the frequency of 11.9 GHz. In the whole frequency band, the power-added efficiency is more than 18%. When the input power is 18 dBm, the small signal gain is 15.7 ± 0.7 dB. The dimensions of the HPA are 25 × 15 × 1.5 mm3.