We explore the emergence of intelligent behavior in artificial systems by investigating how the complexity of rule-based systems influences the capabilities of models trained to predict these rules. Our study focuses on elementary cellular automata (ECA), simple yet powerful one-dimensional systems that generate behaviors ranging from trivial to highly complex. By training distinct Large Language Models (LLMs) on different ECAs, we evaluated the relationship between the complexity of the rules' behavior and the intelligence exhibited by the LLMs, as reflected in their performance on downstream tasks. Our findings reveal that rules with higher complexity lead to models exhibiting greater intelligence, as demonstrated by their performance on reasoning and chess move prediction tasks. Both uniform and periodic systems, and often also highly chaotic systems, resulted in poorer downstream performance, highlighting a sweet spot of complexity conducive to intelligence. We conjecture that intelligence arises from the ability to predict complexity and that creating intelligence may require only exposure to complexity.

Discrete diffusion has achieved state-of-the-art performance, outperforming or approaching autoregressive models on standard benchmarks. In this work, we introduce Discrete Diffusion with Planned Denoising (DDPD), a novel framework that separates the generation process into two models: a planner and a denoiser. At inference time, the planner selects which positions to denoise next by identifying the most corrupted positions in need of denoising, including both initially corrupted and those requiring additional refinement. This plan-and-denoise approach enables more efficient reconstruction during generation by iteratively identifying and denoising corruptions in the optimal order. DDPD outperforms traditional denoiser-only mask diffusion methods, achieving superior results on language modeling benchmarks such as text8, OpenWebText, and token-based generation on ImageNet $256 \times 256$. Notably, in language modeling, DDPD significantly reduces the performance gap between diffusion-based and autoregressive methods in terms of generative perplexity. Code is available at https://github.com/liusulin/DDPD.

In an era where artificial intelligence and machine learning algorithms increasingly impact human life, it is crucial to develop models that account for potential discrimination in their predictions. This paper tackles this problem by introducing a new classification tree algorithm using a novel splitting criterion that incorporates fairness adjustments into the tree-building process. The proposed method integrates a fairness-aware impurity measure that balances predictive accuracy with fairness across protected groups. By ensuring that each splitting node considers both the gain in classification error and the fairness, our algorithm encourages splits that mitigate discrimination. Importantly, in penalizing unfair splits, we account for the uncertainty in the fairness metric by utilizing its confidence interval instead of relying on its point estimate. Experimental results on benchmark and synthetic datasets illustrate that our method effectively reduces discriminatory predictions compared to traditional classification trees, without significant loss in overall accuracy.

Bilevel optimization has recently attracted considerable attention due to its abundant applications in machine learning problems. However, existing methods rely on prior knowledge of problem parameters to determine stepsizes, resulting in significant effort in tuning stepsizes when these parameters are unknown. In this paper, we propose two novel tuning-free algorithms, D-TFBO and S-TFBO. D-TFBO employs a double-loop structure with stepsizes adaptively adjusted by the "inverse of cumulative gradient norms" strategy. S-TFBO features a simpler fully single-loop structure that updates three variables simultaneously with a theory-motivated joint design of adaptive stepsizes for all variables. We provide a comprehensive convergence analysis for both algorithms and show that D-TFBO and S-TFBO respectively require $O(\frac{1}{\epsilon})$ and $O(\frac{1}{\epsilon}\log^4(\frac{1}{\epsilon}))$ iterations to find an $\epsilon$-accurate stationary point, (nearly) matching their well-tuned counterparts using the information of problem parameters. Experiments on various problems show that our methods achieve performance comparable to existing well-tuned approaches, while being more robust to the selection of initial stepsizes. To the best of our knowledge, our methods are the first to completely eliminate the need for stepsize tuning, while achieving theoretical guarantees.

