OpenRaiser/Intern-Atlas huggingface dataset:
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
Venue: arXiv cs.CC 2021
Year: 2021

The orthogonality dimension of a graph $G=(V,E)$ over a field $\mathbb{F}$ is the smallest integer $t$ for which there exists an assignment of a vector $u_v \in \mathbb{F}^t$ with $\langle u_v,u_v \rangle \neq 0$ to every vertex $v \in V$, such that $\langle u_v, u_{v'} \rangle = 0$ whenever $v$ and $v'$ are adjacent vertices in $G$. The study of the orthogonality dimension of graphs is motivated by various applications in information theory and in theoretical computer science. The contribution of the present work is two-fold. First, we prove that there exists a constant $c$ such that for every sufficiently large integer $t$, it is $\mathsf{NP}$-hard to decide whether the orthogonality dimension of an input graph over $\mathbb{R}$ is at most $t$ or at least $3t/2-c$. At the heart of the proof lies a geometric result, which might be of independent interest, on a generalization of the orthogonality dimension parameter for the family of Kneser graphs, analogously to a long-standing conjecture of Stahl (J. Comb. Theo. Ser. B, 1976). Second, we study the smallest possible orthogonality dimension over finite fields of the complement of graphs that do not contain certain fixed subgraphs. In particular, we provide an explicit construction of triangle-free $n$-vertex graphs whose complement has orthogonality dimension over the binary field at most $n^{1-δ}$ for some constant $δ>0$. Our results involve constructions from the family of generalized Kneser graphs and they are motivated by the rigidity approach to circuit lower bounds. We use them to answer a couple of questions raised by Codenotti, Pudlák, and Resta (Theor. Comput. Sci., 2000), and in particular, to disprove their Odd Alternating Cycle Conjecture over every finite field.
FrameAxis: Characterizing Microframe Bias and Intensity with Word Embedding
Venue: arXiv cs.CL 2021
Year: 2021

Framing is a process of emphasizing a certain aspect of an issue over the others, nudging readers or listeners towards different positions on the issue even without making a biased argument. {Here, we propose FrameAxis, a method for characterizing documents by identifying the most relevant semantic axes ("microframes") that are overrepresented in the text using word embedding. Our unsupervised approach can be readily applied to large datasets because it does not require manual annotations. It can also provide nuanced insights by considering a rich set of semantic axes. FrameAxis is designed to quantitatively tease out two important dimensions of how microframes are used in the text. \textit{Microframe bias} captures how biased the text is on a certain microframe, and \textit{microframe intensity} shows how actively a certain microframe is used. Together, they offer a detailed characterization of the text. We demonstrate that microframes with the highest bias and intensity well align with sentiment, topic, and partisan spectrum by applying FrameAxis to multiple datasets from restaurant reviews to political news.} The existing domain knowledge can be incorporated into FrameAxis {by using custom microframes and by using FrameAxis as an iterative exploratory analysis instrument.} Additionally, we propose methods for explaining the results of FrameAxis at the level of individual words and documents. Our method may accelerate scalable and sophisticated computational analyses of framing across disciplines.
Do We Need Zero Training Loss After Achieving Zero Training Error?
Venue: arXiv cs.LG 2021
Year: 2021

Overparameterized deep networks have the capacity to memorize training data with zero \emph{training error}. Even after memorization, the \emph{training loss} continues to approach zero, making the model overconfident and the test performance degraded. Since existing regularizers do not directly aim to avoid zero training loss, it is hard to tune their hyperparameters in order to maintain a fixed/preset level of training loss. We propose a direct solution called \emph{flooding} that intentionally prevents further reduction of the training loss when it reaches a reasonably small value, which we call the \emph{flood level}. Our approach makes the loss float around the flood level by doing mini-batched gradient descent as usual but gradient ascent if the training loss is below the flood level. This can be implemented with one line of code and is compatible with any stochastic optimizer and other regularizers. With flooding, the model will continue to "random walk" with the same non-zero training loss, and we expect it to drift into an area with a flat loss landscape that leads to better generalization. We experimentally show that flooding improves performance and, as a byproduct, induces a double descent curve of the test loss.
Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor
Venue: arXiv cs.LG 2021
Year: 2021

In order to mitigate the high communication cost in distributed and federated learning, various vector compression schemes, such as quantization, sparsification and dithering, have become very popular. In designing a compression method, one aims to communicate as few bits as possible, which minimizes the cost per communication round, while at the same time attempting to impart as little distortion (variance) to the communicated messages as possible, which minimizes the adverse effect of the compression on the overall number of communication rounds. However, intuitively, these two goals are fundamentally in conflict: the more compression we allow, the more distorted the messages become. We formalize this intuition and prove an {\em uncertainty principle} for randomized compression operators, thus quantifying this limitation mathematically, and {\em effectively providing asymptotically tight lower bounds on what might be achievable with communication compression}. Motivated by these developments, we call for the search for the optimal compression operator. In an attempt to take a first step in this direction, we consider an unbiased compression method inspired by the Kashin representation of vectors, which we call {\em Kashin compression (KC)}. In contrast to all previously proposed compression mechanisms, KC enjoys a {\em dimension independent} variance bound for which we derive an explicit formula even in the regime when only a few bits need to be communicate per each vector entry.
Differential Privacy for Eye Tracking with Temporal Correlations
Venue: arXiv cs.CR 2021
Year: 2021

New generation head-mounted displays, such as VR and AR glasses, are coming into the market with already integrated eye tracking and are expected to enable novel ways of human-computer interaction in numerous applications. However, since eye movement properties contain biometric information, privacy concerns have to be handled properly. Privacy-preservation techniques such as differential privacy mechanisms have recently been applied to eye movement data obtained from such displays. Standard differential privacy mechanisms; however, are vulnerable due to temporal correlations between the eye movement observations. In this work, we propose a novel transform-coding based differential privacy mechanism to further adapt it to the statistics of eye movement feature data and compare various low-complexity methods. We extend the Fourier perturbation algorithm, which is a differential privacy mechanism, and correct a scaling mistake in its proof. Furthermore, we illustrate significant reductions in sample correlations in addition to query sensitivities, which provide the best utility-privacy trade-off in the eye tracking literature. Our results provide significantly high privacy without any essential loss in classification accuracies while hiding personal identifiers.
Optimal anytime regret with two experts
Venue: arXiv cs.LG 2021
Year: 2021

We consider the classical problem of prediction with expert advice. In the fixed-time setting, where the time horizon is known in advance, algorithms that achieve the optimal regret are known when there are two, three, or four experts or when the number of experts is large. Much less is known about the problem in the anytime setting, where the time horizon is not known in advance. No minimax optimal algorithm was previously known in the anytime setting, regardless of the number of experts. Even for the case of two experts, Luo and Schapire have left open the problem of determining the optimal algorithm. We design the first minimax optimal algorithm for minimizing regret in the anytime setting. We consider the case of two experts, and prove that the optimal regret is $γ\sqrt{t} / 2$ at all time steps $t$, where $γ$ is a natural constant that arose 35 years ago in studying fundamental properties of Brownian motion. The algorithm is designed by considering a continuous analogue of the regret problem, which is solved using ideas from stochastic calculus.
Scalable Second Order Optimization for Deep Learning
Venue: arXiv cs.LG 2021
Year: 2021

Optimization in machine learning, both theoretical and applied, is presently dominated by first-order gradient methods such as stochastic gradient descent. Second-order optimization methods, that involve second derivatives and/or second order statistics of the data, are far less prevalent despite strong theoretical properties, due to their prohibitive computation, memory and communication costs. In an attempt to bridge this gap between theoretical and practical optimization, we present a scalable implementation of a second-order preconditioned method (concretely, a variant of full-matrix Adagrad), that along with several critical algorithmic and numerical improvements, provides significant convergence and wall-clock time improvements compared to conventional first-order methods on state-of-the-art deep models. Our novel design effectively utilizes the prevalent heterogeneous hardware architecture for training deep models, consisting of a multicore CPU coupled with multiple accelerator units. We demonstrate superior performance compared to state-of-the-art on very large learning tasks such as machine translation with Transformers, language modeling with BERT, click-through rate prediction on Criteo, and image classification on ImageNet with ResNet-50.
Incremental Sampling Without Replacement for Sequence Models
Venue: arXiv cs.LG 2021
Year: 2021

Sampling is a fundamental technique, and sampling without replacement is often desirable when duplicate samples are not beneficial. Within machine learning, sampling is useful for generating diverse outputs from a trained model. We present an elegant procedure for sampling without replacement from a broad class of randomized programs, including generative neural models that construct outputs sequentially. Our procedure is efficient even for exponentially-large output spaces. Unlike prior work, our approach is incremental, i.e., samples can be drawn one at a time, allowing for increased flexibility. We also present a new estimator for computing expectations from samples drawn without replacement. We show that incremental sampling without replacement is applicable to many domains, e.g., program synthesis and combinatorial optimization.
Towards Fast Evaluation of Unsupervised Link Prediction by Random Sampling Unobserved Links
Venue: arXiv cs.SI 2021
Year: 2021

Link prediction has aroused extensive attention since it can both discover hidden connections and predict future links in the networks. Many unsupervised link prediction algorithms have been proposed to find these links in a variety of networks. However, there is an evaluation conundrum in unsupervised link prediction. Unobserved links heavily outnumber observed links in large networks, so it is unrealistic to quantify the existence likelihood of all unobserved links to evaluate these algorithms. In this paper, we propose a new evaluation paradigm that is sampling unobserved links to address this problem. First, we demonstrate that the proposed paradigm is feasible in theory. Then, we perform extensive evaluation experiments in real-world networks of different contexts and sizes. The results show that the performance of similarity-based link prediction algorithms is highly stable even at a low sampling ratio in large networks, and the evaluation time degradation caused by sampling is striking. Our findings have broad implications for link prediction.
An Accuracy-Lossless Perturbation Method for Defending Privacy Attacks in Federated Learning
Venue: arXiv cs.LG 2021
Year: 2021

Although federated learning improves privacy of training data by exchanging local gradients or parameters rather than raw data, the adversary still can leverage local gradients and parameters to obtain local training data by launching reconstruction and membership inference attacks. To defend such privacy attacks, many noises perturbation methods (like differential privacy or CountSketch matrix) have been widely designed. However, the strong defence ability and high learning accuracy of these schemes cannot be ensured at the same time, which will impede the wide application of FL in practice (especially for medical or financial institutions that require both high accuracy and strong privacy guarantee). To overcome this issue, in this paper, we propose \emph{an efficient model perturbation method for federated learning} to defend reconstruction and membership inference attacks launched by curious clients. On the one hand, similar to the differential privacy, our method also selects random numbers as perturbed noises added to the global model parameters, and thus it is very efficient and easy to be integrated in practice. Meanwhile, the random selected noises are positive real numbers and the corresponding value can be arbitrarily large, and thus the strong defence ability can be ensured. On the other hand, unlike differential privacy or other perturbation methods that cannot eliminate the added noises, our method allows the server to recover the true gradients by eliminating the added noises. Therefore, our method does not hinder learning accuracy at all.
Optimal Advertising for Information Products
Venue: arXiv cs.GT 2021
Year: 2021

When selling information products, the seller can provide some free partial information to change people's valuations so that the overall revenue can possibly be increased. We study the general problem of advertising information products by revealing partial information. We consider buyers who are decision-makers. The outcomes of the decision problems depend on the state of the world that is unknown to the buyers. The buyers can make their own observations and thus can hold different personal beliefs about the state of the world. There is an information seller who has access to the state of the world. The seller can promote the information by revealing some partial information. We assume that the seller chooses a long-term advertising strategy and then commits to it. The seller's goal is to maximize the expected revenue. We study the problem in two settings. (1) The seller targets buyers of a certain type. In this case, finding the optimal advertising strategy is equivalent to finding the concave closure of a simple function. The function is a product of two quantities, the likelihood ratio and the cost of uncertainty. Based on this observation, we prove some properties of the optimal mechanism, which allow us to solve for the optimal mechanism by a finite-size convex program. The convex program will have a polynomial-size if the state of the world has a constant number of possible realizations or the buyers face a decision problem with a constant number of options. For the general problem, we prove that it is NP-hard to find the optimal mechanism. (2) When the seller faces buyers of different types and only knows the distribution of their types, we provide an approximation algorithm when it is not too hard to predict the possible type of buyers who will make the purchase. For the general problem, we prove that it is NP-hard to find a constant-factor approximation.
Parallel Clique Counting and Peeling Algorithms
Venue: arXiv cs.DS 2021
Year: 2021

We present a new parallel algorithm for $k$-clique counting/listing that has polylogarithmic span (parallel time) and is work-efficient (matches the work of the best sequential algorithm) for sparse graphs. Our algorithm is based on computing low out-degree orientations, which we present new linear-work and polylogarithmic-span algorithms for computing in parallel. We also present new parallel algorithms for producing unbiased estimations of clique counts using graph sparsification. Finally, we design two new parallel work-efficient algorithms for approximating the $k$-clique densest subgraph, the first of which is a $1/k$-approximation and the second of which is a $1/(k(1+ε))$-approximation and has polylogarithmic span. Our first algorithm does not have polylogarithmic span, but we prove that it solves a P-complete problem. In addition to the theoretical results, we also implement the algorithms and propose various optimizations to improve their practical performance. On a 30-core machine with two-way hyper-threading, our algorithms achieve 13.23--38.99x and 1.19--13.76x self-relative parallel speedup for $k$-clique counting and $k$-clique densest subgraph, respectively. Compared to the state-of-the-art parallel $k$-clique counting algorithms, we achieve up to 9.88x speedup, and compared to existing implementations of $k$-clique densest subgraph, we achieve up to 11.83x speedup. We are able to compute the $4$-clique counts on the largest publicly-available graph with over two hundred billion edges for the first time.
Robust Learning-Based Control via Bootstrapped Multiplicative Noise
Venue: arXiv cs.LG 2021
Year: 2021

Despite decades of research and recent progress in adaptive control and reinforcement learning, there remains a fundamental lack of understanding in designing controllers that provide robustness to inherent non-asymptotic uncertainties arising from models estimated with finite, noisy data. We propose a robust adaptive control algorithm that explicitly incorporates such non-asymptotic uncertainties into the control design. The algorithm has three components: (1) a least-squares nominal model estimator; (2) a bootstrap resampling method that quantifies non-asymptotic variance of the nominal model estimate; and (3) a non-conventional robust control design method using an optimal linear quadratic regulator (LQR) with multiplicative noise. A key advantage of the proposed approach is that the system identification and robust control design procedures both use stochastic uncertainty representations, so that the actual inherent statistical estimation uncertainty directly aligns with the uncertainty the robust controller is being designed against. We show through numerical experiments that the proposed robust adaptive controller can significantly outperform the certainty equivalent controller on both expected regret and measures of regret risk.
Millimeter Wave Communications with an Intelligent Reflector: Performance Optimization and Distributional Reinforcement Learning
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, a novel framework is proposed to optimize the downlink multi-user communication of a millimeter wave base station, which is assisted by a reconfigurable intelligent reflector (IR). In particular, a channel estimation approach is developed to measure the channel state information (CSI) in real-time. First, for a perfect CSI scenario, the precoding transmission of the BS and the reflection coefficient of the IR are jointly optimized, via an iterative approach, so as to maximize the sum of downlink rates towards multiple users. Next, in the imperfect CSI scenario, a distributional reinforcement learning (DRL) approach is proposed to learn the optimal IR reflection and maximize the expectation of downlink capacity. In order to model the transmission rate's probability distribution, a learning algorithm, based on quantile regression (QR), is developed, and the proposed QR-DRL method is proved to converge to a stable distribution of downlink transmission rate. Simulation results show that, in the error-free CSI scenario, the proposed approach yields over 30% and 2-fold increase in the downlink sum-rate, compared with a fixed IR reflection scheme and direct transmission scheme, respectively. Simulation results also show that by deploying more IR elements, the downlink sum-rate can be significantly improved. However, as the number of IR components increases, more time is required for channel estimation, and the slope of increase in the IR-aided transmission rate will become smaller. Furthermore, under limited knowledge of CSI, simulation results show that the proposed QR-DRL method, which learns a full distribution of the downlink rate, yields a better prediction accuracy and improves the downlink rate by 10% for online deployments, compared with a Q-learning baseline.
Is The Leader Robot an Adequate Sensor for Posture Estimation and Ergonomic Assessment of A Human Teleoperator?
Venue: arXiv cs.RO 2021
Year: 2021

Ergonomic assessment of human posture plays a vital role in understanding work-related safety and health. Current posture estimation approaches face occlusion challenges in teleoperation and physical human-robot interaction. We investigate if the leader robot is an adequate sensor for posture estimation in teleoperation and we introduce a new probabilistic approach that relies solely on the trajectory of the leader robot for generating observations. We model the human using a redundant, partially-observable dynamical system and we infer the posture using a standard particle filter. We compare our approach with postures from a commercial motion capture system and also two least-squares optimization approaches for human inverse kinematics. The results reveal that the proposed approach successfully estimates human postures and ergonomic risk scores comparable to those estimates from gold-standard motion capture.
Separating the Effects of Batch Normalization on CNN Training Speed and Stability Using Classical Adaptive Filter Theory
Venue: arXiv cs.NE 2021
Year: 2021

Batch Normalization (BatchNorm) is commonly used in Convolutional Neural Networks (CNNs) to improve training speed and stability. However, there is still limited consensus on why this technique is effective. This paper uses concepts from the traditional adaptive filter domain to provide insight into the dynamics and inner workings of BatchNorm. First, we show that the convolution weight updates have natural modes whose stability and convergence speed are tied to the eigenvalues of the input autocorrelation matrices, which are controlled by BatchNorm through the convolution layers' channel-wise structure. Furthermore, our experiments demonstrate that the speed and stability benefits are distinct effects. At low learning rates, it is BatchNorm's amplification of the smallest eigenvalues that improves convergence speed, while at high learning rates, it is BatchNorm's suppression of the largest eigenvalues that ensures stability. Lastly, we prove that in the first training step, when normalization is needed most, BatchNorm satisfies the same optimization as Normalized Least Mean Square (NLMS), while it continues to approximate this condition in subsequent steps. The analyses provided in this paper lay the groundwork for gaining further insight into the operation of modern neural network structures using adaptive filter theory.