In 5G Ultra-Dense Networks, a distributed wireless backhaul is an attractive solution for forwarding traffic to the core. The macro-cell coverage area is divided into many small cells. A few of these cells are designated as gateways and are linked to the core by high-capacity fiber optic links. Each small cell is associated with one gateway and all small cells forward their traffic to their respective gateway through multi-hop mesh networks. We investigate the gateway location problem and show that finding near-optimal gateway locations improves the backhaul network capacity. An exact p-median integer linear program is formulated for comparison with our novel K-GA heuristic that combines a Genetic Algorithm (GA) with K-means clustering to find near-optimal gateway locations. We compare the performance of KGA with six other approaches in terms of average number of hops and backhaul network capacity at different node densities through extensive Monte Carlo simulations. All approaches are tested in various user distribution scenarios, including uniform distribution, bivariate Gaussian distribution, and cluster distribution. In all cases K-GA provides near-optimal results, achieving average number of hops and backhaul network capacity within 2% of optimal while saving an average of 95% of the execution time.

We consider the problem of domain generalization, in which a predictor is trained on data drawn from a family of related training domains and tested on a distinct and unseen test domain. While a variety of approaches have been proposed for this setting, it was recently shown that no existing algorithm can consistently outperform empirical risk minimization (ERM) over the training domains. To this end, in this paper we propose a novel approach for the domain generalization problem called Model-Based Domain Generalization. In our approach, we first use unlabeled data from the training domains to learn multi-modal domain transformation models that map data from one training domain to any other domain. Next, we propose a constrained optimization-based formulation for domain generalization which enforces that a trained predictor be invariant to distributional shifts under the underlying domain transformation model. Finally, we propose a novel algorithmic framework for efficiently solving this constrained optimization problem. In our experiments, we show that this approach outperforms both ERM and domain generalization algorithms on numerous well-known, challenging datasets, including WILDS, PACS, and ImageNet. In particular, our algorithms beat the current state-of-the-art methods on the very-recently-proposed WILDS benchmark by up to 20 percentage points.

Cloud computing accelerates design space exploration in logic synthesis, and parameter tuning in physical design. However, deploying EDA jobs on the cloud requires EDA teams to deeply understand the characteristics of their jobs in cloud environments. Unfortunately, there has been little to no public information on these characteristics. Thus, in this paper, we formulate the problem of migrating EDA jobs to the cloud. First, we characterize the performance of four main EDA applications, namely: synthesis, placement, routing and static timing analysis. We show that different EDA jobs require different machine configurations. Second, using observations from our characterization, we propose a novel model based on Graph Convolutional Networks to predict the total runtime of a given application on different machine configurations. Our model achieves a prediction accuracy of 87%. Third, we develop a new formulation for optimizing cloud deployments in order to reduce deployment costs while meeting deadline constraints. We present a pseudo-polynomial optimal solution using a multi-choice knapsack mapping that reduces costs by 35.29%.

Network models provide an efficient way to represent many real life problems mathematically. In the last few decades, the field of network optimization has witnessed an upsurge of interest among researchers and practitioners. The network models considered in this thesis are broadly classified into four types including transportation problem, shortest path problem, minimum spanning tree problem and maximum flow problem. Quite often, we come across situations, when the decision parameters of network optimization problems are not precise and characterized by various forms of uncertainties arising from the factors, like insufficient or incomplete data, lack of evidence, inappropriate judgements and randomness. Considering the deterministic environment, there exist several studies on network optimization problems. However, in the literature, not many investigations on single and multi objective network optimization problems are observed under diverse uncertain frameworks. This thesis proposes seven different network models under different uncertain paradigms. Here, the uncertain programming techniques used to formulate the uncertain network models are (i) expected value model, (ii) chance constrained model and (iii) dependent chance constrained model. Subsequently, the corresponding crisp equivalents of the uncertain network models are solved using different solution methodologies. The solution methodologies used in this thesis can be broadly categorized as classical methods and evolutionary algorithms. The classical methods, used in this thesis, are Dijkstra and Kruskal algorithms, modified rough Dijkstra algorithm, global criterion method, epsilon constraint method and fuzzy programming method. Whereas, among the evolutionary algorithms, we have proposed the varying population genetic algorithm with indeterminate crossover and considered two multi objective evolutionary algorithms.

We consider the problem of parameter estimation in slowly varying regression models with sparsity constraints. We formulate the problem as a mixed integer optimization problem and demonstrate that it can be reformulated exactly as a binary convex optimization problem through a novel exact relaxation. The relaxation utilizes a new equality on Moore-Penrose inverses that convexifies the non-convex objective function while coinciding with the original objective on all feasible binary points. This allows us to solve the problem significantly more efficiently and to provable optimality using a cutting plane-type algorithm. We develop a highly optimized implementation of such algorithm, which substantially improves upon the asymptotic computational complexity of a straightforward implementation. We further develop a heuristic method that is guaranteed to produce a feasible solution and, as we empirically illustrate, generates high quality warm-start solutions for the binary optimization problem. We show, on both synthetic and real-world datasets, that the resulting algorithm outperforms competing formulations in comparable times across a variety of metrics including out-of-sample predictive performance, support recovery accuracy, and false positive rate. The algorithm enables us to train models with 10,000s of parameters, is robust to noise, and able to effectively capture the underlying slowly changing support of the data generating process.