We consider neural networks (NNs) where the final layer is down-scaled by a fixed hyperparameter $\gamma$. Recent work has identified $\gamma$ as controlling the strength of feature learning. As $\gamma$ increases, network evolution changes from "lazy" kernel dynamics to "rich" feature-learning dynamics, with a host of associated benefits including improved performance on common tasks. In this work, we conduct a thorough empirical investigation of the effect of scaling $\gamma$ across a variety of models and datasets in the online training setting. We first examine the interaction of $\gamma$ with the learning rate $\eta$, identifying several scaling regimes in the $\gamma$-$\eta$ plane which we explain theoretically using a simple model. We find that the optimal learning rate $\eta^*$ scales non-trivially with $\gamma$. In particular, $\eta^* \propto \gamma^2$ when $\gamma \ll 1$ and $\eta^* \propto \gamma^{2/L}$ when $\gamma \gg 1$ for a feed-forward network of depth $L$. Using this optimal learning rate scaling, we proceed with an empirical study of the under-explored "ultra-rich" $\gamma \gg 1$ regime. We find that networks in this regime display characteristic loss curves, starting with a long plateau followed by a drop-off, sometimes followed by one or more additional staircase steps. We find networks of different large $\gamma$ values optimize along similar trajectories up to a reparameterization of time. We further find that optimal online performance is often found at large $\gamma$ and could be missed if this hyperparameter is not tuned. Our findings indicate that analytical study of the large-$\gamma$ limit may yield useful insights into the dynamics of representation learning in performant models.

Learning from demonstrations usually faces an ill-posed problem of inferring the expert reward functions. To facilitate safe learning from demonstrations, the paper formulates a maximin learning problem over a convex reward polytope, in order to guarantee that the worst possible consistent reward would yield a policy that is not much worse than optimal. The assumption is that the reward is linear in known features. The authors proposed two method: (i) ellipsoid method and (ii) follow-the-perturbed leader using separation oracles and a given MDP solver. The experiment is done in a grid world setting, and a modified version of the cart-pole problem.

The paper proposes a general framework for interactive learning. In the framework, the machine learning models are represented as the nodes in a graph G and the user feedback are represented as weighted edges in G. Under the assumption of "if s, s* are the proposed and target models, then any (correct) user feedback s' must lie on the shortest s-s* path in G", the author showed that the Multiplicative Weights Update algorithm can efficiently learn the target model. The framework can be applied to three important machine learning tasks: ranking, clustering, and classification. The problem investigated in the paper is interesting and important. The theoretical results of the paper is convincing.

We may earn revenue from the products available on this page and participate in affiliate programs. As a former elementary school teacher, I'm on board with any plaything that not only entertains but also increases skills, such as hand-eye coordination, or imparts knowledge on a potentially difficult subject like, say, physics. Our picks include a well-rounded quadcopter with a camera that's capable of tricks (our best overall, the DEERC D20 Mini Drone for Kids) all the way to a tiny but fun cameraless beginner's copter to get the little ones up to speed with flying at speed at a price. Here, then, are our picks for the best drones for kids of all ages … and a few adults, too. When choosing these drones, we considered various factors.

The paper studies the framework of teaching a loss function to a machine learning algorithm (the student model). Inspired from ideas of machine teaching and recent work of "learning to teach" [Fan et al. 18], the paper proposes L2T-DLF framework where a teacher model is jointly trained with a student model. Here, the teacher's goal is to learn a better policy of how to generate dynamic loss functions for the student by accounting for the current state of the student (e.g., training iteration, training error, test error). As shown in Algorithm#1, the teacher/student interaction happens in episodes: (1) the teacher's parameter \theta is fixed in a given episode, (2) the student model is trained end-to-end, and (3) then \theta is updated. In Section 3.3, the paper proposes a gradient-based method to update the parameter of the teacher model.

This paper studies the online learning (stochastic and full-information) problem of bidding in multi commodity first price auctions. The paper introduces a polynomial time algorithm that achieves a regret of \sqrt{T log(T)} that has a near optimal dependence on T. The main challenge that the paper has to deal with is to find a computationally efficient algorithm for computing the best biding strategy given a known distribution.The authors first demonstrate that natural approaches for solving this problem exactly are not computationally efficient (this is not a formal np-hardness proof). Then, they provide a FPTAS for solving the problem using dynamic programming. Once they have a FPTAS for the offline problem, their results hold for the stochastic online setting using existing reductions. I haven't carefully looked in to the details of their analysis of the dynamic programming, but I think the effectiveness of it here is interesting and surprising -- specially given that the variation of this problem for the second price auctions is hard to approximate.