Search

Fast changing states or volatile environments pose a significant challenge to online optimization, which needs to perform rapid adaptation under limited observation. In this paper, we give query and regret optimal bandit algorithms under the strict notion of strongly adaptive regret, which measures the maximum regret over any contiguous interval $I$. Due to its worst-case nature, there is an almost-linear $\Omega(|I|^{1-\epsilon})$ regret lower bound, when only one query per round is allowed [Daniely el al, ICML 2015]. Surprisingly, with just two queries per round, we give Strongly Adaptive Bandit Learner (StABL) that achieves $\tilde{O}(\sqrt{n|I|})$ adaptive regret for multi-armed bandits with $n$ arms. The bound is tight and cannot be improved in general. Our algorithm leverages a multiplicative update scheme of varying stepsizes and a carefully chosen observation distribution to control the variance. Furthermore, we extend our results and provide optimal algorithms in the bandit convex optimization setting. Finally, we empirically demonstrate the superior performance of our algorithms under volatile environments and for downstream tasks, such as algorithm selection for hyperparameter optimization., Comment: ICLR2024

Preference learning algorithms (e.g., RLHF and DPO) are frequently used to steer LLMs to produce generations that are more preferred by humans, but our understanding of their inner workings is still limited. In this work, we study the conventional wisdom that preference learning trains models to assign higher likelihoods to more preferred outputs than less preferred outputs, measured via $\textit{ranking accuracy}$. Surprisingly, we find that most state-of-the-art preference-tuned models achieve a ranking accuracy of less than 60% on common preference datasets. We furthermore derive the $\textit{idealized ranking accuracy}$ that a preference-tuned LLM would achieve if it optimized the DPO or RLHF objective perfectly. We demonstrate that existing models exhibit a significant $\textit{alignment gap}$ -- $\textit{i.e.}$, a gap between the observed and idealized ranking accuracies. We attribute this discrepancy to the DPO objective, which is empirically and theoretically ill-suited to fix even mild ranking errors in the reference model, and derive a simple and efficient formula for quantifying the difficulty of learning a given preference datapoint. Finally, we demonstrate that ranking accuracy strongly correlates with the empirically popular win rate metric when the model is close to the reference model used in the objective, shedding further light on the differences between on-policy (e.g., RLHF) and off-policy (e.g., DPO) preference learning algorithms.

We study dynamic algorithms robust to adaptive input generated from sources with bounded capabilities, such as sparsity or limited interaction. For example, we consider robust linear algebraic algorithms when the updates to the input are sparse but given by an adversary with access to a query oracle. We also study robust algorithms in the standard centralized setting, where an adversary queries an algorithm in an adaptive manner, but the number of interactions between the adversary and the algorithm is bounded. We first recall a unified framework of [HKM+20, BKM+22, ACSS23] for answering $Q$ adaptive queries that incurs $\widetilde{\mathcal{O}}(\sqrt{Q})$ overhead in space, which is roughly a quadratic improvement over the na\"{i}ve implementation, and only incurs a logarithmic overhead in query time. Although the general framework has diverse applications in machine learning and data science, such as adaptive distance estimation, kernel density estimation, linear regression, range queries, and point queries and serves as a preliminary benchmark, we demonstrate even better algorithmic improvements for (1) reducing the pre-processing time for adaptive distance estimation and (2) permitting an unlimited number of adaptive queries for kernel density estimation. Finally, we complement our theoretical results with additional empirical evaluations.

Recent works in dimensionality reduction for regression tasks have introduced the notion of sensitivity, an estimate of the importance of a specific datapoint in a dataset, offering provable guarantees on the quality of the approximation after removing low-sensitivity datapoints via subsampling. However, fast algorithms for approximating $\ell_p$ sensitivities, which we show is equivalent to approximate $\ell_p$ regression, are known for only the $\ell_2$ setting, in which they are termed leverage scores. In this work, we provide efficient algorithms for approximating $\ell_p$ sensitivities and related summary statistics of a given matrix. In particular, for a given $n \times d$ matrix, we compute $\alpha$-approximation to its $\ell_1$ sensitivities at the cost of $O(n/\alpha)$ sensitivity computations. For estimating the total $\ell_p$ sensitivity (i.e. the sum of $\ell_p$ sensitivities), we provide an algorithm based on importance sampling of $\ell_p$ Lewis weights, which computes a constant factor approximation to the total sensitivity at the cost of roughly $O(\sqrt{d})$ sensitivity computations. Furthermore, we estimate the maximum $\ell_1$ sensitivity, up to a $\sqrt{d}$ factor, using $O(d)$ sensitivity computations. We generalize all these results to $\ell_p$ norms for $p > 1$. Lastly, we experimentally show that for a wide class of matrices in real-world datasets, the total sensitivity can be quickly approximated and is significantly smaller than the theoretical prediction, demonstrating that real-world datasets have low intrinsic effective dimensionality.

