Paper addresses generalization error bounds for learning with censored feedback.
problem Impact of censored feedback on generalization error bounds.
method Derives an extension of DKW inequality for non-IID data due to censored feedback and uses it to bound generalization error.
result Existing generalization error bounds fail to account for censored feedback, necessitating new bounds.
The paper provides guarantees for feedback control with sensor errors.
problem Certifying performance and safety in feedback control systems with sensor errors.
method Solving a supervised learning problem to characterize sensor errors and providing uniform error bounds.
result Finite-time convergence rate on sub-optimality of using a regressor in closed-loop for waypoint tracking.
Artificial neural networks are most commonly trained with the back-propagation algorithm, where the gradient for learning is provided by back-propagating the error, layer by layer, from the output layer to the hidden layers. A recently discovered method called feedback-alignment shows that the weights used for propagat…
New techniques improve distributed training with compressed gradients.
problem Gradient mismatch problem in local error feedback.
method Step-ahead error feedback and error averaging techniques.
result Our methods handle gradient mismatch and train faster than full-precision training.
New method provides fine-grained feedback on interactive student programs.
problem Time-consuming manual grading of interactive student programs.
method Meta-exploration approach using reinforcement learning.
result 94.3% accuracy in providing fine-grained feedback.
Quantized Adam reduces communication cost in deep learning training.
problem Reducing communication cost in distributed deep learning training.
method Gradient and weight quantization with error feedback in Adam.
result Proposed methods converge to first-order stationary points.
Sign-based algorithms (e.g. signSGD) have been proposed as a biased gradient compression technique to alleviate the communication bottleneck in training large neural networks across multiple workers. We show simple convex counter-examples where signSGD does not converge to the optimum. Further, even when it does conver…
This paper analyzes error feedback in compressed federated learning for non-convex optimization problems.
problem Reducing communication cost in federated learning with biased gradient compression.
method Proposes Fed-EF, a compressed federated learning scheme with error feedback, and analyzes its convergence rate and performance under partial client participation.
result Fed-EF can match the convergence rate of full-precision FL under data heterogeneity with a linear speedup and no extra slow-down factor due to stale error compensation.
SA-PEF improves federated learning efficiency by correcting gradient mismatches.
problem Slow decay of residual error in federated learning under non-IID data.
method Integrates step-ahead correction with partial error feedback.
result Achieves faster convergence and target accuracy compared to standard EF.
Time series forecasting gets much attention due to its impact on many practical applications. Higher-order neural network with recurrent feedback is a powerful technique which used successfully for forecasting. It maintains fast learning and the ability to learn the dynamics of the series over time. For that, in this p…
EF21-Muon optimizes deep learning with error feedback, improving efficiency and accuracy.
problem Lack of principled distributed frameworks for non-Euclidean LMO-based optimizers.
method Introduces EF21-Muon, a communication-efficient, non-Euclidean LMO-based optimizer with convergence guarantees.
result First efficient distributed implementation of non-Euclidean LMO-based optimizers, achieving up to 7x communication savings.
New method tackles composite optimization with error feedback.
problem Challenges in distributed machine learning training and message compression.
method Combines Dual Averaging with EControl for composite optimization.
result First strong convergence analysis for composite optimization with error feedback.
Clip21 improves convergence of gradient-clipped methods in DP settings.
problem Gradient clipping introduces bias in distributed training, causing convergence issues.
method Clip21 designs an error feedback mechanism to mitigate bias in gradient-clipped methods.
result Clip21 converges at the same rate as distributed gradient descent, improving from previous $\mathcal{O}\left(\frac{1}{\sqrt{K}}
ight)$ to $\mathcal{O}\left(\frac{1}{K}
ight)$.
Paper introduces robust learning from feature feedback, even with annotator errors.
problem Learning from human feedback on discriminative features, especially when annotators make mistakes.
method Develops a robust framework for learning with imperfect feedback, deriving regret bounds in adversarial and stochastic settings.
result Regret bounds independent of feature number, showing robust learning is not reducible to non-robust settings.
Recent advances in deep neural networks (DNNs) owe their success to training algorithms that use backpropagation and gradient-descent. Backpropagation, while highly effective on von Neumann architectures, becomes inefficient when scaling to large networks. Commonly referred to as the weight transport problem, each neur…
CausalRM models rewards from user feedback, overcoming noise and bias.
problem Aligning language models with user preferences from noisy, biased feedback.
method Causal-theoretic reward modeling framework addressing noise and bias in observational feedback.
result CausalRM learns accurate reward signals from noisy and biased observational feedback.
Modulo-SK outperforms Deepcode in error probability and feedback rounds.
problem Improving communication over noisy channels with deep learning.
method Combining classical SK scheme with modulo-arithmetic for deterministic feedback.
result Modulo-SK requires less feedback SNR and fewer rounds than Deepcode.
Graph-based approach repairs programs from diagnostic feedback.
problem Learning to repair programs from limited labeled data and compiler error messages.
method Introduces program-feedback graph and graph neural network for reasoning, and self-supervised learning with unlabeled programs.
result DrRepair significantly outperforms prior work, achieving high repair rates.
Improved error feedback method reduces communication complexity in distributed training.
problem Improving convergence in distributed training methods with compression techniques.
method Introduced and improved a modern form of error feedback (EF21) by reducing its theoretical communication complexity.
result Communication complexity depends on the arithmetic mean of smoothness parameters, leading to significant improvements.
We develop a communication-efficient distributed learning algorithm that is robust against Byzantine worker machines. We propose and analyze a distributed gradient-descent algorithm that performs a simple thresholding based on gradient norms to mitigate Byzantine failures. We show the (statistical) error-rate of our al…
Paper solves tracking control for (x,u)-flat systems using classical states.
problem Tracking control for (x,u)-flat systems. method Quasi-static feedback of classical states.
result Achieves linear, decoupled and asymptotically stable tracking error dynamics.
Perfect tracking control for real-world Euler-Lagrange systems is challenging due to uncertainties in the system model and external disturbances. The magnitude of the tracking error can be reduced either by increasing the feedback gains or improving the model of the system. The latter is clearly preferable as it allows…
Active learning framework for optimizing human preferences in reinforcement learning.
problem Selecting most informative feedback for training models of human preferences.
method Proposes an active learning framework to collect preferential feedback online or offline.
result Errors in DPO logit estimates diminish with more feedback.
Feedback improves ESN performance by 30-60% across various tasks.
problem Reducing computational complexity in ESNs for complex sequential data processing.
method State feedback to modify the internal reservoir state of ESNs.
result Feedback significantly improves ESN performance, reducing error by 30-60%.
New method improves optimization and DP in FL.
problem Combining strong DP and optimization in FL.
method Combining clipping, momentum, and error feedback.
result Optimal convergence rate and near optimal DP guarantees.
When learning from a batch of logged bandit feedback, the discrepancy between the policy to be learned and the off-policy training data imposes statistical and computational challenges. Unlike classical supervised learning and online learning settings, in batch contextual bandit learning, one only has access to a colle…
Safe-EF improves federated learning for non-smooth, constrained optimization.
problem Federated learning's communication bottlenecks with high-dimensional model updates.
method Error feedback (EF) for non-smooth convex optimization with safety constraints.
result Safe-EF matches lower complexity bounds and ensures safety constraints.
Unified framework for expert selection with bandit and lower-bound feedback.
problem Selecting the best expert in scenarios with bandit feedback and lower-bound information.
method Introduces a new feedback model combining bandit and lower-bound information, proving optimal regret bounds for modified Exp3 algorithms.
result Optimal regret bounds for modified Exp3 algorithms, generalizing both bandit and full-information settings.
New algorithm improves distributed SGD with random sparsification for better convergence and generalization.
problem Communication bottleneck in distributed deep learning.
method Proposes detached error feedback (DEF) algorithm to improve convergence and generalization of communication-efficient distributed SGD.
result Shows better convergence and generalization bounds than existing methods.
Despite the superiority of convolutional neural networks demonstrated in time series modeling and forecasting, it has not been fully explored on the design of the neural network architecture and the tuning of the hyper-parameters. Inspired by the incremental construction strategy for building a random multilayer percep…
The paper analyzes matrix completion with unlabeled implicit feedback and provides error bounds.
problem Matrix completion with shared low-rank ground truth and sampling distribution.
method Combining subspace recovery theory and matrix completion bounds.
result Error bounds showing contributions from estimating the sampling distribution and ground truth.
We present online boosting algorithms for multiclass classification with bandit feedback, where the learner only receives feedback about the correctness of its prediction. We propose an unbiased estimate of the loss using a randomized prediction, allowing the model to update its weak learners with limited information. …
A new method improves communication efficiency in distributed learning.
problem Reducing communication overhead in distributed machine learning.
method Transforming contractive compressors into induced unbiased compressors.
result Significant improvements in memory requirements and communication complexity.
In the past few years, deep learning has transformed artificial intelligence research and led to impressive performance in various difficult tasks. However, it is still unclear how the brain can perform credit assignment across many areas as efficiently as backpropagation does in deep neural networks. In this paper, we…
Algometrics analyzes how predictive models affect their own forecasts in algorithmic markets.
problem How predictive models affect their own forecasts in algorithmic markets.
method Introduces algometrics, a framework for time series with feedback, proving three results on deployment risk.
result Deployment risk cannot be identified from passive historical data alone, and historical rankings can invert under crowding.
Method improves volatility targeting for index construction.
problem High turnover, leverage spikes, and sensitivity to estimation error in existing volatility-targeting strategies.
method Proportional-control approach for setting index weights that corrects tracking error through feedback.
result The proportional-control approach achieves the target volatility more effectively than open-loop alternatives.
ECI improves time series prediction uncertainty quantification by smoothing miscoverage error.
problem Challenges in uncertainty quantification for time series prediction due to temporal dependence and distribution shift.
method Error-quantified Conformal Inference (ECI) by smoothing quantile loss function and introducing adaptive feedback scale.
result ECI achieves valid miscoverage control and tighter prediction sets than existing methods.
In this paper, we utilize information theory to study the fundamental performance limitations of generic feedback systems, where both the controller and the plant may be any causal functions/mappings while the disturbance can be with any distributions. More specifically, we obtain fundamental Lp bounds on …
Study quantile reward identification with 1-bit feedback constraints.
problem Best arm identification with quantile reward and 1-bit communication.
method Proposes an algorithm using noisy binary search for quantile reward estimation.
result Derives upper and lower bounds on sample complexity for 1-bit feedback.
Recommender systems play a crucial role in mitigating the problem of information overload by suggesting users' personalized items or services. The vast majority of traditional recommender systems consider the recommendation procedure as a static process and make recommendations following a fixed strategy. In this paper…
We propose a novel spectral convolutional neural network (CNN) model on graph structured data, namely Distributed Feedback-Looped Networks (DFNets). This model is incorporated with a robust class of spectral graph filters, called feedback-looped filters, to provide better localization on vertices, while still attaining…
Muon fails to converge on convex Lipschitz functions.
problem Understanding the convergence of Muon on convex and Lipschitz functions.
method Analyzing Muon's performance on convex and Lipschitz functions without error feedback.
result Muon does not converge on convex and Lipschitz functions, regardless of learning rate schedule.
Agents trained in simulation may make errors in the real world due to mismatches between training and execution environments. These mistakes can be dangerous and difficult to discover because the agent cannot predict them a priori. We propose using oracle feedback to learn a predictive model of these blind spots to red…
Not all types of supervision signals are created equal: Different types of feedback have different costs and effects on learning. We show how self-regulation strategies that decide when to ask for which kind of feedback from a teacher (or from oneself) can be cast as a learning-to-learn problem leading to improved cost…
A new RL method improves revenue management with delayed feedback.
problem Delayed feedback in revenue management affects substantial value.
method Choice-model-assisted Q-learning for delayed feedback revenue management.
result Q-learning with model-imputed targets converges to an optimal Q-function.
In semantic parsing for question-answering, it is often too expensive to collect gold parses or even gold answers as supervision signals. We propose to convert model outputs into a set of human-understandable statements which allow non-expert users to act as proofreaders, providing error markings as learning signals to…
Algorithm identifies Copeland winners in dueling bandits with ternary feedback.
problem Identifying Copeland winners in dueling bandits with indifferences.
method Proposed POCOWISTA algorithm with a sample complexity close to lower bound.
result Algorithm shows excellent performance, even for conventional dueling bandits.
Random Feedback Alignment helps solve low-rank matrix factorization problems.
problem Solving low-rank matrix factorization problems efficiently.
method Random Feedback Alignment (FA) as a bio-plausible alternative to gradient descent.
result FA converges to the optimal solution when the rank of the matrix is at least the rank of the input matrix.