Deep neural networks (DNNs) are notorious for making more mistakes for the classes that have substantially fewer samples than the others during training. Such class imbalance is ubiquitous in clinical applications and very crucial to handle because the classes with fewer samples most often correspond to critical cases (e.g., cancer) where misclassifications can have severe consequences. Not to miss such cases, binary classifiers need to be operated at high True Positive Rates (TPR) by setting a higher threshold but this comes at the cost of very high False Positive Rates (FPR) for problems with class imbalance. Existing methods for learning under class imbalance most often do not take this into account. We argue that prediction accuracy should be improved by emphasizing reducing FPRs at high TPRs for problems where misclassification of the positive samples are associated with higher cost. To this end, we pose the training of a DNN for binary classification as a constrained optimization problem and introduce a novel constraint that can be used with existing loss functions to enforce maximal area under the ROC curve (AUC). We solve the resulting constrained optimization problem using an Augmented Lagrangian method (ALM), where the constraint emphasizes reduction of FPR at high TPR. We present experimental results for image-based classification applications using the CIFAR10 and an in-house medical imaging dataset. Our results demonstrate that the proposed method almost always improves the loss functions it is used with by attaining lower FPR at high TPR and higher or equal AUC.

We consider the zeroth-order optimization problem in the huge-scale setting, where the dimension of the problem is so large that performing even basic vector operations on the decision variables is infeasible. In this paper, we propose a novel algorithm, coined ZO-BCD, that exhibits favorable overall query complexity and has a much smaller per-iteration computational complexity. In addition, we discuss how the memory footprint of ZO-BCD can be reduced even further by the clever use of circulant measurement matrices. As an application of our new method, we propose the idea of crafting adversarial attacks on neural network based classifiers in a wavelet domain, which can result in problem dimensions of over 1.7 million. In particular, we show that crafting adversarial examples to audio classifiers in a wavelet domain can achieve the state-of-the-art attack success rate of 97.9%.

It is argued that a broad class of AGI-relevant algorithms can be expressed in a common formal framework, via specifying Galois connections linking search and optimization processes on directed metagraphs whose edge targets are labeled with probabilistic dependent types, and then showing these connections are fulfilled by processes involving metagraph chronomorphisms. Examples are drawn from the core cognitive algorithms used in the OpenCog AGI framework: Probabilistic logical inference, evolutionary program learning, pattern mining, agglomerative clustering, pattern mining and nonlinear-dynamical attention allocation. The analysis presented involves representing these cognitive algorithms as recursive discrete decision processes involving optimizing functions defined over metagraphs, in which the key decisions involve sampling from probability distributions over metagraphs and enacting sets of combinatory operations on selected sub-metagraphs. The mutual associativity of the combinatory operations involved in a cognitive process is shown to often play a key role in enabling the decomposition of the process into folding and unfolding operations; a conclusion that has some practical implications for the particulars of cognitive processes, e.g. militating toward use of reversible logic and reversible program execution. It is also observed that where this mutual associativity holds, there is an alignment between the hierarchy of subgoals used in recursive decision process execution and a hierarchy of subpatterns definable in terms of formal pattern theory.

In this paper, we investigate the constraint typology of mixed-integer linear programming MILP formulations. MILP is a commonly used mathematical programming technique for modelling and solving real-life scheduling, routing, planning, resource allocation, timetabling optimization problems, providing optimized business solutions for industry sectors such as: manufacturing, agriculture, defence, healthcare, medicine, energy, finance, and transportation. Despite the numerous real-life Combinatorial Optimization Problems found and solved, and millions yet to be discovered and formulated, the number of types of constraints, the building blocks of a MILP, is relatively much smaller. In the search of a suitable machine readable knowledge representation for MILPs, we propose an optimization modelling tree built based upon an MILP ontology that can be used as a guidance for automated systems to elicit an MILP model from end-users on their combinatorial business optimization problems.

We consider a discounted infinite horizon optimal stopping problem. If the underlying distribution is known a priori, the solution of this problem is obtained via dynamic programming (DP) and is given by a well known threshold rule. When information on this distribution is lacking, a natural (though naive) approach is "explore-then-exploit," whereby the unknown distribution or its parameters are estimated over an initial exploration phase, and this estimate is then used in the DP to determine actions over the residual exploitation phase. We show: (i) with proper tuning, this approach leads to performance comparable to the full information DP solution; and (ii) despite common wisdom on the sensitivity of such "plug in" approaches in DP due to propagation of estimation errors, a surprisingly "short" (logarithmic in the horizon) exploration horizon suffices to obtain said performance. In cases where the underlying distribution is heavy-tailed, these observations are even more pronounced: a ${\it single \, sample}$ exploration phase suffices.