Biological and artificial information processing systems form representations that they can use to categorize, reason, plan, navigate, and make decisions. How can we measure the extent to which the representations formed by these diverse systems agree? Do similarities in representations then translate into similar behavior? How can a system's representations be modified to better match those of another system? These questions pertaining to the study of representational alignment are at the heart of some of the most active research areas in cognitive science, neuroscience, and machine learning. For example, cognitive scientists measure the representational alignment of multiple individuals to identify shared cognitive priors, neuroscientists align fMRI responses from multiple individuals into a shared representational space for group-level analyses, and ML researchers distill knowledge from teacher models into student models by increasing their alignment. Unfortunately, there is limited knowledge transfer between research communities interested in representational alignment, so progress in one field often ends up being rediscovered independently in another. Thus, greater cross-field communication would be advantageous. To improve communication between these fields, we propose a unifying framework that can serve as a common language between researchers studying representational alignment. We survey the literature from all three fields and demonstrate how prior work fits into this framework. Finally, we lay out open problems in representational alignment where progress can benefit all three of these fields. We hope that our work can catalyze cross-disciplinary collaboration and accelerate progress for all communities studying and developing information processing systems. We note that this is a working paper and encourage readers to reach out with their suggestions for future revisions., Comment: Working paper, changes to be made in upcoming revisions

Scalarization is a general technique that can be deployed in any multiobjective setting to reduce multiple objectives into one, such as recently in RLHF for training reward models that align human preferences. Yet some have dismissed this classical approach because linear scalarizations are known to miss concave regions of the Pareto frontier. To that end, we aim to find simple non-linear scalarizations that can explore a diverse set of $k$ objectives on the Pareto frontier, as measured by the dominated hypervolume. We show that hypervolume scalarizations with uniformly random weights are surprisingly optimal for provably minimizing the hypervolume regret, achieving an optimal sublinear regret bound of $O(T^{-1/k})$, with matching lower bounds that preclude any algorithm from doing better asymptotically. As a theoretical case study, we consider the multiobjective stochastic linear bandits problem and demonstrate that by exploiting the sublinear regret bounds of the hypervolume scalarizations, we can derive a novel non-Euclidean analysis that produces improved hypervolume regret bounds of $\tilde{O}( d T^{-1/2} + T^{-1/k})$. We support our theory with strong empirical performance of using simple hypervolume scalarizations that consistently outperforms both the linear and Chebyshev scalarizations, as well as standard multiobjective algorithms in bayesian optimization, such as EHVI., Comment: New version coming

Model overconfidence and poor calibration are common in machine learning and difficult to account for when applying standard empirical risk minimization. In this work, we propose a novel method to alleviate these problems that we call odd-$k$-out learning (OKO), which minimizes the cross-entropy error for sets rather than for single examples. This naturally allows the model to capture correlations across data examples and achieves both better accuracy and calibration, especially in limited training data and class-imbalanced regimes. Perhaps surprisingly, OKO often yields better calibration even when training with hard labels and dropping any additional calibration parameter tuning, such as temperature scaling. We demonstrate this in extensive experimental analyses and provide a mathematical theory to interpret our findings. We emphasize that OKO is a general framework that can be easily adapted to many settings and a trained model can be applied to single examples at inference time, without significant run-time overhead or architecture changes., Comment: Published as a conference paper at ICLR 2024

We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly, such as during an optimization process. Specifically, for any $m$ matrices $A_1,...,A_m$ with consecutive differences bounded in Schatten-$1$ norm by $\alpha$, we provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $\epsilon$ error with $\delta$ failure probability with an optimal query complexity of $\widetilde{O}\left(m \alpha\sqrt{\log(1/\delta)}/\epsilon + m\log(1/\delta)\right)$, improving the dependence on both $\alpha$ and $\delta$ from Dharangutte and Musco (NeurIPS, 2021). Our procedure works without additional norm bounds on $A_i$ and can be generalized to a bound for the $p$-th Schatten norm for $p \in [1,2]$, giving a complexity of $\widetilde{O}\left(m \alpha\left(\sqrt{\log(1/\delta)}/\epsilon\right)^p +m \log(1/\delta)\right)$. By using novel reductions to communication complexity and information-theoretic analyses of Gaussian matrices, we provide matching lower bounds for static and dynamic trace estimation in all relevant parameters, including the failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation, resolving open questions of prior work., Comment: 30 pages

