We address the challenge of optimizing meta-parameters (hyperparameters) in machine learning, a key factor for efficient training and high model performance. Rather than relying on expensive meta-parameter search methods, we introduce MetaOptimize: a dynamic approach that adjusts meta-parameters, particularly step sizes (also known as learning rates), during training. More specifically, MetaOptimize can wrap around any first-order optimization algorithm, tuning step sizes on the fly to minimize a specific form of regret that considers the long-term impact of step sizes on training, through a discounted sum of future losses. We also introduce lower-complexity variants of MetaOptimize that, in conjunction with its adaptability to various optimization algorithms, achieve performance comparable to those of the best hand-crafted learning rate schedules across diverse machine learning tasks.

We consider the problem of federated learning in a one-shot setting in which there are$m$machines, each observing$n$sample functions from an unknown distribution on non-convex loss functions. Let$F:[-1,1]^{d}\to {\mathbb {R}} $be the expected loss function with respect to this unknown distribution. The goal is to find an estimate of the minimizer of$F$. Based on its observations, each machine generates a signal of bounded length$B$and sends it to a server. The server collects signals of all machines and outputs an estimate of the minimizer of$F$. We show that the expected loss of any algorithm is lower bounded by$\max \big (1/(\sqrt {n}(mB)^{1/d}), 1/\sqrt {mn}\big)$, up to a logarithmic factor. We then prove that this lower bound is order optimal in$m$and$n$by presenting a distributed learning algorithm, called Multi-Resolution Estimator for Non-Convex loss function (MRE-NC), whose expected loss matches the lower bound for large$mn$up to polylogarithmic factors.

Gradient-based methods for value estimation in reinforcement learning have favorable stability properties, but they are typically much slower than Temporal Difference (TD) learning methods. We study the root causes of this slowness and show that Mean Square Bellman Error (MSBE) is an ill-conditioned loss function in the sense that its Hessian has large condition-number. To resolve the adverse effect of poor conditioning of MSBE on gradient based methods, we propose a low complexity batch-free proximal method that approximately follows the Gauss-Newton direction and is asymptotically robust to parameterization. Our main algorithm, called RANS, is efficient in the sense that it is significantly faster than the residual gradient methods while having almost the same computational complexity, and is competitive with TD on the classic problems that we tested.

We consider distributed statistical optimization in one-shot setting, where there are $m$ machines each observing $n$ i.i.d. samples. Based on its observed samples, each machine sends a $B$-bit-long message to a server. The server then collects messages from all machines, and estimates a parameter that minimizes an expected convex loss function. We investigate the impact of communication constraint, $B$, on the expected error and derive a tight lower bound on the error achievable by any algorithm. We then propose an estimator, which we call Multi-Resolution Estimator (MRE), whose expected error (when $B\ge d\log mn$ where $d$ is the dimension of parameter) meets the aforementioned lower bound up to a poly-logarithmic factor in $mn$. The expected error of MRE, unlike existing algorithms, tends to zero as the number of machines ($m$) goes to infinity, even when the number of samples per machine ($n$) remains upper bounded by a constant. We also address the problem of learning under tiny communication budget, and present lower and upper error bounds for the case that the budget $B$ is a constant.

We consider distributed statistical optimization in one-shot setting, where there are $m$ machines each observing $n$ i.i.d samples. Based on its observed samples, each machine then sends an $O(\log(mn))$-length message to a server, at which a parameter minimizing an expected loss is to be estimated. We propose an algorithm called Multi-Resolution Estimator (MRE) whose expected error is no larger than $\tilde{O}( m^{-1/\max(d,2)} n^{-1/2})$, where $d$ is the dimension of the parameter space. This error bound meets existing lower bounds up to poly-logarithmic factors, and is thereby order optimal. The expected error of MRE, unlike existing algorithms, tends to zero as the number of machines ($m$) goes to infinity, even when the number of samples per machine ($n$) remains upper bounded by a constant. This property of the MRE algorithm makes it applicable in new machine learning paradigms where $m$ is much larger than $n$.

In this paper, a property for sparse recovery algorithms, called invariancy, is introduced. The significance of invariancy is that the performance of the algorithms with this property is less affected when the sensing (i.e., the dictionary) is ill-conditioned. This is because for this kind of algorithms, there exists implicitly an equivalent well-conditioned problem, which is being solved. Some examples of sparse recovery algorithms will also be considered and it will be shown that some of them, such as SL0, Basis Pursuit (using interior point LP solver), FOCUSS, and hard thresholding algorithms, are invariant, and some others, like Matching Pursuit and SPGL1, are not. Then, as an application example of the invariancy property, a sparse-decomposition-based method for direction of arrival estimation is reviewed, and it is shown that if an invariant algorithm is utilized for solving the corresponding sparse recovery problem, the spatial characteristics of the sensors will have essentially no effect on the final estimation, provided that the number of sensors is large enough.

Considering the collection of all networks with independent set interference model, Shah, Tse, and Tsitsiklis showed that there exist scheduling algorithms with polynomial complexity and delay, only if the maximum independent set problem can be solved in polynomial time (equivalently, P=NP). In this paper, we extend this result to arbitrary collections of networks and present a clear-cut criterion for the existence of polynomial complexity and delay scheduling algorithms relative to a given collection of networks with arbitrary interference models, not confined to independent set interference or SINR models, and not necessarily encompassing all network topologies. This amounts to the equivalence of polynomial scheduling and effective approximation of maximum weighted actions.

In this paper, we propose an analytical approach to compute the probability of connectivity for one-dimensional ad hoc networks. The proposed analysis gives the exact probability of connectivity for an arbitrary distribution of nodes, provided that nodes are independently and identically distributed. We conduct separate analyses for two cases; in the first case, the number of nodes varies by time under a stationary distribution and in the second case, there is a fixed (known) number of nodes in the network. Using the approaches presented in this work, we are able to derive closed-form formulas for the probability of connectivity for some spatial distributions, while for more complicated distributions, our approach leads to tractable numerical algorithms. As an example, we apply our method to a special case (uniform distribution) and derive a closed-form formula for its probability of connectivity. Finally, we confirm the validity of our analytical approach by simulation for several distributions and show higher accuracy and applicability of the proposed approach compared with existing methods.