Meta-learning hyperparameter optimization (HPO) algorithms from prior experiments is a promising approach to improve optimization efficiency over objective functions from a similar distribution. However, existing methods are restricted to learning from experiments sharing the same set of hyperparameters. In this paper, we introduce the OptFormer, the first text-based Transformer HPO framework that provides a universal end-to-end interface for jointly learning policy and function prediction when trained on vast tuning data from the wild, such as Google's Vizier database, one of the world's largest HPO datasets. Our extensive experiments demonstrate that the OptFormer can simultaneously imitate at least 7 different HPO algorithms, which can be further improved via its function uncertainty estimates. Compared to a Gaussian Process, the OptFormer also learns a robust prior distribution for hyperparameter response functions, and can thereby provide more accurate and better calibrated predictions. This work paves the path to future extensions for training a Transformer-based model as a general HPO optimizer., Comment: Published as a conference paper in Neural Information Processing Systems (NeurIPS) 2022. Code can be found in https://github.com/google-research/optformer and Google AI Blog can be found in https://ai.googleblog.com/2022/08/optformer-towards-universal.html

Interior point methods (IPM) are first introduced as an efficient polynomial time algorithm to solve linear programs. Since then, they have enjoyed success in general convex optimization with the introduction of self-concordant barriers, replacing the ellipsoid method as the optimizer of choice in many settings. As compared to the ellipsoid method, interior point methods boast a better runtime complexity due to its $O(\sqrt{n})$ iteration complexity, where each iteration requires a linear system solve for the Newton step computation. This implies a naive $O(n^{0.5+\omega})$ total runtime for IPMs, where $\omega$ is the exponent of matrix multiplication.In a recent breakthrough work, [Cohen, Lee, Song'18] showed that we can solve linear programs in the IPM framework in current matrix multiplication time $\widetilde{O}(n^{\omega})$, implying that linear programs are computationally not much harder than matrix inversion. In this thesis, we extend this result to general Empirical Risk Minimization (ERM), showing that many convex optimization problems can be solved as efficiently as matrix inversion.Specifically, many convex problems in machine learning and computer science share the same form: \begin{align*} \min_{x} \sum_{i} f_i( A_i x + b_i), \end{align*}where $f_i$ are convex functions on $\R^{n_i}$ with constant $n_i$, $A_i \in \R^{n_i \times d}$, $b_i \in \R^{n_i}$ and $\sum_i n_i = n$. This problem generalizes linear programming and we give an algorithm that runs in time\begin{align*}O^* ( ( n^{\omega} + n^{2.5 - \alpha/2} + n^{2+ 1/6} ) \log (1 / \delta) )\end{align*}where $\alpha$ is the dual exponent of matrix multiplication, and $\delta$ is the relative accuracy, and $O^*$ hides sub-polynomial terms. Note that the runtime has only a log dependence on the condition numbers or other data dependent parameters and these are captured in $\delta$. For the current bound $\omega \sim 2.38$ and $\alpha \sim 0.31$, our runtime $O^* ( n^{\omega} \log (n / \delta))$ match

Interior point methods (IPM) are first introduced as an efficient polynomial time algorithm to solve linear programs. Since then, they have enjoyed success in general convex optimization with the introduction of self-concordant barriers, replacing the ellipsoid method as the optimizer of choice in many settings. As compared to the ellipsoid method, interior point methods boast a better runtime complexity due to its $O(\sqrt{n})$ iteration complexity, where each iteration requires a linear system solve for the Newton step computation. This implies a naive $O(n^{0.5+\omega})$ total runtime for IPMs, where $\omega$ is the exponent of matrix multiplication.In a recent breakthrough work, [Cohen, Lee, Song'18] showed that we can solve linear programs in the IPM framework in current matrix multiplication time $\widetilde{O}(n^{\omega})$, implying that linear programs are computationally not much harder than matrix inversion. In this thesis, we extend this result to general Empirical Risk Minimization (ERM), showing that many convex optimization problems can be solved as efficiently as matrix inversion.Specifically, many convex problems in machine learning and computer science share the same form: \begin{align*} \min_{x} \sum_{i} f_i( A_i x + b_i), \end{align*}where $f_i$ are convex functions on $\R^{n_i}$ with constant $n_i$, $A_i \in \R^{n_i \times d}$, $b_i \in \R^{n_i}$ and $\sum_i n_i = n$. This problem generalizes linear programming and we give an algorithm that runs in time\begin{align*}O^* ( ( n^{\omega} + n^{2.5 - \alpha/2} + n^{2+ 1/6} ) \log (1 / \delta) )\end{align*}where $\alpha$ is the dual exponent of matrix multiplication, and $\delta$ is the relative accuracy, and $O^*$ hides sub-polynomial terms. Note that the runtime has only a log dependence on the condition numbers or other data dependent parameters and these are captured in $\delta$. For the current bound $\omega \sim 2.38$ and $\alpha \sim 0.31$, our runtime $O^* ( n^{\omega} \log (n / \delta))$ match

Can deep learning solve multiple tasks simultaneously, even when they are unrelated and very different? We investigate how the representations of the underlying tasks affect the ability of a single neural network to learn them jointly. We present theoretical and empirical findings that a single neural network is capable of simultaneously learning multiple tasks from a combined data set, for a variety of methods for representing tasks -- for example, when the distinct tasks are encoded by well-separated clusters or decision trees over certain task-code attributes. More concretely, we present a novel analysis that shows that families of simple programming-like constructs for the codes encoding the tasks are learnable by two-layer neural networks with standard training. We study more generally how the complexity of learning such combined tasks grows with the complexity of the task codes; we find that combining many tasks may incur a sample complexity penalty, even though the individual tasks are easy to learn. We provide empirical support for the usefulness of the learning bounds by training networks on clusters, decision trees, and SQL-style aggregation., Comment: 30 pages, 6 figures

In this paper, we approach the problem of optimizing blackbox functions over large hybrid search spaces consisting of both combinatorial and continuous parameters. We demonstrate that previous evolutionary algorithms which rely on mutation-based approaches, while flexible over combinatorial spaces, suffer from a curse of dimensionality in high dimensional continuous spaces both theoretically and empirically, which thus limits their scope over hybrid search spaces as well. In order to combat this curse, we propose ES-ENAS, a simple and modular joint optimization procedure combining the class of sample-efficient smoothed gradient techniques, commonly known as Evolutionary Strategies (ES), with combinatorial optimizers in a highly scalable and intuitive way, inspired by the one-shot or supernet paradigm introduced in Efficient Neural Architecture Search (ENAS). By doing so, we achieve significantly more sample efficiency, which we empirically demonstrate over synthetic benchmarks, and are further able to apply ES-ENAS for architecture search over popular RL benchmarks., Comment: Previously published at ICLR 2020 NAS Workshop. See https://github.com/google-research/google-research/tree/master/es_enas for associated code

Single-objective black box optimization (also known as zeroth-order optimization) is the process of minimizing a scalar objective $f(x)$, given evaluations at adaptively chosen inputs $x$. In this paper, we consider multi-objective optimization, where $f(x)$ outputs a vector of possibly competing objectives and the goal is to converge to the Pareto frontier. Quantitatively, we wish to maximize the standard hypervolume indicator metric, which measures the dominated hypervolume of the entire set of chosen inputs. In this paper, we introduce a novel scalarization function, which we term the hypervolume scalarization, and show that drawing random scalarizations from an appropriately chosen distribution can be used to efficiently approximate the hypervolume indicator metric. We utilize this connection to show that Bayesian optimization with our scalarization via common acquisition functions, such as Thompson Sampling or Upper Confidence Bound, provably converges to the whole Pareto frontier by deriving tight hypervolume regret bounds on the order of $\widetilde{O}(\sqrt{T})$. Furthermore, we highlight the general utility of our scalarization framework by showing that any provably convergent single-objective optimization process can be effortlessly converted to a multi-objective optimization process with provable convergence guarantees., Comment: ICML 2020

The tremendous success of deep neural networks has motivated the need to better understand the fundamental properties of these networks, but many of the theoretical results proposed have only been for shallow networks. In this paper, we study an important primitive for understanding the meaningful input space of a deep network: span recovery. For $k

Large neural network models have been successful in learning functions of importance in many branches of science, including physics, chemistry and biology. Recent theoretical work has shown explicit learning bounds for wide networks and kernel methods on some simple classes of functions, but not on more complex functions which arise in practice. We extend these techniques to provide learning bounds for analytic functions on the sphere for any kernel method or equivalent infinitely-wide network with the corresponding activation function trained with SGD. We show that a wide, one-hidden layer ReLU network can learn analytic functions with a number of samples proportional to the derivative of a related function. Many functions important in the sciences are therefore efficiently learnable. As an example, we prove explicit bounds on learning the many-body gravitational force function given by Newton's law of gravitation. Our theoretical bounds suggest that very wide ReLU networks (and the corresponding NTK kernel) are better at learning analytic functions as compared to kernel learning with Gaussian kernels. We present experimental evidence that the many-body gravitational force function is easier to learn with ReLU networks as compared to networks with exponential activations.

Zeroth-order optimization is the process of minimizing an objective $f(x)$, given oracle access to evaluations at adaptively chosen inputs $x$. In this paper, we present two simple yet powerful GradientLess Descent (GLD) algorithms that do not rely on an underlying gradient estimate and are numerically stable. We analyze our algorithm from a novel geometric perspective and present a novel analysis that shows convergence within an $\epsilon$-ball of the optimum in $O(kQ\log(n)\log(R/\epsilon))$ evaluations, for any monotone transform of a smooth and strongly convex objective with latent dimension $k < n$, where the input dimension is $n$, $R$ is the diameter of the input space and $Q$ is the condition number. Our rates are the first of its kind to be both 1) poly-logarithmically dependent on dimensionality and 2) invariant under monotone transformations. We further leverage our geometric perspective to show that our analysis is optimal. Both monotone invariance and its ability to utilize a low latent dimensionality are key to the empirical success of our algorithms, as demonstrated on BBOB and MuJoCo benchmarks., Comment: 11 main pages, 26 total pages

The classical low rank approximation problem is to find a rank $k$ matrix $UV$ (where $U$ has $k$ columns and $V$ has $k$ rows) that minimizes the Frobenius norm of $A - UV$. Although this problem can be solved efficiently, we study an NP-hard variant of this problem that involves weights and regularization. A previous paper of [Razenshteyn et al. '16] derived a polynomial time algorithm for weighted low rank approximation with constant rank. We derive provably sharper guarantees for the regularized version by obtaining parameterized complexity bounds in terms of the statistical dimension rather than the rank, allowing for a rank-independent runtime that can be significantly faster. Our improvement comes from applying sharper matrix concentration bounds, using a novel conditioning technique, and proving structural theorems for regularized low rank problems.

Many convex problems in machine learning and computer science share the same form: \begin{align*} \min_{x} \sum_{i} f_i( A_i x + b_i), \end{align*} where $f_i$ are convex functions on $\mathbb{R}^{n_i}$ with constant $n_i$, $A_i \in \mathbb{R}^{n_i \times d}$, $b_i \in \mathbb{R}^{n_i}$ and $\sum_i n_i = n$. This problem generalizes linear programming and includes many problems in empirical risk minimization. In this paper, we give an algorithm that runs in time \begin{align*} O^* ( ( n^{\omega} + n^{2.5 - \alpha/2} + n^{2+ 1/6} ) \log (n / \delta) ) \end{align*} where $\omega$ is the exponent of matrix multiplication, $\alpha$ is the dual exponent of matrix multiplication, and $\delta$ is the relative accuracy. Note that the runtime has only a log dependence on the condition numbers or other data dependent parameters and these are captured in $\delta$. For the current bound $\omega \sim 2.38$ [Vassilevska Williams'12, Le Gall'14] and $\alpha \sim 0.31$ [Le Gall, Urrutia'18], our runtime $O^* ( n^{\omega} \log (n / \delta))$ matches the current best for solving a dense least squares regression problem, a special case of the problem we consider. Very recently, [Alman'18] proved that all the current known techniques can not give a better $\omega$ below $2.168$ which is larger than our $2+1/6$. Our result generalizes the very recent result of solving linear programs in the current matrix multiplication time [Cohen, Lee, Song'19] to a more broad class of problems. Our algorithm proposes two concepts which are different from [Cohen, Lee, Song'19] : $\bullet$ We give a robust deterministic central path method, whereas the previous one is a stochastic central path which updates weights by a random sparse vector. $\bullet$ We propose an efficient data-structure to maintain the central path of interior point methods even when the weights update vector is dense.

Absolute fast converging (AFC) phylogeny estimation methods are ones that have been proven to recover the true tree with high probability given sequences whose lengths are polynomial in the number of number of leaves in the tree (once the shortest and longest branch lengths are fixed). While there has been a large literature on AFC methods, the best in terms of empirical performance was DCM_NJ, published in SODA 2001. The main empirical advantage of DCM_NJ over other AFC methods is its use of neighbor joining (NJ) to construct trees on smaller taxon subsets, which are then combined into a tree on the full set of species using a supertree method; in contrast, the other AFC methods in essence depend on quartet trees that are computed independently of each other, which reduces accuracy compared to neighbor joining. However, DCM_NJ is unlikely to scale to large datasets due to its reliance on supertree methods, as no current supertree methods are able to scale to large datasets with high accuracy. In this study we present a new approach to large-scale phylogeny estimation that shares some of the features of DCM_NJ but bypasses the use of supertree methods. We prove that this new approach is AFC and uses polynomial time. Furthermore, we describe variations on this basic approach that can be used with leaf-disjoint constraint trees (computed using methods such as maximum likelihood) to produce other AFC methods that are likely to provide even better accuracy. Thus, we present a new generalizable technique for large-scale tree estimation that is designed to improve scalability for phylogeny estimation methods to ultra-large datasets, and that can be used in a variety of settings (including tree estimation from unaligned sequences, and species tree estimation from gene trees).

We study whether a depth two neural network can learn another depth two network using gradient descent. Assuming a linear output node, we show that the question of whether gradient descent converges to the target function is equivalent to the following question in electrodynamics: Given k fixed protons in R^d, and k electrons, each moving due to the attractive force from the protons and repulsive force from the remaining electrons, whether at equilibrium all the electrons will be matched up with the protons, up to a permutation. Under the standard electrical force, this follows from the classic Earnshaw's theorem. In our setting, the force is determined by the activation function and the input distribution. Building on this equivalence, we prove the existence of an activation function such that gradient descent learns at least one of the hidden nodes in the target network. Iterating, we show that gradient descent can be used to learn the entire network one node at a time.

B cell activation during normal immune responses and oncogenic transformation impose increased metabolic demands on B cells and their ability to retain redox homeostasis. While the serine/threonine-protein phosphatase 2A (PP2A) was identified as a tumor suppressor in multiple types of cancer, our genetic studies revealed an essential role of PP2A in B cell tumors. Thereby, PP2A redirects glucose carbon utilization from glycolysis to the pentose phosphate pathway (PPP) to salvage oxidative stress. This unique vulnerability reflects constitutively low PPP activity in B cells and transcriptional repression of G6PD and other key PPP enzymes by the B cell transcription factors PAX5 and IKZF1. Reflecting B-cell-specific transcriptional PPP-repression, glucose carbon utilization in B cells is heavily skewed in favor of glycolysis resulting in lack of PPP-dependent antioxidant protection. These findings reveal a gatekeeper function of the PPP in a broad range of B cell malignancies that can be efficiently targeted by small molecule inhibition of PP2A and G6PD.

Absolute fast converging (AFC) phylogeny estimation methods are ones that have been proven to recover the true tree with high probability given sequences whose lengths are polynomial in the number of number of leaves in the tree (once the shortest and longest branch lengths are fixed). While there has been a large literature on AFC methods, the best in terms of empirical performance was DCM_NJ, published in SODA 2001. The main empirical advantage of DCM_NJ over other AFC methods is its use of neighbor joining (NJ) to construct trees on smaller taxon subsets, which are then combined into a tree on the full set of species using a supertree method; in contrast, the other AFC methods in essence depend on quartet trees that are computed independently of each other, which reduces accuracy compared to neighbor joining. However, DCM_NJ is unlikely to scale to large datasets due to its reliance on supertree methods, as no current supertree methods are able to scale to large datasets with high accuracy. In this study we present a new approach to large-scale phylogeny estimation that shares some of the features of DCM_NJ but bypasses the use of supertree methods. We prove that this new approach is AFC and uses polynomial time. Furthermore, we describe variations on this basic approach that can be used with leaf-disjoint constraint trees (computed using methods such as maximum likelihood) to produce other AFC methods that are likely to provide even better accuracy. Thus, we present a new generalizable technique for large-scale tree estimation that is designed to improve scalability for phylogeny estimation methods to ultra-large datasets, and that can be used in a variety of settings (including tree estimation from unaligned sequences, and species tree estimation from gene trees).

We study whether a depth two neural network can learn another depth two network using gradient descent. Assuming a linear output node, we show that the question of whether gradient descent converges to the target function is equivalent to the following question in electrodynamics: Given k fixed protons in R^d, and k electrons, each moving due to the attractive force from the protons and repulsive force from the remaining electrons, whether at equilibrium all the electrons will be matched up with the protons, up to a permutation. Under the standard electrical force, this follows from the classic Earnshaw's theorem. In our setting, the force is determined by the activation function and the input distribution. Building on this equivalence, we prove the existence of an activation function such that gradient descent learns at least one of the hidden nodes in the target network. Iterating, we show that gradient descent can be used to learn the entire network one node at a time.

We consider the phylogenetic tree reconstruction problem with insertions and deletions (indels). Phylogenetic algorithms proceed under a model where sequences evolve down the model tree, and given sequences at the leaves, the problem is to reconstruct the model tree with high probability. Traditionally, sequences mutate by substitution-only processes, although some recent work considers evolutionary processes with insertions and deletions. In this paper, we improve on previous work by giving a reconstruction algorithm that simultaneously has $O(\text{poly} \log n)$ sequence length and tolerates constant indel probabilities on each edge. Our recursively-reconstructed distance-based technique provably outputs the model tree when the model tree has $O(\text{poly} \log n)$ diameter and discretized branch lengths, allowing for the probability of insertion and deletion to be non-uniform and asymmetric on each edge. Our polylogarithmic sequence length bounds improve significantly over previous polynomial sequence length bounds and match sequence length bounds in the substitution-only models of phylogenetic evolution, thereby challenging the idea that many global misalignments caused by insertions and deletions when $p_{indel}$ is large are a fundamental obstruction to reconstruction with short sequences., Comment: Update: Many minor edits to improve clarity and presentation as suggested by STOC reviewers. The results and overall structure of the paper are unaffected. To appear in STOC 2019

We study whether a depth two neural network can learn another depth two network using gradient descent. Assuming a linear output node, we show that the question of whether gradient descent converges to the target function is equivalent to the following question in electrodynamics: Given $k$ fixed protons in $\mathbb{R}^d,$ and $k$ electrons, each moving due to the attractive force from the protons and repulsive force from the remaining electrons, whether at equilibrium all the electrons will be matched up with the protons, up to a permutation. Under the standard electrical force, this follows from the classic Earnshaw's theorem. In our setting, the force is determined by the activation function and the input distribution. Building on this equivalence, we prove the existence of an activation function such that gradient descent learns at least one of the hidden nodes in the target network. Iterating, we show that gradient descent can be used to learn the entire network one node at a time., Comment: in ITCS 2018

[ES] En el laboratorio hemos generado mutantes que modulan la dinámica de agregación de péptidos que contienen expansiones de 40 glutaminas en gusanos nematodos C. elegans (Cepa AM141; genotipo-rmIs133[unc-54p::40Q::YFP] Morley et al., PNAS 2002). Esta cepa presente un fenotipo de agregación de las poliglutaminas dependiente de la edad. Los individuos jóvenes apenas presentan agregados, mientras que los adultos los producen en abundancia. En el presente trabajo caracterizaremos el papel modulador de la agregación de estas poliglutaminas del gen unc-1 del gusano, que tiene homología con el gen humano stomatin-like protein 3 (STOML3). Gusanos portadores de un alelo de pérdida total de función de este gen (unc-1(vlt10)) tienen agravado el fenotipo de agregación de péptidos 40Q::YFP. Este fenotipo es cuantificable porque los agregados colapsan en cuerpos de inclusión que son fácilmente observados en un estereoscopio equipado con fluorescencia. Para demostrar que la pérdida de función de unc-1 produce este fenotipo introduciremos en AM141 otros alelos caracterizados del gen, y disponibles en el repositorio de cepas de gusano (Caenorhabditis Genetics Center). Además emplearemos RNAi para silenciar el gen y dar más robustez a los experimentos descritos arriba. Todo esto sentará las bases para una futura búsqueda del mecanismo por el cual el gen modula la agregación de poliglutaminas., [EN] Huntington’s disease (HD) is a rare dominant neurodegenerative disease of genetic heritance. Patients of HD suffer coordination problems and chorea and progressive damage of the cognitive function. HD is caused by the presence of an abnormally long CAG expansion, encoding polyglutamines (polyQs), in the first exon of the huntingtin (htt) gene. When carriers have 39 or more triplets huntingtin acquires a toxic gain of function, which impairs many cellular functions. Although this gene is ubiquitously expressed, mutant huntingtin (mHtt) affects particularly neurons, inducing neuronal degeneration that leads to cell death. mHtt is very prone to aggregation and there is a vivid debate about whether aggregation of mHtt is a cause or a consequence of HD. In this regard it is essential to understand the molecules and mechanisms involved in the dynamics of aggregation of polyQ-containing proteins, such as mHtt. We use C. elegans to screen for genes that modify the dynamics of aggregation of polyQ-containing proteins. We isolated a number of mutants from the AM141 strain, which contains a transgene that induces the expression of a tandem of 40 glutamines (40Q) fused in frame with YFP. This strain shows an age-dependent aggregation pattern that can be easily followed using a dissecting microscope equipped with fluorescence. We sequenced by NGS means the whole genome of several mutant worms, and we have identified, using bioinformatics, a mutation in the unc-1/stomatinlike protein gene, vlt10, which enhances the aggregation phenotype of AM141. To verify the role of unc-1 in the dynamics of aggregation, we have introduced different unc-1 alleles within AM141 which confirmed that unc-1 is an enhancer of aggregation. We also show that ARNi against this gene also increases the speed of the aggregation pattern of AM141. We are currently working to find out the mechanism by which this gene modulates aggregation dynamics of polyglutamin-containing molecules.

[ES] En el laboratorio hemos generado mutantes que modulan la dinámica de agregación de péptidos que contienen expansiones de 40 glutaminas en gusanos nematodos C. elegans (Cepa AM141; genotipo-rmIs133[unc-54p::40Q::YFP] Morley et al., PNAS 2002). Esta cepa presente un fenotipo de agregación de las poliglutaminas dependiente de la edad. Los individuos jóvenes apenas presentan agregados, mientras que los adultos los producen en abundancia. En el presente trabajo caracterizaremos el papel modulador de la agregación de estas poliglutaminas del gen unc-1 del gusano, que tiene homología con el gen humano stomatin-like protein 3 (STOML3). Gusanos portadores de un alelo de pérdida total de función de este gen (unc-1(vlt10)) tienen agravado el fenotipo de agregación de péptidos 40Q::YFP. Este fenotipo es cuantificable porque los agregados colapsan en cuerpos de inclusión que son fácilmente observados en un estereoscopio equipado con fluorescencia. Para demostrar que la pérdida de función de unc-1 produce este fenotipo introduciremos en AM141 otros alelos caracterizados del gen, y disponibles en el repositorio de cepas de gusano (Caenorhabditis Genetics Center). Además emplearemos RNAi para silenciar el gen y dar más robustez a los experimentos descritos arriba. Todo esto sentará las bases para una futura búsqueda del mecanismo por el cual el gen modula la agregación de poliglutaminas., [EN] Huntington’s disease (HD) is a rare dominant neurodegenerative disease of genetic heritance. Patients of HD suffer coordination problems and chorea and progressive damage of the cognitive function. HD is caused by the presence of an abnormally long CAG expansion, encoding polyglutamines (polyQs), in the first exon of the huntingtin (htt) gene. When carriers have 39 or more triplets huntingtin acquires a toxic gain of function, which impairs many cellular functions. Although this gene is ubiquitously expressed, mutant huntingtin (mHtt) affects particularly neurons, inducing neuronal degeneration that leads to cell death. mHtt is very prone to aggregation and there is a vivid debate about whether aggregation of mHtt is a cause or a consequence of HD. In this regard it is essential to understand the molecules and mechanisms involved in the dynamics of aggregation of polyQ-containing proteins, such as mHtt. We use C. elegans to screen for genes that modify the dynamics of aggregation of polyQ-containing proteins. We isolated a number of mutants from the AM141 strain, which contains a transgene that induces the expression of a tandem of 40 glutamines (40Q) fused in frame with YFP. This strain shows an age-dependent aggregation pattern that can be easily followed using a dissecting microscope equipped with fluorescence. We sequenced by NGS means the whole genome of several mutant worms, and we have identified, using bioinformatics, a mutation in the unc-1/stomatinlike protein gene, vlt10, which enhances the aggregation phenotype of AM141. To verify the role of unc-1 in the dynamics of aggregation, we have introduced different unc-1 alleles within AM141 which confirmed that unc-1 is an enhancer of aggregation. We also show that ARNi against this gene also increases the speed of the aggregation pattern of AM141. We are currently working to find out the mechanism by which this gene modulates aggregation dynamics of polyglutamin-containing molecules.

Partial 1-trees are undirected graphs of treewidth at most one. Similarly, partial 1-DAGs are directed graphs of KellyWidth at most two. It is well-known that an undirected graph is a partial 1-tree if and only if it has no K_3 minor. In this paper, we generalize this characterization to partial 1-DAGs. We show that partial 1-DAGs are characterized by three forbidden directed minors, K_3, N_4 and M_5.

Tourism is a relatively new research field in China. Theme parks, being a branch of tourism industry, were firstly introduced to Chinese people two decades ago. However, the current situation and issues of Chinese theme parks has not been well studied. This research intended to explore the relationship between Chinese culture and theme parks as well as problems of the existing Chinese theme parks. Tourist behaviour, tourism market segmentation, culture transmission theory and Hofstede’s culture theory were applied in the research. Twenty-one semi-structured in-depth interviews and two focus groups were pursued for data collection. Based on the data analysis, two main findings were identified: the segmentation of Chinese theme parks is rather crude; and the themes lack originality and uniqueness.

Tourism is a relatively new research field in China. Theme parks, being a branch of tourism industry, were firstly introduced to Chinese people two decades ago. However, the current situation and issues of Chinese theme parks has not been well studied. This research intended to explore the relationship between Chinese culture and theme parks as well as problems of the existing Chinese theme parks. Tourist behaviour, tourism market segmentation, culture transmission theory and Hofstede’s culture theory were applied in the research. Twenty-one semi-structured in-depth interviews and two focus groups were pursued for data collection. Based on the data analysis, two main findings were identified: the segmentation of Chinese theme parks is rather crude; and the themes lack originality and uniqueness.

Tourism is a relatively new research field in China. Theme parks, being a branch of tourism industry, were firstly introduced to Chinese people two decades ago. However, the current situation and issues of Chinese theme parks has not been well studied. This research intended to explore the relationship between Chinese culture and theme parks as well as problems of the existing Chinese theme parks. Tourist behaviour, tourism market segmentation, culture transmission theory and Hofstede’s culture theory were applied in the research. Twenty-one semi-structured in-depth interviews and two focus groups were pursued for data collection. Based on the data analysis, two main findings were identified: the segmentation of Chinese theme parks is rather crude; and the themes lack originality and uniqueness.

The object of this paper is to jointly test the existence of income smoothing, capital management behavior and procyclicality with respect to Chinese commercial banks' provisioning during 2009-2014. Our results provide evidence for income smoothing behavior and procyclical provisioning, but we find no evidence for capital management behavior. In order to address the problems of income smoothing and procyclical provisioning, we give the following suggestions. Bank regulators should further promote the implementation of Basel III regimes among Chinese commercial banks. The dynamic provisioning practice should be promoted and the accounting disclosure requirements should be improved. Besides, bank regulators should require banks to write off uncollectible loans in time and should also strengthen the supervision and scrutiny of banks' activities.

Tourism is a relatively new research field in China. Theme parks, being a branch of tourism industry, were firstly introduced to Chinese people two decades ago. However, the current situation and issues of Chinese theme parks has not been well studied. This research intended to explore the relationship between Chinese culture and theme parks as well as problems of the existing Chinese theme parks. Tourist behaviour, tourism market segmentation, culture transmission theory and Hofstede’s culture theory were applied in the research. Twenty-one semi-structured in-depth interviews and two focus groups were pursued for data collection. Based on the data analysis, two main findings were identified: the segmentation of Chinese theme parks is rather crude; and the themes lack originality and uniqueness.